6.857 Computer and Network Security September 26, 2002Lecture Notes 7 : More Number TheoryLecturer: Ron Rivest Scribe: Bailey/Cholankeril/Kwon/Zitser[These notes come from Fall 2001. Check with students’ notes for new topics brought up in 2002.]1 Outline:• Erratum• GCD & Modular Inverses• Order & Generators & Discrete Log Problem2 ErratumIn the previous lecture, there was a small error in the definition of a Carmichael number. Thecorrected definition is as follows:Definition (corrected): An integer n > 1 is a Carmichael number if,an−1≡ 1(mod n)∀a, 1 ≤ a < n, s.t. gcd(a, n) = 1Question: Are there any proofs on the density of Carmichael numbers?Answer: Yes. There are some bounds on the density of Carmichael numbers. These numbers arevery rare, annoying obstacles.3 GCD, Modular InversesDefinition 1 d | a (“d divides a”) if ∃k s.t. a = kdFact 1 ∀d, d | 0. This includes 0 | 0. If a 6= 0, then 0 6 | aDefinition 2 A divisor of an integer a is any d ≥ 0 s.t. d | aDefinition 3 If d is a divisor of a and also of b, then d is a common divisor of a and b.0May be freely reproduced for educational or personal use.12 3 GCD, MODULAR INVERSESExample 1 7 is a common divisor of 14 and 77.Definition 4 The greatest common divisor, gcd(a, b), of two integers a and b is the largest of theircommon divisors. (But gcd(0, 0) = 0 by definition.)gcd(0, 5) = 5gcd(24, 30) = 6gcd(4, 7) = 1Question: How are GCD’s defined when negative numbers are involved?Answer: They are defined the same way they are defined for positive numbers.Question: And what are the divisors of a negative number?Answer: By the definition of divisibility, a | n implies a | −n, so negative numbers are consideredto be divisible by the same numbers their positive counterparts are divisible by.Definition 5 Integers a and b are relatively prime if gcd(a, b) = 1.Fact 2 If p is prime and 1 ≤ a < p, then gcd(a, p) = 1.Fact 3 It is easy to compute gcd(a, b). This is surprising because you might think that in order tocompute the GCD of a and b you would need to figure out their divisors, i.e. solve the factoringproblem. But, as you will see, we don’t need to figure out the divisors of a and b to find their GCD.3.1 Euclid’s AlgorithmEuclid’s Algorithm is probably one of the world’s oldest computing algorithms. It allows us to easilycalculate the greatest common divisor of any two integers a and b. The algorithm is illustratedbelow:Assume a ≥ 0, b ≥ 0gcd(a, b) =a if b = 0gcd(b, a mod b) otherwiseExample 2 Using Euclid’s Algorithm, find the greatest common divisor of 12 and 33.gcd(12, 33) = gcd(33, 12)= gcd(12, 9)= gcd(9, 3)= gcd(3, 0)= 3Question: Why does Euclid’s algorithm always terminate?Answer: a mod b is always less than b. Hence, on each recursive call, the second argument isstrictly less than it was on the previous call.3Theorem 1 The time to compute gcd(a, b) is O(log b).Proof: See CLRS, Chapter 31.Intuitive Proof:In a typical scenario, gcd(b, a mod b) is about b/2. If we imagine b to be to be expressed in bits, thisis equivalent to taking one bit off of b. So the order of execution will be roughly log b. The actualworst case is for a pair of fibonnaci numbers; they decrease by the golden ration on each iteration.Theorem 2 (∀a, b), ∃x, y s.t. ax + by = gcd(a, b) where x, y are integers.Proof: By example, (Euclid’s Extended Algorithm)gcd(12, 33) 33 = 1 ∗ 33gcd(33, 12) 12 = 1 ∗ 12gcd(12, 9) 9 = 1 ∗ 33 − 2 ∗ 12gcd(9, 3) 3 = 3 ∗ 12 − 1 ∗ 333 and -1 are the values of x and y that satisfy the statement: ∀a,bit is true that gcd(a, b) = ax + byfor some pair of integers x, y.Corollary 1 It is easy to find such x and y. The method used to find x and y s.t. ax+by = gcd(a, b)is called Euclid’s Extended Algorithm.Corollary 2 Given prime p and a where 1 ≤ a < p, it is easy to find an x s.t. ax ≡ 1(mod p) [i.e.x = a−1(mod p)]. Or equivalently, ax + py = 1Fact 4 The above works even if p is not prime, as long as gcd(a, p) = 1.4 Orders & Generators & DLPBy Fermat’s Theorem, ap−1≡ 1(mod p) if p is prime and a 6≡ 0(mod p).Definition 6 The least positive x s.t. ax≡ 1(mod p) is called the order of a, mod p.Theorem 3 - LagrangeThe order of any element a, modulo p (where p is prime and a 6≡ 0mod p) is a divisor of p − 1.Proof: See CLRS, Chapter 31.Example 3 Calculate the orders of various elements modulo 7p = 7 and p-1 = 6. The divisors of 6 are 1, 2, 3, 6. So all of the numbers in Z∗7must have order1, 2, 3, or 6 modulo 7.4 4 ORDERS & GENERATORS & DLPa ∈ Z∗pa2a3a4a5a6order(a)6 62= 1 63= 6 1 6 1 22 4 1 2 4 1 33 2 6 4 5 1 6Definition 7 g is a generator of Z∗pif the order of g mod p is equal to p − 1.Question: Can generators of groups be even?Answer: Yes. But there aren’t any modulo 7. If you play around with primes other than 7, youshould be able to find even generators.Theorem 4 If p is prime, then ∃g s.t. g is a generator mod p.Fact 5 If p is prime and g is a generator mod p, then for every y in Z∗p(i.e. in {1, 2, . . . , p − 1})∃ a unique x(0 ≤ x < p − 1) s.t. gx≡ y(mod p)Definition 8 In the above theorem, x is called the discrete logarithm of y modulo p, base gTheorem 5 If p is prime, then g is a generator mod p iff g(p−1)/q6≡ 1(mod p) for every prime qdividing p − 1Question: How many generators exist for Z∗p?Answer: Enough to sample and find one efficiently. It’s like finding a prime. We need to testwhether a candidate number is a generator.Question: How do we find generators for numbers mod a large prime? Does this require knowingALL of the prime factors of p − 1?Answer: Rather than trying to find all q for a prime p to determine the generator g, we can takea different approach and pick our prime p, s.t. the factorization of p − 1 is known, allowing us toeasily find the generator g.Idea: Let factorization of p − 1 be known (e.g., p − 1 = 2 ∗ q, where q is prime).Pick g at random. Test g(p−1)/26≡ 1(mod p) &g(p−1)/q6≡ 1(mod p) → g is a generator mod p,otherwise pick another g.There are lots of generators, so this works. Yields p, g where p is prime and g is a generator mod p.4.1 Discrete Logarithm ProblemGiven a prime pa generator g mod pa value y ∈ Z∗pFindx s.t. y = gx(mod p)4.1 Discrete Logarithm Problem 5The discrete logarithm problem is believed to be computationally infeasible if p is large (e.g., …
View Full Document
Unlocking...