Help: What Primality Programs Do

The List of Largest Known Primes

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 N^k-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).