Thankyou Steinar. It ain't "rocket science" but very pretty none the less. I'll check it out on 2^11-1 in Basic when I feel like some programming coming on:)
BTW "i.e." <> "e.g" David ---------------------------------------- > Date: Tue, 14 Nov 2006 12:04:06 +0100 > From: [EMAIL PROTECTED] > To: [email protected] > Subject: Re: [Prime] Shifting the residue > > 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 _________________________________________________________________ Be one of the first to try Windows Live Mail. http://ideas.live.com/programpage.aspx?versionId=5d21c51a-b161-4314-9b0e-4911fb2b2e6d _______________________________________________ Prime mailing list [email protected] http://hogranch.com/mailman/listinfo/prime
