caching of transforms used for large multiplications

Philip McLaughlin pbmcl at
Fri Jun 14 19:02:01 CEST 2013

Daniel Lichtblau wrote:

> That said, I confess I am not sure there is much need for this outside
> of subquadratic gcd code. If it is not more generally useful, then I
> guess this automation would only be of benefit to a limited set of
> users. (Like, maybe four of us.)

Years ago I published a paper in Math. Comp. which showed (Variation 2.) how to use both cyclic and negacyclic transforms in the context of Montgomery multiplication. The re-use of forward transforms, for example in powering algoorithms, was specifically mentioned. See

Unfortunately I've never had the time to actually implement the method so I don't know how useful it might be in practice.

Phil McLaughlin

More information about the gmp-devel mailing list