February 2, 2010
We examined algorithms for checking the primality of a number in two previous exercises. Both algorithms are probabilistic; the Rabin-Miller algorithm has known false positives, and Carl Pomerance proved that the Baillie-Wagstaff algorithm has an infinite number of false positives, even though none are known.
Today’s exercise describes an algorithm for proving that a number is prime, not probably but certainly. The algorithm works by a theorem of Edouard Lucas, which is based on Fermat’s Little Theorem (if n is prime then bn-1 ≡ 1 (mod n) for every integer b coprime to n):
If, for some integer b, bn-1 ≡ 1 (mod n), and if b(n-1)/q ≢ 1 (mod n) for any prime divisor q of n-1, then n is a prime number.
Thus, if the factors of n-1 are known, it is easy to determine the primality of n.
Your task is to write a function that determines the primality of an integer using Lucas’ primality test; use it to prove the primality of 289-1. When you are finished, you are welcome to read or run a suggested solution , or to post your own solution or discuss the exercise in the comments below.