8.2. Fermat's and Euler's TheoremsTwo theorems that play important roles in public-key cryptography are Fermat's theorem and Euler's theorem. Fermat's Theorem[4]
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
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).
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.
Euler's Totient FunctionBefore 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.
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.
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, f(n) = (pq 1) [(q 1) + (p 1)] = pq (p + q) + 1 = (p 1) x (q 1) = f(p) x f(q)
Euler's TheoremEuler's theorem states that for every a and n that are relatively prime: Equation 8-4
Cryptography and Network Security (4th Edition) ISBN: 0131873164
EAN: 2147483647 Year: 2005
Pages: 209 Authors: William Stallings
flylib.com © 2008-2017. If you may any questions please contact us: flylib@qtcs.net |