Finding primes & proving primality
4.3:
Conclusion and suggestions |
 |
|
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?