The Cooley-Tukey Algorithm is an FFT algorithm especially suited, and adapted for large integer multiplication. It was first published in 1965.
GIMPS' mprime uses "radix-4" Cooley-Tukey to achieve a computation time of the order of NlogN (for N*N multiplication).
http://en.wikipedia.org/wiki/Cooley-Tukey_FFT_algorithm
No comments:
Post a Comment