# Can my Home PC Handle the Lucas-Lehmer Test by Itself? (or Do I Need GIMPS)

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?

• 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. – Winther Jul 10 at 19:39
• 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 – reuns Jul 10 at 19:49
• For a short proof of LLT you can look there – reuns Jul 10 at 19:55
• @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. – samuelbowditch Jul 10 at 20:09

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"));

• you can do mod mp with shifts and adds. – Roddy MacPhee Jul 12 at 1:25
• 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) – reuns Jul 12 at 20:01
• 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) – reuns Jul 12 at 20:21
• I only know that, because I once made a thread about fast versions of LL on the GIMPS forum. – Roddy MacPhee Jul 12 at 20:23
• 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. – Roddy MacPhee Jul 12 at 20:48

$$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.

• 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. – samuelbowditch Jul 10 at 19:16
• For integers, you need not set a precision, the only problem can be the memory. – Peter Jul 10 at 19:17
• Oh, I did not know that. Thank you again. – samuelbowditch Jul 10 at 19:18
• 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. – Gottfried Helms Jul 11 at 10:23
• you can limit the residue by mapping to equivalent residues saving bits on the squaring. – Roddy MacPhee Jul 12 at 23:15