30 Jun
2006
30 Jun
'06
9:41 a.m.
* franktaw@netscape.net <franktaw@netscape.net> [Jun 30. 2006 11:15]:
To make this work for GF(2), you have to reinterpret them as polynomials over GF(2^k) for some sufficiently large k.
Franklin T. Adams-Watters
But then you have orders that are factors of 2^k-1, making it hard to have a fast transform. I wouldn't be surprised is float-FFT beats all other schemes for large enough degree. Exercise 8.30 on p.250 of "Modern Computer Algebra" by J. von zur Gathen and Juergen Gerhard (wonderful book!) suggests to use modulus x^(2n)+x^n+1 for n=3^k (ascribed to Schoenhage, 1977).