Thursday, 21 March 2013

Fermat's and Euler's Theorems


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 ka(mod p) where 1 j < k p 1. Because a is relatively prime[5] to p, we can eliminate a from both sides of the equation [see Equation (4.3)] resulting in: j k(mode 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 1)](mode p)
ap1(p 1)! (p 1)!(mod 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) = a(mod p)
p = 5, a = 10
ap = 105 = 100000 10(mod 5) = 0(mod 5) = a(mod p)

No comments:

Post a Comment