Introduction to Public-Key Cryptography - Understanding Cryptography - page 165

Theorem 6.3.2 Fermat's Little Theorem
Let a be an integer and p be a prime, then:

a p ≡ a ( mod p ) .

We note that arithmetic in finite fields GF ( p ) is done modulo p , and hence, the
theorem holds for all integers a which are elements of a finite field GF ( p ).The
theorem can be stated in the form:

a p − 1 ≡ 1 ( mod p )

which is often useful in cryptography. One application is the computation of the
inverse in a finite field. We can rewrite the equation as a

a p − 2

1 ( mod p ).This
is exactly the definition of the multiplicative inverse. Thus, we immediately have a
way for inverting an integer a modulo a prime:

· ≡

a − 1 a p − 2 ( mod p ) ≡ (6.7)

We note that this inversion method holds only if p is a prime. Let's look at an
example:

Example 6.11. Let p = 7 and a = 2. We can compute the inverse of a as:

a p − 2 = 2 5 = 32 ≡ 4mod7 .

This is easy to verify: 2 · 4 ≡ 1 mod 7.

Performing the exponentiation in Eq. (6.7) is usually slower than using the extended
Euclidean algorithm. However, there are situations where it is advantageous to use
Fermat's Little Theorem, e.g., on smart cards or other devices which have a hard-
ware accelerator for fast exponentiation anyway. This is not uncommon because
many public-key algorithms require exponentiation, as we will see in subsequent
chapters.
A generalization of Fermat's Little Theorem to any integer moduli, i.e., moduli
that are not necessarily primes, is Euler's theorem .

Theorem 6.3.3 Euler's Theorem
Let a and m be integers with gcd( a , m )=1 , then:

a Φ( m )

≡ 1 ( mod m ) .

Since it works modulo m , it is applicable to integer rings Z m . We show now an

example for Euler's theorem with small values.

Example 6.12. Let m = 12 and a = 5. First, we compute Euler's phi function of m :