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