| |
Finding very large primes is inherently difficult. Some of the
algorithms for special forms can be easy to understand, but programming them
requires fast multiplication of very large numbers. Choosing which
number to test can also require thought. Before using the main
primality tests we also should strongly consider presieving with some
type of trial division program.
A variety of programmers have done their best to make this easier for
you. For example, on the top twenty list you can see those programs that
have used while finding the most primes. But if you look at this list
closely you will see we are comparing apples and oranges--the programs in the list
often do very different things. Below I will explain the very rough
categories we have divided these programs into.
- sieve
- A sieve quickly removes the numbers that have small composite
divisors from large set of potentially prime numbers. Folks that find the
record twins, for example, sieve very heavily before they use more
definitive (and time consuming) primality tests.
- minus
- We can prove a number N is prime if we have enough factors of
N-1. Programs that implement this type of test for a reasonably broad
class of numbers are indicated with 'minus' in the database.
- plus
- We can also prove a number N is prime if we have enough factors of
N+1. Programs that implement this type of test for a reasonably broad
class of numbers are indicated with 'plus' in the database.
- classical
- There are ways of combining factors of N-1 and N+1, as well as
factors of Nk-1 for small integers k.
Programs that implement some relatively large part of these combined tests are
marked with 'classical' in the database.
- special
- 'special' is just that, the program implements some test that works
only for a very special form of prime (e.g., Prime95 implements just the
Lucas-Lehmer test for Mersennes, but does it exceptionally well!)
- general
- The hardest type of program to write is perhaps one that will
quickly show a large number prime without using the classical tests
above. Those few that do are marked 'general'.
- other
- I am not sure what this means yet. Certainly something other
than the above...
Notes:
- The above categories are very broad and roughly applied. To see
what a program really does, go to its web site.
- I only list programs used to find several primes on the list of the
largest known primes. Look elsewhere for programs that work for small
numbers (say less than 5,000 digits).
|
