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

  • $\begingroup$ Since $q(x)$ is of constant degree, wouldn't trivial division give you time $O(n)$? $\endgroup$ Oct 23, 2013 at 20:57
  • 1
    $\begingroup$ 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}$. $\endgroup$ Oct 23, 2013 at 20:57
  • 1
    $\begingroup$ @MCH: Euclidean division can take $O(N)$ time, but $N$ is specified in binary, so that's exponential time... $\endgroup$ Oct 23, 2013 at 20:58
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 23, 2013 at 21:10
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 23, 2013 at 22:12

1 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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.