What is a pseudoprime?

An integer n is a Fermat pseudoprime to base a if a^n-1 - 1 is divisible by n, and n is not prime.

Last week's code-breaking challenges (Mini-Challenges #6 and #7) were fun, but cryptography in the internet age is more sophisticated. Many modern cryptographic methods involve prime numbers, and it is therefore to crack codes it is necessary to have efficient ways to determine whether or not a number is prime.

There is an obvious way to check whether a number n is prime - you  can simply try every smaller number greater than 1 to see whether it is a divisor of n.  You should be able to convince yourself that you needn't try numbers bigger than the square root of n, and that you need only try prime numbers as divisors.  For example, to see whether 10001 is prime, you need only try the prime numbers up to 100, meaning that you only need to test using 25 primes.

But this method becomes impracticable for numbers much larger than 10²⁰, and other methods are used.

One property that prime numbers have is given by Fermat's Little Theorem.  Let p be a prime number.  If a is any number not divisible by p, then a^p-1 - 1 is divisible by p. (Recall from Tutorial 5 that this is the same as writing that a^p-1 - 1 is congruent to 0 (mod p), or a^p-1 ≡ 1 (mod p).)

This suggests a way to see whether a number is not prime -- given a number n, choose any a in the range 1 < a < n, and compute a^n-1 (mod n).  If this is not 1, then n cannot be prime.

It turns out to be very quick to compute powers a^n-1: we may compute a, a², a⁴, a⁸, etc., by successively squaring the previous term, and then we may multiply suitably-chosen terms together.  In fact, since we only care about the remainders modulo n, we should do all our arithmetic modulo n. (In other words, we should take the remainder, using % operator in Python).

Unfortunately, for each a, there are numbers which are not prime, but which nevertheless satisfy a^n-1 ≡ 1 (mod n).  Such numbers are called Fermat pseudoprimes to base a.  You could check, for example, that 2³⁴⁰ = 1 (mod 341), but 341=11x31, so 341 is a pseudoprime to base 2 (in fact, it is the smallest pseudoprime to base 2).