## Other

drummers-lowrise

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

 Subscribe SortOldest firstNewest firstHighest rated posts first
Author Message
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)

____________ 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

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.

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