Toom-Cook non-congruent multiplication

Kevin Ryde user42 at
Mon Mar 1 10:10:08 CET 2004

Josh Liu <zliu2 at> writes:
> One can multiply $n$ point by $m$ point numbers with $n+m-1$ point
> multiplications of congruent numbers by applying the Toom-Cook
> multiplication algorithm. The degree of an $n-1$ degree polynomial
> multiplied by an $m-1$ degree polynomial will yield an $n+m-1$ degree
> polynomial.

I think there's some freedom in where one makes the split points too,
ie. it doesn't have to be 1/2 or 1/3 of the bigger operand.  Torbjorn
had a reference to a guy (Tim Smith?) on sci.math who did some

More information about the gmp-devel mailing list