caching of transforms used for large multiplications

[Philip McLaughlin]

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

http://www.ams.org/journals/mcom/2004-73-246/S0025-5718-03-01543-6/S0025-5718-03-01543-6.pdf

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

Regards,
Phil McLaughlin