Multiplying Not-So-Big Integers with FFTs

[Torbjörn Granlund]

Paul Zimmermann <Paul.Zimmermann at inria.fr> writes:

  https://eprint.iacr.org/2026/2366

They use small fields, I presume?  Niels and I made some work on small
field FFTs some 10 years ago, and saw positive performance improvements,
in particiular for truly huge operands.

We used from 3 to 5 small prime fields, and two-dimensional Cooley-Tukey
(a k a Bailey 4-step IIRC).

(For huge operands the current code in GMP has poor cache locality,
while the code I and Niels worked on has good L1 hit rate.)

-- 
Torbjörn
Please encrypt, key id 0xC8601622