caching of transforms used for large multiplications

[Daniel Lichtblau]

On 06/14/2013 12:02 PM, Philip McLaughlin wrote:
> 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

Thanks, I'll have a look at that reference.

Daniel Lichtblau