Section 8.2. Fermat s and Euler s Theorems


[Page 238 (continued)]

8.2. Fermat's and Euler's Theorems

Two theorems that play important roles in public-key cryptography are Fermat's theorem and Euler's theorem.


[Page 239]

Fermat's Theorem[4]

[4] This is sometimes referred to as Fermat's little theorem.

Fermat's theorem states the following: If p is prime and a is a positive integer not divisible by p, then

Equation 8-2


Proof: Consider the set of positive integers less than p:{1,2,..., p 1} and multiply each element by a, modulo p, to get the set X = {a mod p, 2a mod p, . . . (p 1)a mod p}. None of the elements of X is equal to zero because p does not divide a. Furthermore no two of the integers in X are equal. To see this, assume that ja p) where 1 p 1. Because [5] to p, we can eliminate a from both sides of the equation [see Equation (4.3)] resulting in: j p). This last equality is impossible because j and k are both positive integers less than p. Therefore, we know that the (p 1) elements of X are all positive integers, with no two elements equal. We can conclude the X consists of the set of integers {1,2,..., p 1} in some order. Multiplying the numbers in both sets and taking the result mod p yields

[5] Recall from Chapter 4 that two numbers are relatively prime if they have no prime factors in common; that is, their only common divisor is 1. This is equivalent to saying that two numbers are relatively prime if their greatest common divisor is 1.

a x 2a x ... x (p 1) [(1 x 2 x ... x (p)

ap1(p 1)! (p)

We can cancel the (p 1)! term because it is relatively prime to p [see Equation (4.3)]. This yields Equation (8.2).

a = 7, p = 19

72 = 49 11(mod 19)

74 121 7(mod 19)

78 49 7(mod 19)

716 121 7(mod 19)

ap1 = 718 = 716 x 72 7 x 11 1(mod 19)


An alternative form of Fermat's theorem is also useful: If p is prime and a is a positive integer, then

Equation 8-3


Note that the first form of the theorem [Equation (8.2)] requires that a be relatively prime to p, but this form does not.

p = 5,a = 3

ap = 35 = 243 3(mod 5) = p)

p = 5, a = 10

ap = 105 = 100000 10(mod 5) = 0(mod 5) = p)



[Page 240]

Euler's Totient Function

Before presenting Euler's theorem, we need to introduce an important quantity in number theory, referred to as Euler's totient function and written f(n), defined as the number of positive integers less than n and relatively prime to n. By convention, f(1) = 1.

Determine f(37) and f(35).

Because 37 is prime, all of the positive integers from 1 through 36 are relatively prime to 37. Thus f(37) = 36.

To determine f(35), we list all of the positive integers less than 35 that are relatively prime to it:

1, 2, 3, 4, 6, 8, 9, 11, 12, 13, 16, 17, 18,

19, 22, 23, 24, 26, 27, 29, 31, 32, 33, 34.

There are 24 numbers on the list, so f(35) = 24.


Table 8.2 lists the first 30 values of f(n). The value f(1) is without meaning but is defined to have the value 1.

Table 8.2. Some Values of Euler's Totient Function f(n)

n

f(n)

1

1

2

1

3

2

4

2

5

4

6

2

7

6

8

4

9

6

10

4

11

10

12

4

13

12

14

6

15

8

16

8

17

16

18

6

19

18

20

8

21

12

22

10

23

22

24

8

25

20

26

12

27

18

28

12

29

28

30

8


It should be clear that for a prime number p,

f(p) = p 1

Now suppose that we have two prime numbers p and q, with p n = pq,

f(n) = f(pq) = f(p) x f(q) = (p 1) x (q x 1)

To see that f(n) = f(p) x f(q), consider that the set of positive integers less that n is the set {1,..., (pq 1)}. The integers in this set that are not relatively prime to n are the set {p,2 p,..., (q 1)p} and the set {q,2q,..., (p 1)q} Accordingly,


[Page 241]

f(n) = (pq 1) [(q 1) + (p 1)]

= pq (p + q) + 1

= (p 1) x (q 1)

= f(p) x f(q)

f(21) = f(3) x f(7) = (3 1) x (7 1) = 2 x 6 = 12

where the 12 integers are {1,2,4,5,8,10,11,13,16,17,19,20}


Euler's Theorem

Euler's theorem states that for every a and n that are relatively prime:

Equation 8-4


a = 3; n = 10; f(10) = 4

af(n) = 34 = 81 1(mod 10) = 1 (mod

a = 2; n = 11; f(11) = 10

af(n) = 210 = 1024 1(mod 11) = 1 (mod Proof: Equation (8.4) is true if n is prime, because in that case f(n) = (n 1) and Fermat's theorem holds. However, it also holds for any integer n. Recall that f(n) is the number of positive integers less than n that are relatively prime to n. Consider the set of such integers, labeled as follows:

R {x1, x2,..., xf(n)}

That is, each element xi of R is a unique positive integer less than n with gcd(xi, n) = 1. Now multiply each element by a, modulo n:

S = {(ax1 mod n), (ax2 mod n),..., (axf(n) mod n)}

The set S is a permutation of R, by the following line of reasoning:

  1. Because a is relatively prime to n and xi is relatively prime to n, axi must also be relatively prime to n. Thus, all the members of S are integers that are less than n and that are relatively prime to n.

  2. There are no duplicates in S. Refer to Equation (4.3). If axi mod n = axj mod n then xi = xj.

Therefore,



[Page 242]


This is the same line of reasoning applied to the proof of Fermat's theorem. As is the case for Fermat's theorem, an alternative form of the theorem is also useful:

Equation 8-5


Again, similar to the case with Fermat's theorem, the first form of Euler's theorem [Equation (8.4)] requires that a be relatively prime to n, but this form does not.




Cryptography and Network Security Principles and Practices
Cryptography and Network Security (4th Edition)
ISBN: 0131873164
EAN: 2147483647
Year: 2005
Pages: 209

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net