Complexity of Polynomial Division

Question

Let $P(x)$ be a univariate polynomial with integer coefficients where both coefficients and degrees are in binary and let $q(x)$ be another polynomial also with integer coefficients where the degrees are given in unary and the coefficients in binary. What is the complexity of determining $P(x) \bmod{q(x)}$?

I am specifically interested in the case when $P(x) = x^N$ for a binary integer $N$ and $q(x)$ is a constant degree polynomial. Any upper bound on this problem will imply the same bound on the matrix powering problem (see comment there) for constant size matrices (the degree of $q(x)$ figures as the dimension of the matrix).

The problem can be reduced to $\mathsf{BitSLP}$ (see this for definition) e.g. by reducing the problem to computing (large) powers of a matrix (Healy-Viola show how to do the reduction over finite fields in Lemma 21 - the algorithm being essentially the Kung-Sieveking algorithm - but the basic ideas are the same over $\mathbb{Z}$ also. The challenge is to improve the bound from the one for $\mathsf{BitSLP}$ proved in Allender et al viz. $\mathsf{PH}^{\mathsf{PP}^{\mathsf{PP}^\mathsf{PP}}} \subseteq \mathsf{CH}$

Answer 1

I don't know if this quite counts as an answer, but in fact this problem is equivalent to the matrix powering problem, so the references and comments on the question about matrix powering referenced in the OQ all apply here as well. (And this was a little too long for a comment anyway.)

The reduction from matrix powering to polynomial division is in Section 3 of this paper, as referenced in a comment on the other question.

The reduction from computing $x^N mod q(x)$ to matrix powering is as follows. Given $N$ and $q$ as in the description of the problem, construct the $d \times d$ companion matrix $M_q$. Using matrix powering, compute $M_q^N$. Let $d = \deg q$. Solve a $d^2 \times d$ system of linear equations in $poly(d)$ time (or even $\mathsf{NC}^2$ in $d$, I believe) to compute the unique coefficients $c_i$ such that $M_q^N = \sum_{i=0}^{d-1} c_i M_q^i$. Output $r_N(x) = \sum_{i=0}^{d-1} c_i x^i$.

Proof of correctness. Since $M_q$ is the companion matrix of $q$, its minimal polynomial is precisely $q$. Thus for any power $N$ we have $M_q^N = r_N(M_q)$, where here we mean literal equality of integer matrices (not modulo anything). Further, since $q$ has degree $d$ and is the minimal polynomial of $M_q$, we have the $I, M_q, M_q^2, \dotsc, M_q^{d-1}$ is a linear basis of $V := Span_{\mathbb{Q}}\{M_q^a : a \in \mathbb{N}\}$. Thus we may write $M_q^N$ uniquely as a linear combination $M_q^N = \sum_{i=0}^{d-1} c_i M_q^i$, so the coefficients $c_i$ constructed in the reduction are indeed unique. Finally, by the linear independence of the first $d$ powers of $M_q$, the fact that $M_q^N$ is also equal to $r_N(M_q)$, and that $\deg r_N < d$, we must have $r_N(x) = \sum_{i=0}^{d-1} c_i x^i$. (This also tells us that, although in principle from the linear equations the $c_i$ might have merely been rational, in fact they must be integers since they are the coefficients of $r_N$.) QED