On Tue, Nov 14, 2006 at 04:37:02AM +0000, david eddy wrote: > I am wrestling to understand why this shifting works, assuming it doesn't > require > understanding of the FFT. Can anyone help?
We are doing arithmetic modulo 2^p-1 (say p=7 for simplicity), which means our operations are inherently circular -- if we touch bits >= p, it's just the same as folding them down below (ie. if you add 256, which is bit number 8=p+1, that's the same as adding 2, which is bit number 1). Given that squaring by FFT give us this kind of circular operation by default (it's a property of the FFT), and our only other operation is the subtraction of 2 (which is also circular, since it's also done mod 2^p-1), all our operations are indeed circular. But then it doesn't really matter how we store the number in memory; storing a0 a1 a2 a3 (or whatever, depending on how many bits we need) is exactly the same as storing a1 a2 a3 a0, a2 a3 a0 a1, or a3 a0 a1 a2. The operations are exactly the same, except that we have to remember how much we've shifted by when subtracting 2 (since that has to go on the right bits; subtracting 2 is certainly not the same as subtracting 4, 8, or 16), and we keep this shift all the way down the test. (The end result we test for, zero, is the same no matter what our shift is, of course.) /* Steinar */ -- Homepage: http://www.sesse.net/ _______________________________________________ Prime mailing list [email protected] http://hogranch.com/mailman/listinfo/prime
