<p>I don't know if this quite counts as an answer, but in fact this problem is <em>equivalent</em> to the matrix powering problem, so the references and comments on the  <a href="https://cstheory.stackexchange.com/questions/12785/complexity-of-matrix-powering">question about matrix powering</a> referenced in the OQ all apply here as well. (And this was a little too  long for a comment anyway.)</p>
<p>The reduction from matrix powering to polynomial division is in Section 3 of <a href="http://www.numdam.org/item/ITA_2000__34_1_39_0/" rel="nofollow noreferrer">this paper</a>, as referenced in a comment on the other question.</p>
<p>The reduction from computing <span class="math-container">$x^N mod q(x)$</span> to matrix powering is as follows. Given <span class="math-container">$N$</span> and <span class="math-container">$q$</span> as in the description of the problem, construct the <span class="math-container">$d \times d$</span> companion matrix <span class="math-container">$M_q$</span>. Using matrix powering, compute <span class="math-container">$M_q^N$</span>. Let <span class="math-container">$d = \deg q$</span>. Solve a <span class="math-container">$d^2 \times d$</span> system of linear equations in <span class="math-container">$poly(d)$</span> time (or even <span class="math-container">$\mathsf{NC}^2$</span> in <span class="math-container">$d$</span>, I believe) to compute the unique coefficients <span class="math-container">$c_i$</span> such that <span class="math-container">$M_q^N = \sum_{i=0}^{d-1} c_i M_q^i$</span>. Output <span class="math-container">$r_N(x) = \sum_{i=0}^{d-1} c_i x^i$</span>.</p>
<p><em>Proof of correctness.</em>
Since <span class="math-container">$M_q$</span> is the companion matrix of <span class="math-container">$q$</span>, its minimal polynomial is precisely <span class="math-container">$q$</span>. Thus for any power <span class="math-container">$N$</span> we have <span class="math-container">$M_q^N = r_N(M_q)$</span>, where here we mean literal equality of integer matrices (not modulo anything). Further, since <span class="math-container">$q$</span> has degree <span class="math-container">$d$</span> and is the minimal polynomial of <span class="math-container">$M_q$</span>, we have the <span class="math-container">$I, M_q, M_q^2, \dotsc, M_q^{d-1}$</span> is a linear basis of <span class="math-container">$V := Span_{\mathbb{Q}}\{M_q^a : a \in \mathbb{N}\}$</span>. Thus we may write <span class="math-container">$M_q^N$</span> uniquely as a linear combination <span class="math-container">$M_q^N = \sum_{i=0}^{d-1} c_i M_q^i$</span>, so the coefficients <span class="math-container">$c_i$</span> constructed in the reduction are indeed unique. Finally, by the linear independence of the first <span class="math-container">$d$</span> powers of <span class="math-container">$M_q$</span>, the fact that <span class="math-container">$M_q^N$</span> is also equal to <span class="math-container">$r_N(M_q)$</span>, and that <span class="math-container">$\deg r_N &lt; d$</span>, we must have <span class="math-container">$r_N(x) = \sum_{i=0}^{d-1} c_i x^i$</span>. (This also tells us that, although in principle from the linear equations the <span class="math-container">$c_i$</span> might have merely been rational, in fact they must be integers since they are the coefficients of <span class="math-container">$r_N$</span>.) QED</p>

CC BY-SA 4.0
2022-04-20T23:31:51.637Z
2022-04-20T23:31:51.637Z
Joshua Grochow
<p>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)}$? </p>

<p>I am specifically interested in the case when $P(x) = x^N$ for a binary integer $N$ and $q(x)$ is a <em>constant</em> degree polynomial. Any upper bound on this problem will imply the same bound on the <a href="https://cstheory.stackexchange.com/questions/12785/complexity-of-matrix-powering">matrix powering problem</a> (see comment there) for constant size matrices (the degree of $q(x)$ figures as the dimension of the matrix).</p>

<p>The problem can be reduced to $\mathsf{BitSLP}$ (see <a href="http://ftp.cs.rutgers.edu/pub/allender/slp.pdf" rel="nofollow noreferrer">this</a> for definition) e.g. by reducing the problem to computing (large) powers of a matrix (<a href="http://alexhealy.net/papers/FieldOps.pdf" rel="nofollow noreferrer">Healy-Viola</a> 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 <a href="http://eccc.hpi-web.de/report/2013/177/" rel="nofollow noreferrer">Allender et al</a> viz. $\mathsf{PH}^{\mathsf{PP}^{\mathsf{PP}^\mathsf{PP}}} \subseteq \mathsf{CH}$</p>

CC BY-SA 3.0
2013-10-23T20:57:23.763Z
Since $q(x)$ is of constant degree, wouldn't trivial division give you time $O(n)$?
Mahdi Cheraghchi
CC BY-SA 3.0
2013-10-23T20:57:47.180Z
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}$.
Joshua Grochow
CC BY-SA 3.0
2013-10-23T20:58:50.357Z
@MCH: Euclidean division can take $O(N)$ time, but $N$ is specified in binary, so that's exponential time...
Joshua Grochow
CC BY-SA 3.0
2013-10-23T21:10:32.757Z
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.
Joshua Grochow
CC BY-SA 3.0
2013-10-23T21:39:03.097Z
@Joshua Thanks for reference - I will check it. AFAIK best upper bound on the complexity of finding the N-th bit of (real) roots of a polynomial is the same as PosSLP (see e.g. http://arxiv.org/pdf/1112.4295.pdf). The real question is do we need that much precision.
SamiD
CC BY-SA 3.0
2013-10-23T22:12:48.693Z
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.
Joshua Grochow
<cc.complexity-theory><circuit-complexity><arithmetic-circuits>
Complexity of Polynomial Division
SamiD
# Complexity of Polynomial Division

(Asked by: username_0 on 2013-10-23)

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](https://cstheory.stackexchange.com/questions/12785/complexity-of-matrix-powering) (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](http://ftp.cs.rutgers.edu/pub/allender/slp.pdf) for definition) e.g. by reducing the problem to computing (large) powers of a matrix ([Healy-Viola](http://alexhealy.net/papers/FieldOps.pdf) 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](http://eccc.hpi-web.de/report/2013/177/) viz. $\mathsf{PH}^{\mathsf{PP}^{\mathsf{PP}^\mathsf{PP}}} \subseteq \mathsf{CH}$

**Tags:** cc.complexity-theory, circuit-complexity, arithmetic-circuits
> **Comments:**
> **username_1**: Since $q(x)$ is of constant degree, wouldn't trivial division give you time $O(n)$?  
> **username_2**: 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}$.  
> **username_2**: @MCH: Euclidean division can take $O(N)$ time, but $N$ is specified in binary, so that's exponential time...  
> **username_2**: 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.  
> **username_0**: @Joshua Thanks for reference - I will check it. AFAIK best upper bound on the complexity of finding the N-th bit of (real) roots of a polynomial is the same as PosSLP (see e.g. http://arxiv.org/pdf/1112.4295.pdf). The real question is do we need that much precision.  
> **username_2**: 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.  

---

## 1 answers

### Answer by username_2 on 2022-04-20. Score: 2

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](https://cstheory.stackexchange.com/questions/12785/complexity-of-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](http://www.numdam.org/item/ITA_2000__34_1_39_0/), 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


---

