View source for Talk:Lucas-Lehmer test

== M<small><sub>23,209</sub></small> &nbsp; is &nbsp; 36 &nbsp; CPU hours ≡ 1979 ==
Welcome to 1979!
:Yeah.  I know. :-) --[[User:Short Circuit|Short Circuit]] 07:55, 21 February 2008 (MST)

==List of known Mersenne primes==
The table below lists all known Mersenne primes:
{| class="wikitable"
|-
! #
! ''n''
! ''M''<sub>''n''</sub>
! Digits in ''M''<sub>''n''</sub>
! Date of discovery
! Discoverer
|-
| align="right" | 1
| align="right" | 2
| align="right" | 3 (number)|3
| align="right" | 1
| ''ancient''
| ''ancient''
|-
| align="right" | 2
| align="right" | 3
| align="right" | 7 (number)|7
| align="right" | 1
| ''ancient''
| ''ancient''
|-
| align="right" | 3
| align="right" | 5
| align="right" | 31 (number)|31
| align="right" | 2
| ''ancient''
| ''ancient''
|-
| align="right" | 4
| align="right" | 7
| align="right" | 127 (number)|127
| align="right" | 3
| ''ancient''
| ''ancient''
|-
| align="right" | 5
| align="right" | 13
| align="right" | 8191
| align="right" | 4
| 1456
| ''anonymous'' [http://primes.utm.edu/mersenne/]
|-
| align="right" | 6
| align="right" | 17
| align="right" | 131071
| align="right" | 6
| 1588
| Pietro Cataldi|Cataldi
|-
| align="right" | 7
| align="right" | 19
| align="right" | 524287
| align="right" | 6
| 1588
| Pietro Cataldi|Cataldi
|-
| align="right" | 8
| align="right" | 31
| align="right" | 2147483647
| align="right" | 10
| 1772
| Leonhard Euler|Euler
|-
| align="right" | 9
| align="right" | 61
| align="right" | 2305843009213693951
| align="right" | 19
| 1883
| Ivan Mikheevich Pervushin|Pervushin
|-
| align="right" | 10
| align="right" | 89
| align="right" | 618970019…449562111
| align="right" | 27
| 1911
| R. E. Powers|Powers 
|-
| align="right" | 11
| align="right" | 107
| align="right" | 162259276…010288127
| align="right" | 33
| 1914
| R. E. Powers|Powers[http://primes.utm.edu/notes/fauquem.html]
|-
| align="right" | 12
| align="right" | 127
| align="right" | 170141183…884105727
| align="right" | 39
| 1876
| Edouard Lucas|Lucas
|-
| align="right" | 13
| align="right" | 521
| align="right" | 686479766…115057151
| align="right" | 157
| January 30 1952
| Raphael M. Robinson|Robinson
|-
| align="right" | 14
| align="right" | 607
| align="right" | 531137992…031728127
| align="right" | 183
| January 30 1952
| Raphael M. Robinson|Robinson
|-
| align="right" | 15
| align="right" | 1,279
| align="right" | 104079321…168729087
| align="right" | 386
| June 25 1952
| Raphael M. Robinson|Robinson
|-
| align="right" | 16
| align="right" | 2,203
| align="right" | 147597991…697771007
| align="right" | 664
| October 7 1952
| Raphael M. Robinson|Robinson
|-
| align="right" | 17
| align="right" | 2,281
| align="right" | 446087557…132836351
| align="right" | 687
| October 9 1952
| Raphael M. Robinson|Robinson
|-
| align="right" | 18
| align="right" | 3,217
| align="right" | 259117086…909315071
| align="right" | 969
| September 8 1957
| Hans Riesel|Riesel
|-
| align="right" | 19
| align="right" | 4,253
| align="right" | 190797007…350484991
| align="right" | 1,281
| November 3 1961
| Alexander Hurwitz|Hurwitz
|-
| align="right" | 20
| align="right" | 4,423
| align="right" | 285542542…608580607
| align="right" | 1,332
| November 3 1961
| Alexander Hurwitz|Hurwitz
|-
| align="right" | 21
| align="right" | 9,689
| align="right" | 478220278…225754111
| align="right" | 2,917
| May 11 1963
| Donald B. Gillies|Gillies
|-
| align="right" | 22
| align="right" | 9,941
| align="right" | 346088282…789463551
| align="right" | 2,993
| May 16 1963
| Donald B. Gillies|Gillies
|-
| align="right" | 23
| align="right" | 11,213
| align="right" | 281411201…696392191
| align="right" | 3,376
| June 2 1963
| Donald B. Gillies|Gillies
|-
| align="right" | 24
| align="right" | 19,937
| align="right" | 431542479…968041471
| align="right" | 6,002
| March 4 1971
| Bryant Tuckerman|Tuckerman
|-
| align="right" | 25
| align="right" | 21,701
| align="right" | 448679166…511882751
| align="right" | 6,533
| October 30 1978
| Landon Curt Noll|Noll & Laura Nickel|Nickel
|-
| align="right" | 26
| align="right" | 23,209
| align="right" | 402874115…779264511
| align="right" | 6,987
| February 9 1979
| Landon Curt Noll|Noll
|-
| align="right" | 27
| align="right" | 44,497
| align="right" | 854509824…011228671
| align="right" | 13,395
| April 8 1979
| Harry Nelson|Nelson & David Slowinski|Slowinski
|-
| align="right" | 28
| align="right" | 86,243
| align="right" | 536927995…433438207
| align="right" | 25,962
| September 25 1982
| David Slowinski|Slowinski
|-
| align="right" | 29
| align="right" | 110,503
| align="right" | 521928313…465515007
| align="right" | 33,265
| January 28 1988
| Walt Colquitt|Colquitt & Luke Welsh|Welsh
|-
| align="right" | 30
| align="right" | 132,049
| align="right" | 512740276…730061311
| align="right" | 39,751
| September 19 1983[http://www.isthe.com/chongo/tech/math/prime/mersenne.html#largest]
| David Slowinski|Slowinski
|-
| align="right" | 31
| align="right" | 216,091
| align="right" | 746093103…815528447
| align="right" | 65,050
| September 1 1985[http://www.isthe.com/chongo/tech/math/prime/mersenne.html#largest]
| David Slowinski|Slowinski
|-
| align="right" | 32
| align="right" | 756,839
| align="right" | 174135906…544677887
| align="right" | 227,832
| February 19 1992
| David Slowinski|Slowinski & Paul Gage|Gage on Harwell Lab Cray-2 [http://primes.utm.edu/notes/756839.html]
|-
| align="right" | 33
| align="right" | 859,433
| align="right" | 129498125…500142591
| align="right" | 258,716
| January 4 1994 [http://www.math.unicaen.fr/~reyssat/largest.html]
| David Slowinski|Slowinski & Paul Gage|Gage
|-
| align="right" | 34
| align="right" | 1,257,787
| align="right" | 412245773…089366527
| align="right" | 378,632
| September 3 1996
| David Slowinski|Slowinski & Paul Gage|Gage [http://primes.utm.edu/notes/1257787.html]
|-
| align="right" | 35
| align="right" | 1,398,269
| align="right" | 814717564…451315711
| align="right" | 420,921
| November 13 1996
| Great Internet Mersenne Prime Search|GIMPS / Joel Armengaud [http://www.mersenne.org/1398269.htm]
|-
| align="right" | 36
| align="right" | 2,976,221
| align="right" | 623340076…729201151
| align="right" | 895,932
| August 24 1997
| Great Internet Mersenne Prime Search|GIMPS / Gordon Spence [http://www.mersenne.org/2976221.htm]
|-
| align="right" | 37
| align="right" | 3,021,377
| align="right" | 127411683…024694271
| align="right" | 909,526
| January 27 1998
| Great Internet Mersenne Prime Search|GIMPS / Roland Clarkson [http://www.mersenne.org/3021377.htm]
|-
| align="right" | 38
| align="right" | 6,972,593
| align="right" | 437075744…924193791
| align="right" | 2,098,960
| June 1 1999
| Great Internet Mersenne Prime Search|GIMPS / Nayan Hajratwala [http://www.mersenne.org/6972593.htm]
|-
| align="right" | 39
| align="right" | 13,466,917
| align="right" | 924947738…256259071
| align="right" | 4,053,946
| November 14 2001
| Great Internet Mersenne Prime Search|GIMPS / Michael Cameron [http://www.mersenne.org/13466917.htm]
|-
| align="right" | 40<sup>*</sup>
| align="right" | 20,996,011
| align="right" | 125976895…855682047
| align="right" | 6,320,430
| November 17 2003
| Great Internet Mersenne Prime Search|GIMPS / Michael Shafer [http://www.mersenne.org/20996011.htm]
|-
| align="right" | 41<sup>*</sup>
| align="right" | 24,036,583
| align="right" | 299410429…733969407
| align="right" | 7,235,733
| May 15 2004
| Great Internet Mersenne Prime Search|GIMPS / Josh Findley [http://www.mersenne.org/24036583.htm]
|-
| align="right" | 42<sup>*</sup>
| align="right" | 25,964,951
| align="right" | 122164630…577077247
| align="right" | 7,816,230
| February 18 2005
| Great Internet Mersenne Prime Search|GIMPS / Martin Nowak [http://www.mersenne.org/25964951.htm]
|-
| align="right" | 43<sup>*</sup>
| align="right" | 30,402,457
| align="right" | 315416475…652943871
| align="right" | 9,152,052
| December 15 2005
| Great Internet Mersenne Prime Search|GIMPS / Curtis Cooper (mathematician)|Curtis Cooper & Steven Boone [http://www.mersenne.org/30402457.htm]
|-
| align="right" | 44<sup>*</sup>
| align="right" | 32,582,657
| align="right" | 124575026…053967871
| align="right" | 9,808,358
| September 4 2006
| Great Internet Mersenne Prime Search|GIMPS / Curtis Cooper (mathematician)|Curtis Cooper & Steven Boone [http://www.mersenne.org/32582657.htm]
|}


:The 45th and 46th Mersenne primes have been discovered, is the intention to keep this table up to date? --[[User:Lupus|Lupus]] 17:24, 2 December 2008 (UTC)

:: The above list seems to be copied &nbsp; ''in toto'' &nbsp; from the updated &nbsp; Wikipedia site: 
                  <big> https://en.wikipedia.org/wiki/Mersenne_prime#List_of_known_Mersenne_primes </big>
:: The above Wikipedia site now has a list of &nbsp; '''51''' &nbsp; Mersenne primes. &nbsp; &nbsp; -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 19:57, 7 May 2019 (UTC)

== Java precision ==
The Java version is still limited by types. Integer.parseInt(args[0]) limits p to 2147483647. Also the fact that isMersennePrime takes an int limits it there too. For full arbitrary precision every int needs to be a BigInteger or BigDecimal and a square root method will need to be created for them. The limitation is OK I think (I don't think we'll be getting up to 2<sup>2147483647</sup> - 1 anytime soon), but the claim "any arbitrary prime" is false because of the use of ints. --[[User:Mwn3d|Mwn3d]] 07:45, 21 February 2008 (MST)


== Speeding things up ==
The main loop in Lucas-Lehmer is doing (n*n) mod M where M=2^p-1, and p > 1. '''But we can do it without division'''.

<lang>We compute the remainder of a division by M. Now, intuitively, dividing by 2^p-1 is almost
like dividing by 2^p, except the latter is much faster since it's a shift.
Let's compute how much the two divisions differ.

We will call S = n*n. Notice that since the remainder mod M is computed again and again, the value of n must be < M at
the beginning of a loop, that is at most 2^p-2, thus S = n*n <= 2^(2*p) - 4*2^p + 4 = 2^p * (2^p - 2) + 4 - 2*2^p

When dividing S by M, you get quotient q1 and remainder r1 with S = q1*M + r1 and 0 <= r1 < M
When dividing S by M+1, you get likewise S = q2*(M+1) + r2 and 0 <= r2 <= M
In the latter, we divide by a larger number, so the quotient must be less, or maybe equal, that is, q2 <= q1.

Subtract the two equalities, giving
0 = (q2 - q1)*M + q2 + r2 - r1
(q1 - q2)*M = q2 + r2 - r1

Since S =  2^p * (2^p - 2) + 4 - 2*2^p
        <= 2^p * (2^p - 2),
then the quotient q2 is less than 2^p - 2 (remember, when computing q2, we divide by M+1 = 2^p).

Now, 0 <= q2 <= 2^p - 2
     0 <= r2 <= 2^p - 1
     0 <= r1 <= 2^p - 2
Thus the right hand side is >= 0, and <= 2*2^p - 3.
The left hand side is a multiple of M = 2^p - 1.

Therefore, this multiple must be 0*M or 1*M, certainly not 2*M = 2*2^p - 2,
which would be > 2*2^p - 3, and not any other higher multiple would do.
So we have proved that q1 - q2 = 0 or 1.

This means that division by 2^p is almost equivalent (regarding the quotient)
to dividing by 2^p-1: it's the same quotient, or maybe too short by 1.

Now, the remainder S mod M.
We start with a quotient q = S div 2^p, or simply q = S >> p (right shift).
The remainder is S - q*M = S - q*(2^p - 1) = S - q*2^p + q, and the multiplication by 2^p is a left shift.
And this remainder may be a bit too large, if our quotient is a bit too small (by one): in this case we must subtract M.

So, in pseudo-code, we are done if we do:

    S = n*n
    q = S >> p
    r = S - (q << p) + q
    if r >= M then r = r - M

We can go a bit further: taking S >> p then q << p is simply keeping the higher bits of S.
But then we subtract these higher bits from S, so we only keep the lower bits,
that is we do (S & mask), and this mask is simply M ! (remember, M = 2^p - 1, a bit mask of p bits equal to "1")

The pseudo-code can thus be written

    S = n*n
    r = (S & M) + (S >> p)
    if r >= M then r = r - M

And we have computed a remainder mod M without any division, only a few addition/subtraction/shift/bitwise-and,
which will be much faster (each has a linear time complexity).

How much faster ? For exponents between 1 and 2000, in Python, the job is done 2.87 times as fast.
For exponents between 1 and 5000, it's 3.42 times as fast. And it gets better and better, since the comlexity is lower.
</lang>
[[User:Arbautjc|Arbautjc]] ([[User talk:Arbautjc|talk]]) 22:04, 15 November 2013 (UTC)


May 2015 - fixed small bugs in both Python implementations. In the first, execution failed (Python 3) without a cast to int in the test. In the second, there was a typo - an 'r' should have been 's'.

: Timing for some solutions for 2..11213:
{| class="wikitable"
|-
! Time (s)
! Solution
|-
| 871.2
| Python without optimizations
|-
| 314.7
| Python with optimizations
|-
| 124.7
| Perl Math::GMP without optimizations
|-
| 106.9
| Pari/GP 2.8.0
|-
| 61.8
| Perl Math::GMP with optimization
|-
| 33.0
| Python using gmpy2 (skipping non-primes)
|-
| 14.2
| C/GMP with even more optimizations
|-
| 13.3
| Perl Math::Prime::Util::GMP (source of C/GMP code)
|}
[[User:Danaj|Danaj]] ([[User talk:Danaj|talk]]) 19:49, 9 May 2015 (UTC)

Rust solution for 2..11213 -> 8.6 s

Pari/GP solution for 2..11213 -> 2.835 s --[[User:Nebulus|Nebulus]] ([[User talk:Nebulus|talk]]) 05:21, 22 February 2023 (UTC)