Fermat's and Euler's Theorems
Two theorems that play important roles in public-key
cryptography are Fermat's theorem and Euler's theorem.
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
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