Primality Testing

• Sieve of Eratosthenes
• Trial Division and Fermat
• Pseudoprimes

Sieve of Eratosthenes

The idea behind the sieve is that we have a table containing all the integers from 2 to highest prime we want. Starting with 2 we cross off all multiples of 2 - which obviously cannot be prime as they are divisible by 2. Now we look at the table and see that 3 is the next number and therefore is a prime. We cross off all multiples of 3 and look for the next number, 5, which we now know to be the next prime.

The following is an example of the algorithm. This is the table to get all the primes up to 50

Now we will cross of all multiples of 2

Now we will cross of all multiples of 3

Now we will cross of all multiples of 5

Finally we can cross of all multiples of 7. We say finally as once past the square root of 50 we can stop. (See Trial Division in Factorization section).

Thus the prime numbers less than 50 are: 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47.

There aare two problems with using this method to test for primality. Firstly, it requires a large amount of storage space. Secondly, it is quite slow. The one advantage it does have is that no division is use (and no multilication either). This idea is used later in a different form.

Trial Division and Fermat

In the section on factorization we showed two methods of factorizing numbers. One of the properties of these searches is that they will prove primality if they are run for long enough. However, they are not useful when numbers grow beyond ten or twelve digits.

Pseudoprimes

I will give a better explanation of pseudoprimes in my report, where I have access to better math symbols, but here is the basics behind pseudoprimes and the spseudoprime test.

Fermat observed that if p is a prime then:
2^(p-1) = 1 (mod p)
This basically says, when you raise 2 to the power of p-1 modulus p, you get 1. This means that we have a test for primality that works quite quickly. There is however a slight problem - pseudoprimes.

There are other numbers that exhibit the same property; 341 for example.
341 = 11 x 31
but when we raise 2 to the power of 340 mod 341, we get 1. This means that the test described above is not always successful due to the presence of pseudoprimes like 341. The good news is that there are not many composite numbers that have this property.

Fermat noticed however that there was nothing special about the 2 in the test. Any base that is coprime to the tested number can be used. The advantage of this is that if we use a 3 instead of 2 as the base, 341 fails the test and we can therefore conclude that it is not prime. If we try a few of these different bases, then we can become extremly sure that we have a prime if it passes for all of them. As we increase the number of bases we test against, we improve the probability. Numbers that pass for all bases coprime are called Carmichael numbers (the first is 561 = 3 x 11 x 17) but they are extremely rare. There are only 2163 Carmichael numbers below 25 x 10^9

The Strong Psedoprime Test

There does however exist another test that increases the odds that a number which passes the test is prime. Let us consider n, which passes the test for a base b, where gcd(b,n)=1. There fore n divides
b^(n-1) - 1
Since n must be odd (we would not bother with the test otherwise!) it can be written as n = 2m + 1. So re-writing, n divides
b^(2m) - 1 = (b^m - 1) * (b^m + 1)
by the difference of two squares formula. This means that n must divide one of the right hand factors, if it is prime. It must not divide both of them or would have divided the difference:
(b^m + 1) - (b^m - 1) = 2
which it clearly could not. So if n really is prime, then
b^m === 1 or -1 (mod n)

This can be used in a very efficient algorithm (essentially as fast as the pseudoprime test above). Trial division should be performed first so that the bases are proved to be coprime to the number. Strong pseudoprimes do exist but they are much more scarce than normal pseudoprimes. If we run the test for several different bases, the probability of an incorrect test reduces further. For the bases 2, 3, 5, and 7 there are 1770 pseudoprimes but only 1 strong pseudoprime
3,215,031,752 = 151 x 751 x 28351
less than 25 x 10^9.

A further piece of good news is that there is no analog to the Carmichael numbers we found for pseudoprimes. It can be proven that if n is composite it will fail the strong pseudoprime test for at least half the bases less than n. This might be a long way to prove that a number is prime but it shows the strength of a series of strong pseudoprime tests.

Proof of Primality

Ronan Killeen
Back to home.