Incongruent Multiplication with Interpolation of FFT Complexity

[Josh Liu]

  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.