<p>The following algorithms works well if the underlying field has a very small order $s$.</p>

<p>Suppose we know $q$ is irreducible, of a fixed degree $d$. Then, mod $q$, we know $x^{s^d} = x$ holds. Hence it suffices to pre-compute $p(x) \mod x^{s^d} - x$.</p>

<p>In general, $q(x)$ may decompose into a product of irreducible polynomials $q = q_1 \dots q_r$. In this case, a similar argument applies to computing $p$ modulo each $q_1, \dots, q_r$ separately, and then piecing the results together. So we really need to compute $p(x) \mod x^{s^{d'}} - x$ for each $d' \leq d$.</p>

CC BY-SA 3.0
2013-04-16T22:43:23.237Z
2013-04-18T16:07:54.100Z
2013-04-18T16:07:54.100Z
David Harris
<p>I think there is a pretty fast way to do this. Let the coefficients of the yet unknown polynomial $q$ be $b_i$, so $q=\sum_{i=0}^d b_ix^i$ where $d$ is some small number. Now let us start computing $p \pmod q$ where $p=\sum_{i=0}^D a_ix^i$, where $D$ is big and the $a_i$ are known. This we do by reducing the degree using equalities as $a_Dx^D= \frac {-a_D}{b_d} \sum_{i=1}^{d-1} b_{d-i}x^{D-i}$. Eventually what we get is a degree $&lt;d-1$ polynomial, whose coefficients are polynomials of the $b_i$ (since the $a_i$ are known). These polynomials we can compute fast once we get $q$.</p>

CC BY-SA 3.0
2013-04-18T17:17:35.633Z
2013-04-18T17:17:35.633Z
domotorp
<p>See excellent comments about this post below. :)</p>

<hr>

<p><strong>Preprocessing; input:</strong> $p(x)$</p>

<ol>
<li><p>Factor $p(x)$ as $p(x)=\prod_{i=0}^{1000} (x_i-r_i)$.</p></li>
<li><p>Store this as a table $T$ of distinct roots $r_j$ and their respective
multiplicities $m_j$.</p></li>
</ol>

<p><strong>Online phase; input:</strong> $q(x)$</p>

<ol>
<li><p>Factor $q(x)$ as $q(x)=\prod_{i=0}^5 (x_i-r'_i)$.</p></li>
<li><p>Store this as a list $L$ of distinct roots $r'_j$ and their respective
multiplicities $m'_j$.</p></li>
<li><p>While $L$ is not empty, remove the next root/multiplicity from $L$ and any like terms in $T$.</p></li>
<li><p>Read off $p(x)\bmod{q(x)}$ from the modified table $T$ and output.</p></li>
</ol>

<hr>

<p>Other comments:</p>

<ul>
<li>Obviously you want to sort the table $T$ and access it with binary search (or a tree).</li>
<li>(Let $d$ be the degree of $p(x)$.) If you want the output $p(x)\bmod{q(x)}$ to be in coefficient representation, you can just do a bunch of FFTs at the end to get $\tilde{O}(d)$ time.</li>
<li>Depending on how you formalize it, you can probably pre-compute a lot of the various ways you'd recombine the terms in $T$ beforehand (dynamic programming style), so that most (or all) of the multiplications are just look-ups. The dominating cost is then the number of look-ups, or roughly $O(\log d)$. If $d=1000$, this is just a handful of concrete, arithmetic operations.</li>
</ul>

CC BY-SA 3.0
2013-04-16T06:26:24.750Z
What field are you factoring p in? How big do you expect this representation to be in terms of the original field? And when you say to read off from the modified table and output, what do you mean?
David Eppstein
CC BY-SA 3.0
2013-04-16T14:41:26.020Z
This would only work if you are operating over a field where both $p$ and $q$ split. But this seems to be dependent on $q$; in particular, you cannot precompute the roots for $p$ alone. Furthermore, computing the roots of $q$ over such a large field will take time (at least) $|p|$; this is no better than the naive algorithm.
David Harris
CC BY-SA 3.0
2013-04-16T03:16:23.957Z
2013-04-16T20:52:42.647Z
2013-04-16T20:52:42.647Z
Daniel Apon
<p>Assume we operate in a finite field. We are given a large fixed polynomial p(x) (of, say, degree 1000) over this field. This polynomial is known beforehand and we are allowed to do computation using a lot of resources in the "initial phase." These results may be stored in reasonably small look-up tables.</p>

<p>At the end of the "initial phase", we will be given a small unknown polynomial q(x) (of, say, degree 5 or less). </p>

<p>Is there a fast way to compute p(x) mod q(x) given that we are allowed to do some complicated calculations in the "initial phase"? One obvious way is to calculate p(x) mod q(x) for all possible values of q(x). Is there a better way to do this?</p>

<cc.complexity-theory><ds.algorithms><algebra><algebraic-complexity><polynomials>
Find the remainder of a large fixed polynomial when divided by a small unknown polynomial
paulwaters
# Find the remainder of a large fixed polynomial when divided by a small unknown polynomial

(Asked by: username_0 on 2013-03-29)

Assume we operate in a finite field. We are given a large fixed polynomial p(x) (of, say, degree 1000) over this field. This polynomial is known beforehand and we are allowed to do computation using a lot of resources in the "initial phase." These results may be stored in reasonably small look-up tables.

At the end of the "initial phase", we will be given a small unknown polynomial q(x) (of, say, degree 5 or less).

Is there a fast way to compute p(x) mod q(x) given that we are allowed to do some complicated calculations in the "initial phase"? One obvious way is to calculate p(x) mod q(x) for all possible values of q(x). Is there a better way to do this?

**Tags:** cc.complexity-theory, ds.algorithms, algebra, algebraic-complexity, polynomials


---

## 3 answers

### Answer by username_1 on 2013-04-16. Score: 3

The following algorithms works well if the underlying field has a very small order $s$.

Suppose we know $q$ is irreducible, of a fixed degree $d$. Then, mod $q$, we know $x^{s^d} = x$ holds. Hence it suffices to pre-compute $p(x) \mod x^{s^d} - x$.

In general, $q(x)$ may decompose into a product of irreducible polynomials $q = q\_1 \dots q\_r$. In this case, a similar argument applies to computing $p$ modulo each $q\_1, \dots, q\_r$ separately, and then piecing the results together. So we really need to compute $p(x) \mod x^{s^{d'}} - x$ for each $d' \leq d$.


---

### Answer by username_2 on 2013-04-18. Score: 2

I think there is a pretty fast way to do this. Let the coefficients of the yet unknown polynomial $q$ be $b\_i$, so $q=\sum\_{i=0}^d b\_ix^i$ where $d$ is some small number. Now let us start computing $p \pmod q$ where $p=\sum\_{i=0}^D a\_ix^i$, where $D$ is big and the $a\_i$ are known. This we do by reducing the degree using equalities as $a\_Dx^D= \frac {-a\_D}{b\_d} \sum\_{i=1}^{d-1} b\_{d-i}x^{D-i}$. Eventually what we get is a degree $


---

### Answer by username_3 on 2013-04-16. Score: -1

See excellent comments about this post below. :)

---

**Preprocessing; input:** $p(x)$

1. Factor $p(x)$ as $p(x)=\prod\_{i=0}^{1000} (x\_i-r\_i)$.
2. Store this as a table $T$ of distinct roots $r\_j$ and their respective
   multiplicities $m\_j$.

**Online phase; input:** $q(x)$

1. Factor $q(x)$ as $q(x)=\prod\_{i=0}^5 (x\_i-r'\_i)$.
2. Store this as a list $L$ of distinct roots $r'\_j$ and their respective
   multiplicities $m'\_j$.
3. While $L$ is not empty, remove the next root/multiplicity from $L$ and any like terms in $T$.
4. Read off $p(x)\bmod{q(x)}$ from the modified table $T$ and output.

---

Other comments:

* Obviously you want to sort the table $T$ and access it with binary search (or a tree).
* (Let $d$ be the degree of $p(x)$.) If you want the output $p(x)\bmod{q(x)}$ to be in coefficient representation, you can just do a bunch of FFTs at the end to get $\tilde{O}(d)$ time.
* Depending on how you formalize it, you can probably pre-compute a lot of the various ways you'd recombine the terms in $T$ beforehand (dynamic programming style), so that most (or all) of the multiplications are just look-ups. The dominating cost is then the number of look-ups, or roughly $O(\log d)$. If $d=1000$, this is just a handful of concrete, arithmetic operations.

> **Comments:**
> **username_4**: What field are you factoring p in? How big do you expect this representation to be in terms of the original field? And when you say to read off from the modified table and output, what do you mean?  
> **username_1**: This would only work if you are operating over a field where both $p$ and $q$ split. But this seems to be dependent on $q$; in particular, you cannot precompute the roots for $p$ alone. Furthermore, computing the roots of $q$ over such a large field will take time (at least) $|p|$; this is no better than the naive algorithm.  

---

