Incongruent Multiplication with Interpolation of FFT Complexity
Josh Liu
zliu2 at student.gsu.edu
Sat May 15 02:33:33 CEST 2004
Multiplication of incongruent factors (numbers that have disparagingly
different sizes) can be done with Toom-Cook interpolation. One
evaluates the two factor polynomials at $n$ different points and
multiplies their evaluations. This gives $n$ points on the product
polynomial. With these $n$ points, one can interpolate using Lagrangian
interpolation to obtain the coefficients of the product polynomial.
Langrangian interpolation is an $O(n^2)$ process.
\par
Now we change notation. For convenience we let $n$ be a power of of
two. So $n$ now becomes $2^n$. We can evaluate the two factor
polynomials at the $2^n$ roots of unity modulo $2^g+1$. Here $g$ is a
number that is at least as large as $2 \log \max (\max (u_i), \max
(v_i)) + \log max (m+1, n+1)$ where $u_i$ and $v_i$ are coefficients of
the two factor polynomials respectively and $m$ and $n$ are their
respective degrees. We then multiply these evaluations modulo $2^g+1$
obtaining $W (\omega^i)$ where $W(x)$ is the product polynomial,
$\omega^i$ are roots of unity modulo $2^g+1$. We then apply the inverse
NTT on the $2^n$ points $W (\omega^i)$ to obtain the coefficients of
the product polynomial.
\par
For convenience one can have the degree of the product polynomial be
$2^n-1$, 2^n$, or $2^n+1$.
\par
For degree $2^n-1$ products, we evaluate the product polynomial at the
$2^n$ roots of unity and use the NTT. For degree $2^n+1$ products, one
evaluates at the $2^n$ roots of unity along with evaluation at $0$ and
$\infinity$. This gives $2^n+2$ points that we have evaluated $W(x)$
at. This allows us to have the degree of $W(x)$ be anything up to and
including $2^n-1$. Interpolation for this case is tricker but still
possible at high speed. One needs to subtract $W(0)$ and $W(\omega^{i
2^n}) from every $W(\omega^i)$ to isolate a Vandermonde matrix. Next
one divides the $W(\omega^i)-W(0)-W(\omega^{i 2^n})$ by $\omega^i$.
With these updated values of the evaluation points, we can apply the
inverse NTT to obtain the middle coefficients of the product
polynomial.
\par
Evaluation at $2^n+1$ points would be like the above with one point
omitted.
More information about the gmp-devel
mailing list