Fermat’s “Little” Theorem: Computational Applications

by Henri Cohen

In Honor of Michael Rabin’s Honoris Causa Doctorate

Talence, May 10, 1996 1. Fermat’s Theorem in (ℤ/pℤ)^{∗}

1.1. Introduction

Fermat’s little theorem states that for all prime numbers p and all integers a not divisible by p, we have

a^{p−1} ≡ 1 (mod p) .

The computational aspect of this theorem is due to the following two remarks.

• It is easy to compute a^{p−1} (mod p), even when p is a very large integer (several hundred digits, for example). This is done by using binary powering methods (writing the exponent in base 2), and reducing modulo p as we go along, so that numbers never get larger than p^{2}. This is in marked contrast with the computation of (p−1)! (mod p) for example, which nobody knows how to do quickly when p is very large.

• Although there exist non-prime numbers p satisfying Fermat’s theorem, such “pseudo-primes” are rather rare. For example, the smallest non-prime p such that 2^{p−1} ≡ 1 (mod p) is p = 341 = 11 · 31.

There even exist non-prime numbers p such that a^{p−1} ≡ 1 (mod p) for all a coprime to p. Such numbers are called “Carmichael numbers” and it has only recently been proved by Alford, Granville and Pomerance, that there are infinitely many (in fact more than c · x^{2/7} up to x for some positive c).

Thus, in a first approach to the problem of factoring and primality testing, it is reasonable to proceed as follows. Given a number n, one first trial divides n by small prime numbers up to a certain bound. If this does not give a factor, one then computes 2^{n−1} (mod n). If this is not equal to 1, then we have proved that n is not prime without having given a factor, which seems surprising at first. On the other hand, if 2^{n−1} ≡ 1 (mod n), we may start to believe that n is prime, but this may of course be wrong.

The history of the use of Fermat’s theorem in computational number theory, and especially in the field of primality testing and factoring, is entirely about finding ways to strengthen the statement so that the converse holds, or almost holds.

1.2. Exact Converses: Pocklington-Lehmer

Historically, the first mathematically correct converse to Fermat’s theorem is due to Pocklington, and was improved later by Lehmer and other authors. A very weak version of such a converse is as follows:

Theorem 1. Let N be a positive integer. Assume that for every prime p dividing N − 1 we can find a_{p} such that

a_{p}^{N−1} ≡ 1 (mod N) and gcd(a_{p}^{(N−1)/p}−1, N) = 1 .

Then N is prime.

This type of converse has been considerably improved, but stumbles on a major difficulty: we must find all the prime factors of N − 1. This is in general an infeasible task (factoring is much more difficult than primality testing!). Hence, except in very special cases (for example if N if of the form h2^{n} + 1), this theorem or its improvements will not be very useful.

1.3. Probablistic Compositeness Tests: the Rabin-Miller Test

Another type of statement is obtained by strengthening the result of Fermat’s theorem. Indeed, we have the following result.

Theorem 2. Let N be a positive odd integer, and write N − 1 = 2^{t}m with m odd.

(1) Assume that N is prime. Then for any integer a such that 1 < a < N, either

a^{m} ≡ 1 (mod N)

or there exists j such that 0 ≤ j < t and

a^{2^{j}m} ≡ −1 (mod N) .

(2) Conversely, assume that N is not a prime. The number of a satisfying the conditions of (1) is at most equal to N/4.

This theorem leads to the “Rabin-Miller” probabilistic compositeness test, which goes as follows. After having checked that N is not divisible by small primes, pick at random 10 values of a in the interval [2, N − 1], and test whether the conditions of the theorem are satisfied. If for a single value of a they are not, then N is not prime. If they are satisfied for all values of a, then N has a very good chance of being prime (some authors say that it has probability greater than 1 − 4^{−10}, but this is incorrect). This compositeness test is the workhorse of primality testing and factoring algorithm, and is usually the only one implemented in computer algebra systems.

Obtaining counterexamples to this test is much more difficult, and in fact this doesn’t make much sense since the numbers a are chosen at random. However, recent work on the subject has shown that for some composite numbers N, the test is not as good as it looks, essentially because the trials with different numbers a are not independent. This leads to improvements which are mentioned below.

1.4. Factoring: Pollard’s p − 1

As mentioned, Fermat’s theorem is depressing, since when it tells you that a^{n−1} ≢ 1 (mod n) (with 1 < a < n) you know that n is not prime, but you have no idea of the factors of n, hence one may consider this as a purely negative result. That this is not so, and that Fermat’s theorem can be used in factoring was apparently noticed for the first time at the end of the sixties by J. Pollard whose name is associated to many of the major advances in primality testing and factoring over the last 20 years, although he describes himself as an amateur mathematician.

The idea is as follows. Let N be the number to be factored, and assume that there exists a prime divisor p of N such that p − 1 has only relatively small prime factors (of course p is not known, and this may not happen, but in fact it happens quite frequently). Denote by [1, 2, …, B] the least common multiple of all the integers less or equal to B. Then, if all the prime power factors of p − 1 are less than B, we have:

(p − 1)|[1, 2 …, B] ,

hence by Fermat’s theorem, if a is coprime to N, hence in particular to p, we have

a^{[1,2,...,B]} ≡ 1 (mod p) ,

which implies that

gcd(a^{[1,2,...,B]} − 1, N) > 1 .

The above GCD can easily be computed by induction on B, by using binary powering techniques as usual (in fact the GCD is not computed each time), and if it is not equal to N, which it will rarely be, we have found a non-trivial factor of N.

This method can be considerably improved by the use of various tricks, and leads to spectacular results. It is not uncommon that prime factors of 20 digits or more are discoved in this way. Thus, we see that Fermat’s theorem can also be used for factoring.

However, the major importance of Pollard’s p − 1 method, as this method is known, comes from the fact that it has become the template of several of the best modern methods for factoring, such as Lenstra’s Elliptic Curve Method (see below).

2. The use of Other Groups

2.1. Introduction

The other direction in which mathematicians have studied the computational use of Fermat’s theorem in primality testing and factoring is to change the group used. Indeed, Fermat’s theorem can be viewed as the special case G = (ℤ/pℤ)^{∗} of the following purely grouptheoretic statement:

Theorem 3. Let G be a finite group of cardinality m, let e be the identity element of G, and let g ∈ G be any element. Then

g^{m} = e .

Thanks to this theorem, we can now in more detail.in more detail.play the same game that we have played in the case of the usual case of Fermat’s theorem: we can use it for primality testing, for probabilistic compositeness tests, and for factoring.

The only restriction is that we must use finite groups which are in some way linked to the number-theoretical properties of the number N.

Computational number theorists use the following groups: (ℤ/Nℤ)^{∗} (the group used up to now), 𝔽_{N^{2}}^{∗} and more generally 𝔽_{N^{k}}^{∗} (where 𝔽_{q} denotes the finite field with q elements), (R/NR)^{∗} (where R is some ring), Cl(ℚ(\sqrt{−kN})) (class group of imaginary quadratic fields), E(ℤ/Nℤ) (elliptic curves over ℤ/Nℤ).

We now consider briefly each of these groups.

2.2. The Groups 𝔽_{N^{2}}^{∗} and 𝔽_{N^{k}}^{∗}.

Consider once again the problem of primality testing. If N is prime and d is a quadratic non-residue modulo N, then 𝔽_{N}(\sqrt{d}) is a field with N^{2} elements, and hence its multiplicative group has N^{2} − 1 = (N − 1)(N + 1) elements. Playing the above game in this group, either using explicitly elements of the form a + b\sqrt{d} or equivalently what one calls “Lucas sequences” leads to the so-called “N +1-tests”. We have the same theorems as before (Pocklington-Lehmer, Rabin-Miller, Pollard p + 1), except that now it is the factorization of N + 1, totally unrelated to that of N − 1, which is used.

These tests can be combined with the N −1 tests, and the combination is much stronger than each individual test, even repeated.

2.3. The Groups R/NR

Many rings R can be used in this context. Perhaps the most successful has been the ring ℤ[ζ] of cyclotomic integers, where ζ is some root of unity. It is impossible to give details here, but the use of this ring led Adleman, Pomerance and Rumely, followed by H. Lenstra and the author, to the development of the so-called “Jacobi sum test”, which was the first primality testing program able to prove the primality of numbers of hundreds of decimal digits (running time O(log n^{log log log n})).

This was perhaps the first occurence of non-trivial notions of algebraic number theory in the field of factoring and primality testing, and now this type of tool completely dominates the field (elliptic curves, algebraic number fields, etc...).

The basic reason that makes the test work is that we make several independent Fermat-type tests in cyclotomic rings which can easily be combined using the underlying rich algebraic structure. This is in marked contrast with the classical tests where it is very difficult to combine information coming from different tests, except in trivial ways.

2.4. The Groups Cl(ℚ(\sqrt{−kN}))

The definition of the class group of a number field is not difficult, but I will not give it here. It is enough to say that for any negative number D one can define a finite Abelian group Cl(ℚ(\sqrt{D})), and that the arithmetic properties of D are partly reflected in the structure of this class group. In particular, if D is a multiple of a number N which one wants to factor, the 2-sylow subgroup of this group gives the factorizations of N.

All this was essentially known to Gauss (1798), but we had to wait for D. Shanks (1967) who showed that it was possible to compute these class groups quite quickly (time O(N^{1/4})). Although much slower than primality tests, this was at the time a very competitive factoring method, the other method used at the time being the continued fraction method, which has little to do with Fermat’s theorem.

However, the story did not stop there, and it took 10 more years for Shanks, Pollard, Atkin and Rickert (SPAR) and independently Lenstra and Schnorr, to notice that one can compute the 2-sylow subgroup, hence the factorization of N, much faster than this (in average sub-exponential time, although in the worst case it is exponential).

In the field of factoring, sub-exponential time means time

O (e^{c(log N)^{a}(log log N)^{1−a}}) ,

usually with a = 1/2, and more recently with the advent of the number field sieve, with a = 1/3.

The idea of SPAR is to use once again the p − 1 idea of Pollard, in the groups Cl(ℚ(\sqrt{−kN})). The essential difference with the initial p − 1 method, which could be used with a single group (ℤ/pℤ)^{∗} or perhaps a few more like 𝔽_{p^{2}}^{∗}, is that we now have an infinite number of groups at our disposal, obtained by varying k, and that these groups have little in common apart from containing information on the factorization of N. Thus, one can balance the bound B used in the p − 1 method and the number of values of k, and the sub-exponential behavior follows from this.

This algorithm, which is not used anymore for other reasons, can factor quite easily numbers having up to 40 decimal digits.

3. The use of Elliptic Curves

Together with the number field sieve, the use of elliptic curves in primality testing and in factoring has probably been one of the major advances on primality testing and factoring. Because of its importance, it is perhaps worthwhile to give a little more details.

Let N be a prime number, N > 3. An elliptic curve E modulo N is an equation of the form

y^{2} = x^{3} + ax + b ,

implicitly understood as a projective equation, i.e. including a point at infinity (0 : 1 : 0), and such that the discriminant 4a^{3} + 27b^{2} is coprime to N. If N is not prime, we assume N coprime to 6, and we can essentially keep the same definitions.

What is remarkable about such curves is that they possess a natural group law obtained in a simple geometrical way by the “tangent and chord” method, and O_{E} = (0 : 1 : 0) is the unit. This group law is eminently computable, and hence we can apply the paradigms of the preceding sections, and obtain primality tests, factoring methods and compositeness tests. Here I summarize in a single sentence 10 years work by many authors, but essentially that’s all there is to it!

3.1. The Atkin-Morain Primality Test

The basic stumbling block in the application of elliptic curves is that it is not so easy to compute the cardinality of the group E(ℤ/Nℤ) of points of an elliptic curve modulo N. If we refer to Fermat’s theorem, it is clear that it is essential to compute this cardinality, which will replace the exponent “p − 1” in the theorem. The analogue of Pocklington’s theorem, which can easily be proven once one knows some properties of elliptic curves such as sharp bounds on their number of points modulo N, is the following (note that we use additive notations for an elliptic curve):

Theorem 4. Let E be an elliptic curve modulo an integer N prime to 6 and greater than or equal to 5. Assume that we know an integer m (which will be in practice the cardinality of E(ℤ/Nℤ), but we do not need to assume this) and a point A ∈ E(ℤ/Nℤ) such that:

(1) m · A = O_{E}

(2) There exists a prime divisor q of m such that q > (N^{1/4} + 1)^{2}, (m/q) · A can be computed and is not equal to O_{E}.

Then N is prime.

The computations necessary to compute m · A or (m/q) · A involve computing inverses modulo N, and may fail. But in that case, a factor of N has been found, so N is not prime. Hence the words “can be computed”.

Note also that this is note quite a generalization of Pocklington’s theorem, since it is not always true that for every elliptic curve, the number of points m of E(ℤ/Nℤ) will have a large prime divisor. However, since E can be varied at will, this is not really a problem.

To overcome the stumbling block of computing this cardinality m, two methods exist. One, suggested by Goldwasser and Killian, is to make use of a very nice but complicated algorithm of Schoof which enables us to compute the cardinality of an elliptic curve in (high degree) polynomial time. This method is not practical.

The second method, suggested by Atkin and implemented by Atkin and Morain, is to use a class of elliptic curves for which the cardinality is known in advance, the curves with complex multiplication. The resulting ECPP test is presently the most powerful primality test in existence, and has proved the primality of numbers having more than 1500 decimal digits.

3.2. Lenstra’s Elliptic Curve Factoring Method

This is the application of the Pollard p−1 method to the group of points of an elliptic curve modulo p, where p is an unknown prime factor of the number N we want to factor. As in the class group case, this method is very efficient because we have a very large number of elliptic curves to play with, and once again we obtain a sub-exponential running time.

This method has, however, several advantages over the class group method.

First, the computation of group law is faster. Second, it is sensitive to the size of the smallest prime divisor of N. Thus, if N has 100 decimal digits, it will not be possible to factor N with the class group method, and it will not be possible either in general with ECM, except that in many cases, N has a factor of reasonable size (say less than 25 decimal digits), and in that case ECM will find it in a reasonable amount of time.

Thus ECM has become the workhorse of factoring methods to remove “small” prime factors, i.e. having up to 40 decimal digits (ouch!).

To factor completely a number of 100 decimal digits (the current range), ECM is not sufficient, and we must use methods not based on Fermat such as the multiple polynomial quadratic sieve method (MPQS) or the number field sieve (NFS). Presently, 85 decimal digits is difficult but standard, 100 decimal digits is very hard, and 125 decimal digits needs the CPU power of several hundred workstations on the Internet.

3.3. The Future

More groups? Yes, for example Abelian varieties, and in particular Jacobians of curves of higher genus. Although several attempts have been made, the results have not been practical. On the other hand, the use of Jacobians of curves of genus 2 has led to a beautiful theoretical result of Adleman and Huang:

Theorem 5. (Adleman-Huang) There exists a probabilistic polynomial time algorithm which can prove or disprove that a given number N is prime.

Questions:

(1) Find other useful groups.

(2) Can one use the p − 1 method in cyclotomic rings?