Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

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$ $p$ is a prime and $p$ $p$ does not divide $a,$ $a,$ then

\begin{matrix} a^{p - 1} \equiv 1 & (mod p) . \end{matrix}

$\begin{matrix} a^{p - 1} \equiv 1 & (mod p) . \end{matrix}$

Proof. Let

S = {1, 2, 3, \dots, p - 1} .

$S = {1, 2, 3, \dots, p - 1} .$

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

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

ψ (1), ψ (2), ψ (3), \dots, ψ (p - 1)

$ψ (1), ψ (2), ψ (3), \dots, ψ (p - 1)$

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

\begin{array}{l} 1 \cdot 2 \cdot 3 \dots (p - 1) \\ \equiv ψ (1) \cdot ψ (2) \cdot ψ (3) \dots ψ (p - 1) \\ \equiv (a \cdot 1) (a \cdot 2) (a \cdot 3) \dots (a \cdot (p - 1)) \\ \begin{matrix} \equiv a^{p - 1} (1 \cdot 2 \cdot 3 \dots (p - 1)) & (mod p) . \end{matrix} \end{array}

$\begin{array}{l} 1 \cdot 2 \cdot 3 \dots (p - 1) \\ \equiv ψ (1) \cdot ψ (2) \cdot ψ (3) \dots ψ (p - 1) \\ \equiv (a \cdot 1) (a \cdot 2) (a \cdot 3) \dots (a \cdot (p - 1)) \\ \begin{matrix} \equiv a^{p - 1} (1 \cdot 2 \cdot 3 \dots (p - 1)) & (mod p) . \end{matrix} \end{array}$

Since $gcd (j, p) = 1$ $gcd (j, p) = 1$ for $j \in S,$ $j \in S,$ we can divide this congruence by $1, 2, 3, \dots, p - 1 .$ $1, 2, 3, \dots, p - 1 .$ What remains is $1 \equiv a^{p - 1} (mod p) .$ $1 \equiv a^{p - 1} (mod p) .$

Example

$2^{10} = 1024 \equiv 1 (mod 11) .$ $2^{10} = 1024 \equiv 1 (mod 11) .$ From this we can evaluate $2^{53} (mod 11) :$ $2^{53} (mod 11) :$ Write $2^{53} = (2^{10})^{5} 2^{3} \equiv 1^{5} 2^{3} \equiv 8 (mod 11) .$ $2^{53} = (2^{10})^{5} 2^{3} \equiv 1^{5} 2^{3} \equiv 8 (mod 11) .$ Note that when working mod 11, we are essentially working with the exponents mod 10, not mod 11. In other words, from $53 \equiv 3 (mod 10),$ $53 \equiv 3 (mod 10),$ we deduce $2^{53} \equiv 2^{3} (mod 11) .$ $2^{53} \equiv 2^{3} (mod 11) .$

The example leads us to a very important fact:

Basic Principle

Let $p$ $p$ be prime and let $a, x, y$ $a, x, y$ be integers with $gcd (a, p) = 1 .$ $gcd (a, p) = 1 .$ If $x \equiv y (mod p - 1),$ $x \equiv y (mod p - 1),$ then $a^{x} \equiv a^{y} (mod p) .$ $a^{x} \equiv a^{y} (mod p) .$ In other words, if you want to work mod $p,$ $p,$ you should work mod $p - 1$ $p - 1$ in the exponent.

Proof. Write $x = y + (p - 1) k .$ $x = y + (p - 1) k .$ Then

\begin{matrix} a^{x} = a^{y + (p - 1) k} = a^{y} {(a^{p - 1})}^{k} \equiv a^{y} 1^{k} \equiv a^{y} & (mod p) . \end{matrix}

$\begin{matrix} a^{x} = a^{y + (p - 1) k} = a^{y} {(a^{p - 1})}^{k} \equiv a^{y} 1^{k} \equiv a^{y} & (mod p) . \end{matrix}$

This completes the proof.

In the rest of this book, almost every time you see a congruence mod $p - 1,$ $p - 1,$ 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 .$ $p .$ Do not make the (unfortunately, very common) mistake of working mod $p$ $p$ in the exponent with the hope that it will yield an overall congruence mod $p .$ $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

\begin{array}{l} 2^{2} & \equiv \begin{matrix} 4 & (mod 49) \end{matrix} \\ 2^{4} & \equiv 16 \\ 2^{8} & \equiv 16^{2} \equiv 11 \\ 2^{16} & \equiv 11^{2} \equiv 23 \\ 2^{32} & \equiv 23^{2} \equiv 39 \\ 2^{48} & \equiv 2^{32} 2^{16} \equiv 39 \cdot 23 \equiv 15. \end{array}

$\begin{array}{l} 2^{2} & \equiv \begin{matrix} 4 & (mod 49) \end{matrix} \\ 2^{4} & \equiv 16 \\ 2^{8} & \equiv 16^{2} \equiv 11 \\ 2^{16} & \equiv 11^{2} \equiv 23 \\ 2^{32} & \equiv 23^{2} \equiv 39 \\ 2^{48} & \equiv 2^{32} 2^{16} \equiv 39 \cdot 23 \equiv 15. \end{array}$

Since

\begin{matrix} 2^{48} \equiv 1 & (mod 49), \end{matrix}

$\begin{matrix} 2^{48} \equiv 1 & (mod 49), \end{matrix}$

we conclude that 49 cannot be prime (otherwise, Fermat’s theorem would require that $2^{48} \equiv 1 (mod 49)$ $2^{48} \equiv 1 (mod 49)$ ). Note that we showed that a factorization must exist, even though we didn’t find the factors.

Usually, if $2^{n - 1} \equiv 1 (mod n),$ $2^{n - 1} \equiv 1 (mod n),$ the number $n$ $n$ is prime. However, there are exceptions: $561 = 3 \cdot 11 \cdot 17$ $561 = 3 \cdot 11 \cdot 17$ is composite but $2^{560} \equiv 1 (mod 561) .$ $2^{560} \equiv 1 (mod 561) .$ We can see this as follows: Since $560 \equiv 0 (mod 2),$ $560 \equiv 0 (mod 2),$ we have $2^{560} \equiv 2^{0} \equiv 1 (mod 3) .$ $2^{560} \equiv 2^{0} \equiv 1 (mod 3) .$ Similarly, since $560 \equiv 0 (mod 10)$ $560 \equiv 0 (mod 10)$ and $560 \equiv 0 (mod 16),$ $560 \equiv 0 (mod 16),$ we can conclude that $2^{560} \equiv 1 (mod 11)$ $2^{560} \equiv 1 (mod 11)$ and $2^{560} \equiv 1 (mod 17) .$ $2^{560} \equiv 1 (mod 17) .$ Putting things together via the Chinese remainder theorem, we find that $2^{560} \equiv 1 (mod 561) .$ $2^{560} \equiv 1 (mod 561) .$

Another such exception is $1729 = 7 \cdot 13 \cdot 19 .$ $1729 = 7 \cdot 13 \cdot 19 .$ However, these exceptions are fairly rare in practice. Therefore, if $2^{n - 1} \equiv 1 (mod n),$ $2^{n - 1} \equiv 1 (mod n),$ it is quite likely that $n$ $n$ is prime. Of course, if $2^{n - 1} \equiv 1 (mod n),$ $2^{n - 1} \equiv 1 (mod n),$ then $n$ $n$ cannot be prime.

Since $2^{n - 1} (mod n)$ $2^{n - 1} (mod n)$ can be evaluated very quickly (see Section 3.5), this gives a way to search for prime numbers. Namely, choose a starting point $n_{0}$ $n_{0}$ and successively test each odd number $n \geq n_{0}$ $n \geq n_{0}$ to see whether $2^{n - 1} \equiv 1 (mod n) .$ $2^{n - 1} \equiv 1 (mod n) .$ If $n$ $n$ fails the test, discard it and proceed to the next $n .$ $n .$ When an $n$ $n$ passes the test, use more sophisticated techniques (see Section 9.3) to test $n$ $n$ for primality. The advantage is that this procedure is much faster than trying to factor each $n,$ $n,$ especially since it eliminates many $n$ $n$ quickly. Of course, there are ways to speed up the search, for example, by first eliminating any $n$ $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 $n_{0}$ $n_{0}$ as a starting point. Successively, for each odd integer $n \geq n_{0},$ $n \geq n_{0},$ compute $2^{n - 1} (mod n)$ $2^{n - 1} (mod n)$ by the modular exponentiation technique of Section 3.5. If $2^{n - 1} \equiv 1 (mod n),$ $2^{n - 1} \equiv 1 (mod n),$ Fermat’s theorem guarantees that $n$ $n$ is not prime. This will probably throw out all the composites encountered. When you find an $n$ $n$ with $2^{n - 1} \equiv 1 (mod n),$ $2^{n - 1} \equiv 1 (mod n),$ you probably have a prime number. But how many $n$ $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 \times 10^{297},$ $1.4 \times 10^{297},$ 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 .$ $n .$ Let $ϕ (n)$ $ϕ (n)$ be the number of integers $1 \leq a \leq n$ $1 \leq a \leq n$ such that $gcd (a, n) = 1 .$ $gcd (a, n) = 1 .$ For example, if $n = 10,$ $n = 10,$ then there are four such integers, namely 1,3,7,9. Therefore, $ϕ (10) = 4 .$ $ϕ (10) = 4 .$ Often $ϕ$ $ϕ$ is called Euler’s $ϕ$ $ϕ$ -function.

If $p$ $p$ is a prime and $n = p^{r},$ $n = p^{r},$ then we must remove every $p$ $p$ th number in order to get the list of $a$ $a$ ’s with $gcd (a, n) = 1,$ $gcd (a, n) = 1,$ which yields

ϕ (p^{r}) = (1 - \frac{1}{p}) p^{r} .

$ϕ (p^{r}) = (1 - \frac{1}{p}) p^{r} .$

In particular,

ϕ (p) = p - 1.

$ϕ (p) = p - 1.$

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

ϕ (n) = n \prod_{p | n} (1 - \frac{1}{p}),

$ϕ (n) = n \prod_{p | n} (1 - \frac{1}{p}),$

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

ϕ (p q) = (p - 1) (q - 1) .

$ϕ (p q) = (p - 1) (q - 1) .$

Examples

ϕ (10) = (2 - 1) (5 - 1) = 4,

$ϕ (10) = (2 - 1) (5 - 1) = 4,$

ϕ (120) = 120 (1 - \frac{1}{2}) (1 - \frac{1}{3}) (1 - \frac{1}{5}) = 32

$ϕ (120) = 120 (1 - \frac{1}{2}) (1 - \frac{1}{3}) (1 - \frac{1}{5}) = 32$

Euler’s Theorem

If $gcd (a, n) = 1,$ $gcd (a, n) = 1,$ then

\begin{matrix} a^{ϕ (n)} \equiv 1 & (mod n) . \end{matrix}

$\begin{matrix} a^{ϕ (n)} \equiv 1 & (mod n) . \end{matrix}$

Proof. The proof of this theorem is almost the same as the one given for Fermat’s theorem. Let $S$ $S$ be the set of integers $1 \leq x \leq n$ $1 \leq x \leq n$ with $gcd (x, n) = 1 .$ $gcd (x, n) = 1 .$ Let $ψ : S \to S$ $ψ : S \to S$ be defined by $ψ (x) \equiv a x (mod n) .$ $ψ (x) \equiv a x (mod n) .$ As in the proof of Fermat’s theorem, the numbers $ψ (x)$ $ψ (x)$ for $x \in S$ $x \in S$ are the numbers in $S$ $S$ written in some order. Therefore,

\prod_{x \in S} x \equiv \prod_{x \in S} ψ (x) \equiv a^{ϕ (n)} \prod_{x \in S} x .

$\prod_{x \in S} x \equiv \prod_{x \in S} ψ (x) \equiv a^{ϕ (n)} \prod_{x \in S} x .$

Dividing out the factors $x \in S,$ $x \in S,$ we are left with $1 \equiv a^{ϕ (n)} (mod n) .$ $1 \equiv a^{ϕ (n)} (mod n) .$

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

Example

What are the last three digits of $7^{803}$ $7^{803}$ ?

SOLUTION

Knowing the last three digits is the same as working mod 1000. Since $ϕ (1000) = 1000 (1 - \frac{1}{2}) (1 - \frac{1}{5}) = 400,$ $ϕ (1000) = 1000 (1 - \frac{1}{2}) (1 - \frac{1}{5}) = 400,$ we have $7^{803} = (7^{400})^{2} 7^{3} \equiv 7^{3} \equiv 343 (mod 1000) .$ $7^{803} = (7^{400})^{2} 7^{3} \equiv 7^{3} \equiv 343 (mod 1000) .$ Therefore, the last three digits are 343.

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

Example

Compute $2^{43210} (mod 101) .$ $2^{43210} (mod 101) .$

SOLUTION

Note that 101 is prime. From Fermat’s theorem, we know that $2^{100} \equiv 1 (mod 101) .$ $2^{100} \equiv 1 (mod 101) .$ Therefore,

\begin{matrix} 2^{43210} \equiv {(2^{100})}^{432} 2^{10} \equiv 1^{432} 2^{10} \equiv 1024 \equiv 14 & (mod 101) . \end{matrix}

$\begin{matrix} 2^{43210} \equiv {(2^{100})}^{432} 2^{10} \equiv 1^{432} 2^{10} \equiv 1024 \equiv 14 & (mod 101) . \end{matrix}$

In this case, we were able to change the exponent 43210 to 10 because $43210 \equiv 10 (mod 100) .$ $43210 \equiv 10 (mod 100) .$

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

Basic Principle

Let $a, n, x, y$ $a, n, x, y$ be integers with $n \geq 1$ $n \geq 1$ and $gcd (a, n) = 1 .$ $gcd (a, n) = 1 .$ If $x \equiv y (mod ϕ (n)),$ $x \equiv y (mod ϕ (n)),$ then $a^{x} \equiv a^{y} (mod n) .$ $a^{x} \equiv a^{y} (mod n) .$ In other words, if you want to work mod $n,$ $n,$ you should work mod $ϕ (n)$ $ϕ (n)$ in the exponent.

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

\begin{matrix} a^{x} = a^{y + ϕ (n) k} = a^{y} {(a^{ϕ (n)})}^{k} \equiv a^{y} 1^{k} \equiv a^{y} & (mod n) . \end{matrix}

$\begin{matrix} a^{x} = a^{y + ϕ (n) k} = a^{y} {(a^{ϕ (n)})}^{k} \equiv a^{y} 1^{k} \equiv a^{y} & (mod n) . \end{matrix}$

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)$ $400 = ϕ (1000)$ and mod $100$ $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$ $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$ $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 .$ $K .$

Here is the mathematical realization of the method. First, Alice chooses a large prime number $p$ $p$ that is large enough to represent the key $K .$ $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$ $p$ so that Bob (or anyone else) can download it. Bob downloads $p .$ $p .$ Alice and Bob now do the following:

Alice selects a random number $a$ $a$ with $gcd (a, p - 1) = 1$ $gcd (a, p - 1) = 1$ and Bob selects a random number $b$ $b$ with $gcd (b, p - 1) = 1 .$ $gcd (b, p - 1) = 1 .$ We will denote by $a^{- 1}$ $a^{- 1}$ and $b^{- 1}$ $b^{- 1}$ the inverses of $a$ $a$ and $b$ $b$ mod $p - 1 .$ $p - 1 .$
Alice sends $K_{1} \equiv K^{a} (mod p)$ $K_{1} \equiv K^{a} (mod p)$ to Bob.
Bob sends $K_{2} \equiv K_{1}^{b} (mod p)$ $K_{2} \equiv K_{1}^{b} (mod p)$ to Alice.
Alice sends $K_{3} \equiv K_{2}^{a^{- 1}} (mod p)$ $K_{3} \equiv K_{2}^{a^{- 1}} (mod p)$ to Bob.
Bob computes $K \equiv K_{3}^{b^{- 1}} (mod p) .$ $K \equiv K_{3}^{b^{- 1}} (mod p) .$

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

The reason this works is that Bob has computed $K^{a b a^{- 1} b^{- 1}} (mod p) .$ $K^{a b a^{- 1} b^{- 1}} (mod p) .$ Since $a a^{- 1} \equiv b b^{- 1} \equiv 1 (mod p - 1),$ $a a^{- 1} \equiv b b^{- 1} \equiv 1 (mod p - 1),$ the Basic Principle implies that $K^{a b a^{- 1} b^{- 1}} \equiv K^{1} \equiv K (mod p) .$ $K^{a b a^{- 1} b^{- 1}} \equiv K^{1} \equiv K (mod p) .$

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).

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for 3.6 Fermat&#8217;s Theorem and Euler&#8217;s TheoremFermat’s Theorem and Euler’s Theorem

Create new playlist

Sign In

Sign Up

Table of Contents for
3.6 Fermat’s Theorem and Euler’s TheoremFermat’s Theorem and Euler’s Theorem