3.6 Fermat’s Theorem and Euler’s TheoremFermat’s Theorem and Euler’s Theorem – Introduction to Cryptography with Coding Theory, 3rd Edition

3.6 Fermat’s Theorem and Euler’s Theorem

Two of the most basic results in number theory are Fermat’s and Euler’s theorems. Originally admired for their theoretical value, they have more recently proved to have important cryptographic applications and will be used repeatedly throughout this book.

Fermat’s Theorem

If p is a prime and p does not divide a,  then

ap11(modp).

Proof. Let

S={1, 2, 3, , p1}.

Consider the map ψ:SS defined by ψ(x)=ax(modp). For example, when p=7 and a=2,  the map ψ takes a number x,  multiplies it by 2, then reduces the result mod 7.

We need to check that if xS,  then ψ(x) is actually in S; that is, ψ(x)0. Suppose ψ(x)=0. Then ax0(modp). Since gcd(a, p)=1,  we can divide this congruence by a to obtain x0(modp),  so xS. This contradiction means that ψ(x) cannot be 0, hence ψ(x)S. Now suppose there are x, yS with ψ(x)=ψ(y). This means axay(modp). Since gcd(a, p)=1,  we can divide this congruence by a to obtain xy(modp). We conclude that if x, y are distinct elements of S,  then ψ(x) and ψ(y) are distinct. Therefore,

ψ(1), ψ(2), ψ(3), , ψ(p1)

are distinct elements of S. Since S has only p1 elements, these must be the elements of S written in a some order. It follows that

123(p1)ψ(1)ψ(2)ψ(3)ψ(p1)(a1)(a2)(a3)(a(p1))ap1(123(p1))(modp).

Since gcd(j, p)=1 for jS,  we can divide this congruence by 1, 2, 3, , p1. What remains is 1ap1(modp).

Example

210=10241(mod11). From this we can evaluate 253(mod11): Write 253=(210)52315238(mod11). Note that when working mod 11, we are essentially working with the exponents mod 10, not mod 11. In other words, from 533(mod10),  we deduce 25323(mod11).

The example leads us to a very important fact:

Basic Principle

Let p be prime and let a, x, y be integers with gcd(a, p)=1. If xy(modp1),  then axay(modp). In other words, if you want to work mod p,  you should work mod p1 in the exponent.

Proof. Write x=y+(p1)k. Then

ax=ay+(p1)k=ay(ap1)kay1kay(modp).

This completes the proof.

In the rest of this book, almost every time you see a congruence mod p1,  it will involve numbers that appear in exponents. The Basic Principle that was just stated shows that this translates into an overall congruence mod p. Do not make the (unfortunately, very common) mistake of working mod p in the exponent with the hope that it will yield an overall congruence mod p. It doesn’t.

We can often use Fermat’s theorem to show that a number is composite, without factoring. For example, let’s show that 49 is composite. We use the technique of Section 3.5 to calculate

224(mod49)241628162112161122323223239248232216392315.

Since

2481(mod49), 

we conclude that 49 cannot be prime (otherwise, Fermat’s theorem would require that 2481(mod49)). Note that we showed that a factorization must exist, even though we didn’t find the factors.

Usually, if 2n11(modn),  the number n is prime. However, there are exceptions: 561=31117 is composite but 25601(mod561). We can see this as follows: Since 5600(mod2),  we have 2560201(mod3). Similarly, since 5600(mod10) and 5600(mod16),  we can conclude that 25601(mod11) and 25601(mod17). Putting things together via the Chinese remainder theorem, we find that 25601(mod561).

Another such exception is 1729=71319. However, these exceptions are fairly rare in practice. Therefore, if 2n11(modn),  it is quite likely that n is prime. Of course, if 2n11(modn),  then n cannot be prime.

Since 2n1(modn) can be evaluated very quickly (see Section 3.5), this gives a way to search for prime numbers. Namely, choose a starting point n0 and successively test each odd number nn0 to see whether 2n11(modn). If n fails the test, discard it and proceed to the next n. When an n passes the test, use more sophisticated techniques (see Section 9.3) to test n for primality. The advantage is that this procedure is much faster than trying to factor each n,  especially since it eliminates many n quickly. Of course, there are ways to speed up the search, for example, by first eliminating any n that has small prime factors.

For example, suppose we want to find a random 300-digit prime. Choose a random 300-digit odd integer n0 as a starting point. Successively, for each odd integer nn0,  compute 2n1(modn) by the modular exponentiation technique of Section 3.5. If 2n11(modn),  Fermat’s theorem guarantees that n is not prime. This will probably throw out all the composites encountered. When you find an n with 2n11(modn),  you probably have a prime number. But how many n do we have to examine before finding the prime? The Prime Number Theorem (see Subsection 3.1.2) says that the number of 300-digit primes is approximately 1.4×10297,  so approximately 1 out of every 690 numbers is prime. But we are looking only at odd numbers, so we expect to find a prime approximately every 345 steps. Since the modular exponentiations can be done quickly, the whole process takes much less than a second on a laptop computer.

We’ll also need the analog of Fermat’s theorem for a composite modulus n. Let ϕ(n) be the number of integers 1an such that gcd(a, n)=1. For example, if n=10,  then there are four such integers, namely 1,3,7,9. Therefore, ϕ(10)=4. Often ϕ is called Euler’s ϕ-function.

If p is a prime and n=pr,  then we must remove every pth number in order to get the list of a’s with gcd(a, n)=1,  which yields

ϕ(pr)=(11p)pr.

In particular,

ϕ(p)=p1.

More generally, it can be deduced from the Chinese remainder theorem that for any integer n, 

ϕ(n)=np|n(11p), 

where the product is over the distinct primes p dividing n. When n=pq is the product of two distinct primes, this yields

ϕ(pq)=(p1)(q1).

Examples

ϕ(10)=(21)(51)=4, 
ϕ(120)=120(112)(113)(115)=32

Euler’s Theorem

If gcd(a, n)=1,  then

aϕ(n)1(modn).

Proof. The proof of this theorem is almost the same as the one given for Fermat’s theorem. Let S be the set of integers 1xn with gcd(x, n)=1. Let ψ:SS be defined by ψ(x)ax(modn). As in the proof of Fermat’s theorem, the numbers ψ(x) for xS are the numbers in S written in some order. Therefore,

xSxxSψ(x)aϕ(n)xSx.

Dividing out the factors xS,  we are left with 1aϕ(n)(modn).

Note that when n=p is prime, Euler’s theorem is the same as Fermat’s theorem.

Example

What are the last three digits of 7803?

SOLUTION

Knowing the last three digits is the same as working mod 1000. Since ϕ(1000)=1000(112)(115)=400,  we have 7803=(7400)27373343(mod1000). Therefore, the last three digits are 343.

In this example, we were able to change the exponent 803 to 3 because 8033(modϕ(1000)).

Example

Compute 243210(mod101).

SOLUTION

Note that 101 is prime. From Fermat’s theorem, we know that 21001(mod101). Therefore,

243210(2100)4322101432210102414(mod101).

In this case, we were able to change the exponent 43210 to 10 because 4321010(mod100).

To summarize, we state the following, which is a generalization of what we know for primes:

Basic Principle

Let a, n, x, y be integers with n1 and gcd(a, n)=1. If xy(modϕ(n)),  then axay(modn). In other words, if you want to work mod n,  you should work mod ϕ(n) in the exponent.

Proof. Write x=y+ϕ(n)k. Then

ax=ay+ϕ(n)k=ay(aϕ(n))kay1kay(modn).

This completes the proof.

This extremely important fact will be used repeatedly in the remainder of the book. Review the preceding examples until you are convinced that the exponents mod 400=ϕ(1000) and mod 100 are what count (i.e., don’t be one of the many people who mistakenly try to work with the exponents mod 1000 and mod 101 in these examples).

3.6.1 Three-Pass Protocol

Alice wishes to transfer a secret key K (or any short message) to Bob via communication on a public channel. The Basic Principle can be used to solve this problem.

First, here is a nonmathematical way to do it. Alice puts K into a box and puts her lock on the box. She sends the locked box to Bob, who puts his lock on the box and sends the box back to Alice. Alice then takes her lock off and sends the box to Bob. Bob takes his lock off, opens the box, and finds K.

Here is the mathematical realization of the method. First, Alice chooses a large prime number p that is large enough to represent the key K. For example, if Alice were trying to send a 56-bit key, she would need a prime number that is at least 56 bits long. However, for security purposes (to make what is known as the discrete log problem hard), she would want to choose a prime significantly longer than 56 bits. Alice publishes p so that Bob (or anyone else) can download it. Bob downloads p. Alice and Bob now do the following:

  1. Alice selects a random number a with gcd(a, p1)=1 and Bob selects a random number b with gcd(b, p1)=1. We will denote by a1 and b1 the inverses of a and b mod p1.

  2. Alice sends K1Ka(modp) to Bob.

  3. Bob sends K2K1b(modp) to Alice.

  4. Alice sends K3K2a1(modp) to Bob.

  5. Bob computes KK3b1(modp).

At the end of this protocol, both Alice and Bob have the key K.

The reason this works is that Bob has computed Kaba1b1(modp). Since aa1bb11(modp1),  the Basic Principle implies that Kaba1b1K1K(modp).

The procedure is usually attributed to Shamir and to Massey and Omura. One drawback is that it requires multiple communications between Alice and Bob. Also, it is vulnerable to the intruder-in-the-middle attack (see Chapter 15).