PrimeGrid
Please visit donation page to help the project cover running costs for this month

Toggle Menu

Join PrimeGrid

Returning Participants

Community

Leader Boards

Results

Other

drummers-lowrise

Advanced search

Message boards : Cullen/Woodall prime search : Lucas-Lehmer algorithm - a problem

Author Message
Profile Jim_Clark
Avatar
Send message
Joined: 7 Sep 07
Posts: 42
ID: 11907
Credit: 286,805
RAC: 0
321 LLR Bronze: Earned 10,000 credits (37,581)Cullen LLR Bronze: Earned 10,000 credits (20,534)PSP LLR Bronze: Earned 10,000 credits (78,408)Woodall LLR Bronze: Earned 10,000 credits (66,612)Cullen/Woodall Sieve (suspended) Bronze: Earned 10,000 credits (22,193)PPS Sieve Bronze: Earned 10,000 credits (25,365)
Message 7015 - Posted: 20 Sep 2007 | 3:49:09 UTC

I am trying to understand the generalized Lucas-Lehmer algorithm, but I have encountered a problem.

According to Wikipedia, this is how the eneralized Lucas-Lehmer test for primality works:

"In computational number theory, the Lucas-Lehmer test is a primality test for a natural number n; it requires that the prime factors of n - 1 be already known.

If for every prime factor q of n - 1 there exists an integer a less than n and greater than 1 such that firstly
a^(n-1) = 1 (mod n)
and then
a^((n-1)/q} = 1 (mod n)
then n is prime. If no such number a can be found, then n is composite number."

Let's see how this works for the case n = 11, which we know is prime. In this case, the prime

factors of n - 1 are q = 2 and 5. For q = 2, the values of a which satisfy the two conditions
a^(n-1) = 1 (mod n)
and
a^((n-1)/q} = 1 (mod n)
are a = 3, 4, 5, and 9.
For q = 5, the only value of a which satisfy these two conditions is a = 10. This demonstrates

that sometimes (at least) one value of a will not suffice for all factors of n - 1. So, in general, we need to find a value a for each factor.

Now, let's see how this works for the case n = 57, which we know is composite (57 = 3 * 19).

The prime factors of n - 1 are 2 and 7 in this case. The values a = 20 and 37 satisfy the two

conditions
a^(n-1) = 1 (mod n)
and
a^((n-1)/q} = 1 (mod n)
for both factors q = 2 and 7. Therefore 57 is prime? What is wrong?

Here are the arithmetic details:

a = 20, q = 2:
20^56 = 1 (mod 57) because
56 = 8 + 16 + 32
20^2 = 1 (mod 57)
20^4 = 1 (mod 57)
20^8 = 1 (mod 57)
20^16 = 1 (mod 57)
20^32 = 1 (mod 57)
20^56 = 20^8 * 20^16 * 20^32 = 1 (mod 57)
and
20^(56/2} = 1 (mod 57) because
56/2 = 28 = 4 + 8 + 16
20^28 = 20^4 * 20^8 * 20^16 = 1 (mod 57)

a = 20, q = 7:
20^56 = 1 (mod 57)
and
20^(56/7} = 1 (mod 57) because
56/7 = 8
20^8 = 1 (mod 57)

a = 37, q = 2:
37^56 = 1 (mod 57) because
56 = 8 + 16 + 32
37^2 = 1 (mod 57)
37^4 = 1 (mod 57)
37^8 = 1 (mod 57)
37^16 = 1 (mod 57)
37^32 = 1 (mod 57)
37^56 = 37^8 * 37^16 * 37^32 = 1 (mod 57)
and
37^(56/2} = 1 (mod 57) because
56/2 = 28 = 4 + 8 + 16
37^28 = 37^4 * 37^8 * 37^16 = 1 (mod 57)

a = 37, q = 7:
37^56 = 1 (mod 57)
and
37^(56/7} = 1 (mod 57) because
56/7 = 8
37^8 = 1 (mod 57)

____________

Ben RhodesProject donor
Send message
Joined: 8 May 06
Posts: 33
ID: 2826
Credit: 47,694,214
RAC: 1,457
321 LLR Ruby: Earned 2,000,000 credits (2,021,875)Cullen LLR Ruby: Earned 2,000,000 credits (2,006,720)ESP LLR Ruby: Earned 2,000,000 credits (2,002,720)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,795,334)PPS LLR Ruby: Earned 2,000,000 credits (2,121,680)PSP LLR Ruby: Earned 2,000,000 credits (2,064,051)SoB LLR Ruby: Earned 2,000,000 credits (2,055,088)SR5 LLR Ruby: Earned 2,000,000 credits (2,029,966)SGS LLR Ruby: Earned 2,000,000 credits (2,012,584)TPS LLR (retired) Silver: Earned 100,000 credits (111,894)TRP LLR Ruby: Earned 2,000,000 credits (2,028,168)Woodall LLR Ruby: Earned 2,000,000 credits (2,005,903)Cullen/Woodall Sieve (suspended) Gold: Earned 500,000 credits (803,773)Generalized Cullen/Woodall Sieve Turquoise: Earned 5,000,000 credits (5,058,258)PPS Sieve Turquoise: Earned 5,000,000 credits (5,025,598)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Ruby: Earned 2,000,000 credits (4,110,401)TRP Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,009,196)AP 26/27 Ruby: Earned 2,000,000 credits (2,355,811)GFN Ruby: Earned 2,000,000 credits (2,031,737)
Message 7019 - Posted: 20 Sep 2007 | 15:47:51 UTC

I believe your statement of the test should read "... and then a^((n-1)/q) <> 1 (mod n) then n is prime...". With <> there 11 is still prime and I assume that would make 57 composite as well.

Here is the link I used:
http://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_test

Profile Jim_Clark
Avatar
Send message
Joined: 7 Sep 07
Posts: 42
ID: 11907
Credit: 286,805
RAC: 0
321 LLR Bronze: Earned 10,000 credits (37,581)Cullen LLR Bronze: Earned 10,000 credits (20,534)PSP LLR Bronze: Earned 10,000 credits (78,408)Woodall LLR Bronze: Earned 10,000 credits (66,612)Cullen/Woodall Sieve (suspended) Bronze: Earned 10,000 credits (22,193)PPS Sieve Bronze: Earned 10,000 credits (25,365)
Message 7023 - Posted: 20 Sep 2007 | 19:18:59 UTC - in response to Message 7019.

I believe your statement of the test should read "... and then a^((n-1)/q) <> 1 (mod n) then n is prime...". With <> there 11 is still prime and I assume that would make 57 composite as well.

Here is the link I used:
http://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_test


Thanks. You're right -- I misread the Wikipedia article. I'll try it again with MathCad and my Pascal library.

Profile Jim_Clark
Avatar
Send message
Joined: 7 Sep 07
Posts: 42
ID: 11907
Credit: 286,805
RAC: 0
321 LLR Bronze: Earned 10,000 credits (37,581)Cullen LLR Bronze: Earned 10,000 credits (20,534)PSP LLR Bronze: Earned 10,000 credits (78,408)Woodall LLR Bronze: Earned 10,000 credits (66,612)Cullen/Woodall Sieve (suspended) Bronze: Earned 10,000 credits (22,193)PPS Sieve Bronze: Earned 10,000 credits (25,365)
Message 7026 - Posted: 21 Sep 2007 | 2:08:00 UTC - in response to Message 7025.

I believe your statement of the test should read "... and then a^((n-1)/q) <> 1 (mod n) then n is prime...". With <> there 11 is still prime and I assume that would make 57 composite as well.

Here is the link I used:
http://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_test


Thanks. You're right -- I misread the Wikipedia article. I'll try it again with MathCad and my Pascal library.



When I corrected the algorithm, it agreed with another seive-based primality test for all primes less than 20000.
____________

Message boards : Cullen/Woodall prime search : Lucas-Lehmer algorithm - a problem

[Return to PrimeGrid main page]
DNS Powered by DNSEXIT.COM
Copyright © 2005 - 2019 Rytis Slatkevičius (contact) and PrimeGrid community. Server load 0.79, 0.94, 0.98
Generated 22 Aug 2019 | 15:56:32 UTC