9
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
-1
$\begingroup$

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.
$\endgroup$
  • 2
    $\begingroup$ 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? $\endgroup$ – David Eppstein Apr 16 '13 at 6:26
  • 2
    $\begingroup$ 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. $\endgroup$ – David Harris Apr 16 '13 at 14:41

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.