4

I joined GIMPS for a while and have identified several composite numbers. For those numbers assigned to me for PRP tests, the estimated completion dates and the number of required iterations are always very accurate. How can the estimation be so good. If a small factor is found early, what does the program do? Does it continue with some other calculations or request a new number to work on?

A related question is here.

A list of work types is here.

modnar
  • 458
  • 1
    This is due to how the Lucas-Lehmer test works: it has to compute a certain sequence of integers and see if the last term is zero. There is no intermediate checking of small factors. – Wojowu Jan 14 '20 at 10:57
  • If you want to check a number for primality, it is nevertheless clever to start with trial division upto a reasonable limit before applying the primality test. This might save a lot of time. Imagine, you check a huge number a month long and later you discover a $5$ digit-factor. But as mentioned by Wojowu, a primality test (not only the Lucas-Lehmer-test , also for example the Miller-Rabin-test) usually does not involve trial division. This can of course be done parallel to the calculation or before, but the tests itself do not apply it. – Peter Jan 14 '20 at 11:01
  • The Mersenne numbers have a special structure and because of the restrictions of the prime factors, we can apply trial division to much larger limits than we could for arbitary numbers. – Peter Jan 14 '20 at 11:03
  • By the way, the Lucas Lehmer test , if successful, not only gives us a probable prime, but a proven prime ! This is the reason why most of the largest known primes are Mersenne primes followed by generalized Fermat primes. – Peter Jan 14 '20 at 11:06
  • 1
    They specifically say PRP people ... as in Robert Gerbicz PRP test. I say ask George woltman on the mersenne forum. –  Jan 14 '20 at 12:45

1 Answers1

3

The algorithm used by GIMPS is described at this link. First it checks for small factors (where small can mean as big as $2^{80}$). Then it runs Pollard's $P-1$ method to try and find factors of a special kind.

Only when a number fails these two tests is it sent to a volunteer like you for the Lucas-Lehmer or PRP stage. These primality tests are fixed-time algorithms that run to completion and deliver a YES or NO answer (or in the case of PRP, PROBABLY or NO). This is why the program always knows how much time it is going to need.

TonyK
  • 64,559
  • 1
    They specifically asked about Gerbicz PRP not LL... –  Jan 14 '20 at 12:46
  • @RoddyMacPhee: Thanks for pointing that out. I have edited my answer. – TonyK Jan 14 '20 at 13:12
  • PRP took over as the main testing branch as it was based on an observation of my ramblings about the $2x^2-1$ version of LL, and how $7=2(3)+1$ and so $97=2(4\cdot 3^2+4\cdot 3)+1$ etc. it's basically a 3-PRP with a changed exponent and end residue. it made it quicker to run. –  Jan 14 '20 at 13:21