# Complexity of Polynomial Division

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}$

• Since $q(x)$ is of constant degree, wouldn't trivial division give you time $O(n)$? Oct 23, 2013 at 20:57
• Suppose $q$ has no repeated roots, and let $a_1,...,a_d$ be its roots. Then $P(x)$ mod $q(x)$ is determined by the values of $P(a_i)$, using a $d \times d$ Vandermonde interpolation. Although we can't compute the $a_i$ exactly, they can be computed to any desired precision in $\mathsf{NC}$ (Neff-Reif). I think, but am not sure, that the precision needed for the $d \times d$ interpolation is low enough that this can all be made to run in polytime, if not in $\mathsf{NC}$. Oct 23, 2013 at 20:57
• @MCH: Euclidean division can take $O(N)$ time, but $N$ is specified in binary, so that's exponential time... Oct 23, 2013 at 20:58
• When $q$ has a repeated root, say $a_1$, then we need to know not only the value of $P(a_1)$ but also its derivative $P'(a_1)$ (number of derivatives needed = multiplicity of the root - 1), and then I think the rest of my previous idea should work more or less the same. Oct 23, 2013 at 21:10
• I think the point is that you don't actually need the $N$-th bit of the root (which may be hard, as per your reference), you just need to know the root to sufficient accuracy (which is what Neff-Reif gives). The thing I'm still not sure of is how much accuracy is needed to do this particular interpolation. Oct 23, 2013 at 22:12

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