|
Lucas's Primality Test With Factored N−1 |
|
|
|
Fermat's Little Theorem assures us that if N is a prime then |
|
|
|
|
|
|
|
for every integer b coprime to N. In contrast, if N is composite it is quite rare for the above congruence to be satisfied for any b. This fact enables us to test for compositeness quite easily, simply by checking to see if bN−1 is congruent to 1 (mod N) for some particular value of b. However, although this congruence is necessary for primality, it isn't quite sufficient, because for any given base b there exist composites N that satisfy (1). Such integers are called pseudoprimes to the base b. In fact, there exist composite integers that are pseudoprimes to every base with which they share no common factor. Such composites are called Carmichael numbers, the smallest of which is 561. |
|
|
|
Euler generalized Fermat's theorem by showing that for any integer N, prime or composite, we have |
|
|
|
|
|
|
|
for any integer b coprime to N, where ϕ(N) is Euler's totient function, representing the number of positive integers less than and coprime to N. Obviously if N is a prime then ϕ(N) = N−1, in which case Euler's theorem reduces to Fermat's. |
|
|
|
Edouard Lucas noticed that Euler's theorem enables us to definitely determine the primality of N fairly easily if we know the factorization of N−1. The basic idea of this test is the foundation for virtually all deterministic primality tests, so it's worthwhile to understand exactly how it works. |
|
|
|
Suppose we examine the residues (mod N) of the sequence |
|
|
|
|
|
|
|
Let T denote the smallest exponent such that bT = 1 (mod N). This implies that bk can be congruent to 1 (mod N) only if k is a multiple of T. We can call T the fundamental period of the sequence modulo N. Also, from Euler's theorem we know that bϕ(N) = 1 (mod N), so clearly ϕ(N) is a multiple of T. Thus we can write ϕ(N) = mT for some integer m. |
|
|
|
Now, suppose we have determined by calculation that the number N satisfies Fermat's condition for primality with respect to the base b. In other words, we have found that bN−1 = 1 modulo N. It follows that N−1 must be a multiple of the fundamental period T, so we can write N−1 = nT for some integer n. Thus we know that the fundamental period T divides both ϕ(N) and N−1. Of course, we also know that ϕ(N) is less than or equal to N−1. Therefore, if we could prove that the fundamental period T equals N−1, then it would follow that ϕ(N) equals N−1, which can only be the case if N is a prime. |
|
|
|
But how can we prove that T = N−1? Well, we know that N−1 = nT for some integer n, which means that n divides N−1. Assuming n is greater than 1, let p denote any prime divisor of n. It follows that p is also a prime divisor of N−1, and we must have |
|
|
|
|
|
|
|
On the other hand, suppose we examine b(N−1)/q for every prime divisor q of N−1 and we find that none of those values is congruent to 1 (mod N). This can only mean that n = 1, which means the fundamental period T equals N−1, and therefore ϕ(N) equals N−1 (because T divides ϕ(N), and ϕ(N) is less than or equal to N−1). |
|
|
|
This proves Lucas's primality criterion: If, for some integer b, the quantity b(N-1) is congruent to 1 modulo N, and if b(N-1)/q is not congruent to 1 modulo N for any prime divisor q of N-1, then N is a prime. |
|
|
|
Of course, this all just amounts to the assertion that if we can find an element b whose "order" mod N is N−1, then N is a prime. Such a number is called a "primitive root" mod N. If N is a prime there are ϕ(N-1) primitive roots modulo N, so we are assured of the existence of this many values of b that would be suitable to prove the primality of N via Lucas's test. |
|
|
