View Single Post
Old 2005-12-06, 20:58   #5
smh
 
smh's Avatar
 
"Sander"
Oct 2002
52.345322,5.52471

29×41 Posts
Default

Let me quote about the LL test from www.mersenne.org/math.htm

Quote:
The Lucas-Lehmer primality test is remarkably simple. It states that for P > 2, 2P-1 is prime if and only if Sp-2 is zero in this sequence: S0 = 4, SN = (SN-12 - 2) mod (2P-1). For example, to prove 27 - 1 is prime:
Code:
		S0 = 4
		S1 = (4 * 4 - 2)     mod 127 = 14
		S2 = (14 * 14 - 2)   mod 127 = 67
		S3 = (67 * 67 - 2)   mod 127 = 42
		S4 = (42 * 42 - 2)   mod 127 = 111
		S5 = (111 * 111 - 2) mod 127 = 0
Now how could we start at S5? We don't know the answer. In fact, if we did, we wouldn't have to run the test because the only thing we're interested in is the answer to the very last step in the (long) sequence. If it turns out to be 0, the number is prime. Any other value and the number is composite.

Last fiddled with by smh on 2005-12-06 at 21:02
smh is offline   Reply With Quote