3
$\begingroup$

Last year, the largest Mersenne prime $2^{82,589,933}$ that we now know of was discovered. It contains almost $25,000,000$ digits if expanded out. I do not understand much how GIMPS operates, other than it makes use of the Lucas-Lehmer test algorithm.

My question might be naive, but I ask it anyway: On a PC with 8GB of RAM, am I capable of running the Lucas-Lehmer test on a Mersenne number $M_{p}$ with a prime $p$ of my choice? In theory, I certainly could recursively compute the $(n-1)st$ term of the underlying extended Lucas sequence sequence that GIMPS uses and attempt to divide my chosen $M_{p}$ into it. But can little computers like mine handle such large numbers?

$\endgroup$
  • 4
    $\begingroup$ Read the section "Details on the Discovery and Verification" on mersenne.org/primes/press/M82589933.html . You should be able to check it on your computer, but even with the most optimal implementation of the test it will likely require a week or more worth of computing to complete on a modern CPU. $\endgroup$ – Winther Jul 10 at 19:39
  • 5
    $\begingroup$ At first GIMPS is just an implementation of large numbers, LLT (and FFT multiplication of integers) plus a server telling you a list of unchecked or to be verified $p$. With pari-gp you can implement LLT-FFT in a few lines $\endgroup$ – reuns Jul 10 at 19:49
  • 2
    $\begingroup$ For a short proof of LLT you can look there $\endgroup$ – reuns Jul 10 at 19:55
  • $\begingroup$ @reuns Would you happen to have that few lines of code? I am not very experienced with PARI/GP but would like to get better at it, Many thanks. $\endgroup$ – samuelbowditch Jul 10 at 20:09
5
$\begingroup$

LLT implementation in Pari/gp

    p = 19937; Mp = 2^p-1; x = 4; 

    moduloM(p,n) = { a= shift(n,-p); b = n-shift(a,p); r = b+a; };
    for(n=1, p-2, x = moduloM(p,moduloM(p,x^2-2))); 

    /* slow version :  
       x = Mod(4,Mp); for(n=1, p-2, x = x^2-2); */

    if(x == Mp, print("2^",p,"-1 is prime"), print("2^",p,"-1 is NOT PRIME")); 
$\endgroup$
  • 1
    $\begingroup$ you can do mod mp with shifts and adds. $\endgroup$ – Roddy MacPhee Jul 12 at 1:25
  • 1
    $\begingroup$ I replaced Mod(x^2-2,Mp) by a shift & add and it is much faster now, 2 seconds to check $2^{19937}-1$ is prime, so I guess it uses fft multiplication (in the doc they say they use gmp whose doc suggests fft multiplication is automatic for large numbers) $\endgroup$ – reuns Jul 12 at 20:01
  • $\begingroup$ I will need 6 hours to check $M34 = 2^{1257787}-1$ and adding default("parisizemax", 400000000) to the code we can check the largest Mersenne prime $2^{82589933}-1$ for which it will take 955 days (for such large primes GIMPS probably stores intermediate values on its server) $\endgroup$ – reuns Jul 12 at 20:21
  • $\begingroup$ I only know that, because I once made a thread about fast versions of LL on the GIMPS forum. $\endgroup$ – Roddy MacPhee Jul 12 at 20:23
  • $\begingroup$ You can also rip off the last p bits of your value. Just mod by $2^p$ and you can use 3,p as your iteration count, no $p-2$ required. $\endgroup$ – Roddy MacPhee Jul 12 at 20:48
3
$\begingroup$

$25$ million digits is large but within reach of some number theory tools like pari/gp or maple.

So, in principle, you can check such a number with a single normal computer.

Of course, it will take long until the number is checked.

Note that the calculations that have to be done do not exceed the $50$ million digits mark.

$\endgroup$
  • $\begingroup$ Thank you. I have used PARI/GP for other things but when I try to set the precision too high, such as when working with long decimals of extremely small numbers, it gives me error messages. I guess I'm presuming I'll have the same problem with very large numbers too. $\endgroup$ – samuelbowditch Jul 10 at 19:16
  • 2
    $\begingroup$ For integers, you need not set a precision, the only problem can be the memory. $\endgroup$ – Peter Jul 10 at 19:17
  • $\begingroup$ Oh, I did not know that. Thank you again. $\endgroup$ – samuelbowditch Jul 10 at 19:18
  • 1
    $\begingroup$ For long integers problems I propose to use the 64-bit-processor-version of Pari/GP. Often much faster and more efficiently using memory than the standard version for 32-bit processors, it seems to me. $\endgroup$ – Gottfried Helms Jul 11 at 10:23
  • $\begingroup$ you can limit the residue by mapping to equivalent residues saving bits on the squaring. $\endgroup$ – Roddy MacPhee Jul 12 at 23:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.