Mersenne Digest Tuesday, 19 May 1998 Volume 01 : Number 364 ---------------------------------------------------------------------- From: Jean-Luc Cooke Date: Mon, 18 May 1998 18:53:03 -0400 Subject: Mersenne: HOT DAMN! I've just tried the Fermat test with the new little bit of math Peter showed me. a^( [N+1]/2 ) mod N = -a, for any "a" and N is prime. and have 50% savings in time compared to the LL test! I used the very sophistacated "steamboat" counting system [ :) ] and the M(2203) LL test took about 10 steamboats in Java while the Fast Fermat test took only 5! This is great stuff. I am now convinced we should 3-PRP test all numbers before we go on to the LL tests. I've just tested the first 1,000 primes (n<) as x-values in M(x) = 2^x-1 and the only ones that passed as 3-PRP are Mersenne primes! Try it on my cheep little applet: http://www.engsoc.carleton.ca/~jlcooke/Numbers/GIMPS/ll.shtml I'll send you the source code if you wish to see what I've done. I didn't put in any documentation though so it may be rough. TTYL JLC Peter-Lawrence.Montgomery@cwi.nl wrote: > > Chuck W writes > > > I think the real question is, would the Fermat test ever say a number is > > "unlikely" to be prime when it is actually prime? The fermat test has to > > get us somewhere, hence we have to be able to eliminate exponents somehow. > > The real question is will the Fermat test give us any sort of consistent > > answers. > > The Fermat test will never reject true primes. > If Mp = 2^p - 1 is prime, then a^(Mp + 1) == a^2 (mod Mp) for all bases a. > > One way to get consistent answers is to run it on bases > a = 27 = 3^3 and a = 243 = 3^5. To test Mp, one Fermat tester repeatedly > squares 27 until he gets 27^(Mp + 1). If his final result is 27^2 = 729, > then Mp is a likely Mersenne prime, and an LL test can follow. > Another tester computes 243^(Mp + 1). Even if both testers use the same > program, they are putting different data through the FFT code. > When done, the two testers report the bottom bits of > > [27^(Mp + 1)]^5 and [243^(Mp + 1)]^3 > > to a central site. The outcomes should agree, since both > are computing (3^15)^(Mp + 1). > > [Actually one should use (Mp + 1)/2 rather than Mp as the exponent, > checking whether the outcome is -27 or -243.] - -- Jean-Luc Cooke Carleton University, Electrical Engineering There is a 90% chance that right at this moment I am doing Calculus. God damn Newton, damn him to hell! - ---------------------------------------------------------------------- Hyperactivity Unbounded http://www.engsoc.carleton.ca/~jlcooke - ---------------------------------------------------------------------- AOL-IM ID: JLinOTTAWA http://register.netscape.oscar.aol.com - ---------------------------------------------------------------------- ICQ# 4474419 http://www.mirabilis.com - ---------------------------------------------------------------------- Email addresses jlcooke@ottawa.com jlcooke@magma.ca jlcooke@magmacom.com jlcooke@engsoc.carleton.ca jlcooke@chat.carleton.ca - ---------------------------------------------------------------------- ------------------------------ From: Peter-Lawrence.Montgomery@cwi.nl Date: Tue, 19 May 1998 01:31:04 +0200 (MET DST) Subject: Re: Mersenne: Use Fermat First? An individual whose long signature many of us despise wrote: > I'm not clear why this is the case? So you're saying that > (1) a^( [Mp + 1]/2 ) mod Mp = -a ?? > > Thank you. If this is faster than > > (2) a^(Mp+1) mod Mp = 1 > > Than we should DEFINATLY use the Fermat test before the LL!!! I'm using > (2) and getting 33% fast CPU time. If I use (1) I'll get dramaticly > faster times still!!! Let E = (Mp+1)/2 = 2^(p-1). If Mp is prime, then ( a) a^(E-1) == (--) (mod Mp), (Mp) where the right side is the Jacobi or Legendre symbol a over Mp. The right side is +1 if a is a nonzero square mod Mp, 0 if Mp divides a, and -1 is a is a non-square mod Mp. From the quadratic reciprocity formula (see a number theory textbook), we know 3 is not a square mod Mp for Mp >= 7 since Mp == 7 (mod 12). Hence 3^(E-1) == -1 (mod Mp) whenever Mp is prime. Reducing the exponent from 2^p to 2^(p-1) saves only one squaring mod Mp, a negligible difference when p is several million. ------------------------------ From: George Woltman Date: Mon, 18 May 1998 20:25:53 -0400 Subject: Re: Mersenne: Use Fermat First? Hi all, At 05:48 PM 5/18/98 -0400, Jean-Luc Cooke wrote: >So I just fell back on the question that we should try 3,5,7, or what >ever x-PRP to test. Chris Nash and I are waiting for the PrimeNet/GIMPS >programmers/mathy-people to step in and clear this up. I'll answer as a GIMPS programmer - not as a mathy people. The Fermat test would be a fine way to screen exponents before a Lucas-Lehmer test is run *IF* it can be made to run significantly faster than an LL test. At present, the two tests take the same amount of time - so I use the definitive test rather than the very-very-often correct Fermat test. The Fermat test requires p squarings modulo 2^p-1. The LL test requires p squarings modulo 2^p-1 and p subtractions of 2. The subtractions of 2 cost nothing. So, the two algorithms have the same cost. Given that we are testing exponents near 5,000,000 now, even if you save a squaring, that's only a 1/5,000,000th improvement -- just not worth the bother. Best regards, George ------------------------------ From: Simon Burge Date: Tue, 19 May 1998 11:58:53 +1000 Subject: Re: Mersenne: Use Fermat First? On Mon, 18 May 1998 20:25:53 -0400 George Woltman wrote: > Hi all, > > At 05:48 PM 5/18/98 -0400, Jean-Luc Cooke wrote: > >So I just fell back on the question that we should try 3,5,7, or what > >ever x-PRP to test. Chris Nash and I are waiting for the PrimeNet/GIMPS > >programmers/mathy-people to step in and clear this up. > > I'll answer as a GIMPS programmer - not as a mathy people. > > The Fermat test would be a fine way to screen exponents before > a Lucas-Lehmer test is run *IF* it can be made to run significantly > faster than an LL test. At present, the two tests take the same > amount of time - so I use the definitive test rather than the > very-very-often correct Fermat test. > > The Fermat test requires p squarings modulo 2^p-1. > The LL test requires p squarings modulo 2^p-1 and p subtractions of 2. > > The subtractions of 2 cost nothing. So, the two algorithms have the same > cost. Given that we are testing exponents near 5,000,000 now, even if you > save a squaring, that's only a 1/5,000,000th improvement -- just > not worth the bother. I'll try and answer as a general programmer, who understands just a little about GIMPS programming and just a little about "mathy" stuff. I also don't know the exact algorithm for the Fermat test off the top of my head. If we don't need to subtract 2 each iteration, can we remain in frequency space all of the time, and thus save the FFT/IFFT each iteration? This would be a _HUGE_ saving. Maybe I should research this a little before opening my mouth? Simon. ------------------------------ From: Chris Nash Date: Tue, 19 May 1998 00:51:28 -0400 Subject: Re: Mersenne: Use Fermat First? Simon >If we don't need to subtract 2 each iteration, can we remain in >frequency space all of the time, and thus save the FFT/IFFT each >iteration? This would be a _HUGE_ saving. It would be wonderful if we could... as far as I understand it, we need to drop out of frequency space for accuracy reasons as well, confirming the low-order bits, which is why the subtract 2 is practically free. I'm still not clear where the mod M reduction is done. In frequency space or in integer space? Chris Nash ------------------------------ End of Mersenne Digest V1 #364 ******************************