I also wrote: > Next problem: > for non-power-of-two runlengths, the outputs of the > forward integer transform will occur in a fundamentally > different ordering than for the FFT, i.e. this wonderful > idea of the modular transform mirroring the floating FFT > is out the window when it comes to the dyadic-squaring > phase between the forward and inverse transforms.
At this point, the astute reader will be saying to him- or-herself, "Wait a minute: since we're taking about a dyadic (pointwise) complex squring here, who cares that the complex and modular data are arranged in different patterns? Just square 'em and let the inverse transform do the unscrambling for you." Sadly, things aren't quite so simple. Consider (say) a length N = 6 DFT of a strictly real input vector. The outputs will occur in the following pattern: X0 X1 + i*Y1 X2 + i*Y2 X3 X2 - i*Y2 X1 - i*Y1 Note the symmetry: X(N-j) = ~X(j), where ~ denotes complex conjugation. This symmetry allows us to cut the transform length in half, and in fact all the fast FFT-based large-integer codes use some variant of this strategy, be it implicitly in the structure of a real-input FFT (Prime95 uses such a method) or explicitly by doing a complex-input FFT and then combining outputs with index pairs (j, N-j) appropriately prior to doing the dyadic squaring (Mlucas uses this latter approach). In either case, one is making use in some fashion of the (j, N-j) symmetry of the outputs of a complex DFT applied to real input data, and this symmetry no longer holds when one is doing a modular transform over the field GF(q^2) and the runlength is not a power of 2. -Ernst _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
