Programming Praxis

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 b^n-1 ≡ 1 (mod n) for every integer b coprime to n):

If, for some integer b, b^n-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 2⁸⁹-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.

Pages: 1 2