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$ – Mahdi Cheraghchi Oct 23 '13 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$ – Joshua Grochow Oct 23 '13 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$ – Joshua Grochow Oct 23 '13 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$ – Joshua Grochow Oct 23 '13 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$ – Joshua Grochow Oct 23 '13 at 22:12

Your Answer

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

Browse other questions tagged or ask your own question.