Schönhage-Strassen

[Tsz Wo Sze]

Hi,

First, thanks to the authors of "A GMP-based Implementation of 
Schönhage-Strassen’s Large Integer Multiplication Algorithm".  The paper 
provides many useful information.  Some questions:

- Given n, the number of bits of the operands, what is the best choice of the 
FFT length and the Schönhage-Strassen modulus?

- What is the memory requirement for running Schönhage-Strassen?  Supposed there 
are 16GB memory.  What is the largest n that the machine can support?

- Is there a trade off between running time and memory when choosing the FFT 
length and the modulus?

- I supposed GMP is using Schönhage-Strassen for large integer multiplication.  
However, the author of y-cruncher claims that Hybrid NTT is faster than SSA in 
practice; see the quote below.  Do you agree?

http://www.numberworld.org/y-cruncher/algorithms.html
"The difference between the run-time complexities of Hybrid NTT and SSA  is on 
the order of double-logarithms. However, SSA has a much larger  Big-O constant - 
so large that Hybrid NTT is a lot faster for any  attainable size despite having 
a slightly inferior complexity.  (Of course, this could change if there are any 
new ground-breaking optimizations that apply to SSA but not to Hybrid NTT.)"

Regards,
Tsz-Wo