Talk:Lucas–Lehmer primality test

there is a mistake in the article , it supposed to :
$s_{p-1}\equiv 0{\pmod {M_{p}}};$
not :
$s_{p-2}\equiv 0{\pmod {M_{p}}};$

—The preceding unsigned comment was added by 85.250.124.207 (talk • contribs) 07:26, 4 November 2005 (UTC).

I disagree. $M_{3}$ is prime and also $s_{1}\equiv 0{\pmod {M_{3}}}$. That is, $14\equiv 0{\pmod {7}}$. However, $s_{2}\ \not \equiv \ 0{\pmod {M_{3}}}$; equivalently, $194\ \not \equiv \ 0{\pmod {7}}$. Therefore I think the article is correct as is stands. Eric119 03:35, 5 November 2005 (UTC)

$s_{0}=4$, so is $s_{p-2}\equiv 0{\pmod {M_{p}}}$ and not $s_{p-1}\equiv 0{\pmod {M_{p}}}$.

Dumbing this down with an example?

I think it might help some people by giving an example of how the Lucas-Lehmer test can prove primality of say... 2^5-1, for instance. As the article stands, not many people without prior experience of advanced mathematical notation and terms, would be able to take anything useful from this.

Great idea. Dcoetzee 03:24, 10 May 2007 (UTC)

-Yeah I'd like to see this in simple English. Sorry for not knowing wiki markup and doing this officially. — Preceding unsigned comment added by 96.32.150.222 (talk) 00:22, 11 November 2012 (UTC)

A bit confused about high speed mod

I'm a bit confused about the high speed mod operation. The article gives this example:

916 mod 2⁵−1 = 1110010100 mod 2⁵−1

= 11100 + 10100 mod 25−1 
= 110000 mod 25−1 
= 1 + 10000 mod 25−1 
= 10001 mod 25−1 
= 10001 
= 17. 

However if I try it with 14 mod 7 I get this: 14 mod 2³−1

= 1110 mod 23−1 
= 1 + 110 mod 23−1 
= 111 mod 23−1 
= 7. 

Now I know that 7 mod 7 is 0, but how does the ggiven algo generate a zero ? Thanks —Preceding unsigned comment added by 149.173.6.50 (talk) 15:25, 20 November 2007 (UTC)

That's a good observation, actually - it's possible for the result to be exactly 2ⁿ−1, in which case you have to change it to zero. If it were any larger, you'd reduce it by doing another iteration. Dcoetzee 01:23, 21 November 2007 (UTC)

I think, there are little problems whit this reasoning. First of all, if the modulo operation gives us 0 as a result, then this leads to the next: We arrive at 0, then we square it, it becomes 0 again, then we substract 2, then it is -2. Now, due to the [[1]] article, we can define the modulo of -2, so:

-2 = M_p-2 (mod M_p)

but this computation, namely, that we add M_p to the resutl to get a positive integer is much different from the algorithm described in this article.

Morover, this article states:

"since s × s will never exceed M² < 2^2p"

This statement eables, that the value after the squaring operation be M2^2p, and thus, the value before the squaring operation be M². So if the resutlt after the modulo operation is M_p, then we dont't need to convert it to 0.

So it would be needed to clarify this article on my opinion.

Cleaning up the "sufficient" part of the proof

Is there any reason why we write Zq(sqrt(3)) out explicitly, instead of just calling it an extension field? What's more, if sqrt(3) is in the field, there is no extension and we should just use Zq, whose multiplicative group has order q-1; otherwise, it's an extension field and its multiplicative group has order q^2-1. I suppose you could "extend" it, to get a group with order q(q-1), but it's not clearer that way, at least not to a mathematician. —Preceding unsigned comment added by 64.142.4.173 (talk) 18:15, 27 June 2009 (UTC)

Removed article text

I removed "They consider it valuable for finding very large primes because Mersenne numbers are considered somewhat more likely to be prime than randomly chosen odd integers of the same order of magnitude," because it's simply not true. There have been exactly 47 Mersenne primes, and the first 40 are known to have none in between - out of 1.3 million or so possibilities checked. Your average odd integer has a way higher probability of being prime, hence why we only use the Lucas-Lehmer test to look for the biggest ones, not for large amounts of primes to use for other purposes. —Preceding unsigned comment added by 68.147.216.149 (talk) 04:16, 10 December 2010 (UTC)

I agree it should be removed but don't agree with the stated reason. The chance of a random integer n being prime is 1/log(n). If n is odd then it doubles to 2/log(n). A Mersenne number with prime exponent has a better chance because 2^p-1 has no prime factors below 2p. If random odd integers of similar size as the Mersenne numbers were tested then the expected number of primes up to the 40th Mersenne prime would only have been 9. However, this is not the reason for GIMPS to test Mersenne numbers. PrimeHunter (talk) 14:06, 10 December 2010 (UTC)

Historic (first) use on M257: no prime

Lehmer and his wife Emma "bought a Monroe electric desk calculator on the instalment plan, but could only run it in the day as it blinked the lights in their house and the one next door. … which Lehmer spent some 700 hours in testing c1932"[2].

"In 1922, Monroe introduced the electric version of its Model K non-printing calculating machine. It had a large external driving motor." according to [3]

[4]: "932 D. H. Lehmer develops an improved version of Lucas’ test and shows that M257 is not prime, taking two hours a day for a year."

Finest source, worth looking at [5]: "Emma and Dick moved to Lehigh University in 1932, … The work by the Lehmers was funded by a Penrose Scholarship granted to Vandiver by the American Philosophical Society. Part of the money went to renting a 10-10-20 electric Monroe machine xnumber/pic_monroe_electr.htm at a cost of US$25 per month." – The pictures shows a somewhat smaller model K with just 8-8-16 digits. I can well imagine that the bigger model’s motor made the lights flicker at meager 110 Volt supply. – Fritz Jörn (talk) 08:02, 16 February 2013 (UTC)

Proof of correctness, Necessity

Hi, I think mine is simpler

$(1+{\sqrt {3}})^{2}=2(2+{\sqrt {3}})$ $2^{2^{q-1}}(2+{\sqrt {3}})^{2^{q-1}}=(1+{\sqrt {3}})^{M_{q}+1}\equiv (1+{\sqrt {3}})(1+{\sqrt {3}}^{M_{q}})\equiv (1+{\sqrt {3}})(1-{\sqrt {3}})=-2$ $2^{2^{q-1}}=2^{\frac {M_{q}+1}{2}}=2$ thus $(2+{\sqrt {3}})^{2^{q-1}}=w^{\frac {M_{q}+1}{2}}\equiv -1{\pmod {M_{q}}}$