Finding primes & proving primality 4.3: Conclusion and suggestions
 Home > Primality Proving > Chapter Five: Conclusion

### Conclusion

In practice it is easy to decide what method of primality proof to use:

• If all you want to do is find any number of large enough to make the list of largest known primes, use a version of Proth's Theorem such as theorem 3 (or an equivalent plus side theorem).
• If you are aiming for the money, then either join GIMPS (as Mersenne's have held the record for quite awhile now) or look for a very large generalized Fermat.
• If instead of looking for n, you are given n, first check for small factors.  If it has none, try a Fermat test to see if it is a probable prime.  If so, try briefly to factor n+1, n-1...  If these factor substantially use the classical methods, if not, then reach for a modern method.

When programming the classical methods, the most difficult aspect is multiplying quickly.  Fortunately someone has done much of the work for us!  There are several large free libraries for arithmetic with large integers as well as for proving the primality of large integers.

With the classical methods you can easily handle a 100,000 digit number.  With the modern methods you will work very hard to handle a 5,000 digit number!  Unless you are very brave I would suggest you look for an already coded version of the modern algorithms, they are quite difficult to implement.

At this site we keep a list of the 5000 largest known primes, so if you do find new record primes, why not let us know

 [ next page | previous page ] Copyright © 2023 PrimePages (Originally written by Chris Caldwell)