View Single Post
Old 2019-07-15, 16:04   #3
kriesel's Avatar
Mar 2017
US midwest

129716 Posts
Default Background

The purpose of this post is to describe a shared foundation. Posting claims counter to what's here may indicate someone is an unaware novice, or is a troll. (Once I'm done weeding out my errors, with some help from others, that is.) This necessarily covers some points and leaves out much other material; whole books have been written about individual aspects, such as factorization. It's probably a good idea to read and then maybe return and resume here.
  1. "Natural numbers" are the counting numbers 1, 2, 3, ...
  2. Expression of math operations here follow usual conventions and so are indicated as follows: addition +, subtraction -, division /, multiplication * or implied (as in the expression 2 k p = 2 * k * p), exponentiation of a to the b power ab, square root sqrt(), modulo a mod b, equal =, less than or equal <=.
  3. I use here n, a, b, f or k for natural numbers that may be composite or prime, but p for primes. Occasionally a hopefully helpful subscript is attached.
  4. Natural numbers are either prime (having no natural numbers greater than one but smaller than themselves as exact integer divisors), or composite with factor(s) greater than one and less than the composite number. Five is an example of a prime. Six is an example of a composite: 6 = 2 * 3.
  5. Finding and verifying a single nontrivial factor (a natural number 1 < f < n) of a natural number n proves it is composite, not prime. By definition.
  6. One is not considered a prime, but a more special case.
  7. Smallest possible factor candidates are more likely to be factors than larger candidates. Two divides half the natural numbers, 3 a third, 5 1/5, f 1/f. So it's more efficient to search for factors with the smallest potential factors first.
  8. The largest possible smallest prime factor of a natural number is, the largest natural number no greater than the square root of the number. fmax <= sqrt(n)
  9. To search for factors of a number, it's sufficient to check only the primes below the square root of the number. Composite numbers can be skipped as potential factors, since their prime factors will divide any number they would, and some the composites won't. For example, 4 = 2 * 2, 6 = 2 * 3, 2 divides 14, 3 divides 15, but 4 or 6 divide neither. Thirteen is prime and it is sufficient to trial factor it with 2 and 3, since sqrt(13) ~3.6055 and the next prime, 5, exceeds 13's square root.
  10. Mersenne numbers are a small subset of the natural numbers, having the form of a simple function M(n) = 2n - 1 where n is a natural number greater than 1.
  11. Given a factor a of a number n = a b, the cofactor of a is b = n / a. (definition copied from
  12. Any Mersenne number with a composite exponent n is composite; cannot be a prime. See
  13. Mersenne primes are a small subset of the set of Mersenne numbers with prime exponents. (It is not known whether the set of Mersenne primes is infinite.)
  14. Any factors of Mersenne numbers with prime exponents are of the form f = 2 k p + 1, where p is the prime exponent, and k is a natural number.
  15. Numbers 2 k p + 1 can only be factors of Mersenne numbers with prime exponent if 2 k p + 1 = either 1 or 7, mod 8.
  16. Multiple methods of computerized factoring are employed for Mersenne numbers. Which are worthwhile, and the extent or level of effort to which they are worthwhile, depend on the size of the exponent, the efficiency of algorithm and implementation, and characteristics of the computing hardware involved.
  17. For some additional background, see regarding trial factoring, P-1 factoring, and the Lucas Lehmer test, regarding probable prime testing and the Gerbicz error check, and for an excellent backgrounder including FFT based multiplication of very large numbers
  18. Large amounts of effort have been invested in developing and optimizing factoring and primality testing code relevant to Mersenne numbers for Intel cpus, nonIntel cpus, and gpus from NVIDIA, AMD and also trial factoring on Intel integrated graphics processors. There is summary info about these at
  19. Trial division is one factorization method. Much more about it is available at (especially #12 about implementation as modpow rather than long division for greatly increased speed) and and elsewhere
  20. For exponents much smaller than the current GIMPS search area, ECM (elliptic curve method) is also useful. But not at the current Great Internet Mersenne Prime Search (GIMPS) first-test or double-check wavefront of activity.
  21. P-1 factoring is another useful method, including at currently active and higher exponents. See also and
  22. Eventually, factorization attempts produce diminishing returns, declining to the point where it is more efficient to run either a conclusive primality test (Lucas-Lehmer test), or a quite reliable probable-prime test (PRP3) that can prove a number composite but cannot prove it prime. See also
  23. In such lengthy computations, errors will sometimes occur. For error rates see
  24. The programs contain various error checks that are performed during the computation. These often allow detection of an error and retreating to the point before an error was detected and attempting that portion of the computation again, which can save the lengthy computation if the error is not reproducible.
  25. Some applications report the final error counts with the result. Results with counts of detected errors that may be serious concerning result accuracy can be scheduled for early checking.
  26. Primality tests are eventually done at least twice, to catch the approximately 2 percent chance of incorrect result per LL test, or lesser error rate with PRP/GEC test, with certain precautions taken to ensure results are arrived at independently. The final result of a test mod 264 (called 64-bit residue or res64) is reported to the PrimeNet server. In the case of mismatches for the same exponent and primality test type, additional runs are made until matches are obtained. A coordinated effort to follow up on mismatches is at
  27. Much more on error types and handling is available at
  28. An exciting recent development is the PRP proof, certificate, and verification process supported in gpuowl, mprime, prime95 and the PrimeNet server, and being developed for Mlucas, after first deployment in gpuowl. This is expected to replace for new tests the doublecheck effort described in #26, reducing verification effort to less than 5% of its current cost. Existing completed tests and future runs performed without the proof code present and enabled will still need double-checks.
Some additional reading that may be of use at some point includes:
"A Friendly Introduction to Number Theory", Joseph H. Silverman,
The Prime Pages
Knuth's Algorithms, Donald Knuth
Prime Numbers and Computer Methods for Factorization, Hans Riesel
Number Theory Web
"Prime Numbers: A Computational Perspective", Crandall and Pomerance
"Humble Pi", Matt Parker
"The C Programming Language", Kernighan and Ritchie

"Recreations In The Theory of Numbers", Albert Beiler

(Thanks to Batalov, Dylan14, LaurV and Dr. Sardonicus for contributing to the accuracy and readability of this post; see reference discussion thread.)

Top of reference tree:

Last fiddled with by kriesel on 2020-09-05 at 15:51 Reason: update regarding prp proof implementation status
kriesel is online now