Great Theoretical Ideas In Computer Science Anupam Gupta Lecture 12 CS 15 251 Oct 6 2005 Fall 2005 Carnegie Mellon University Ancient Wisdom Primes Continued Fractions The Golden Ratio and Euclid s GCD 3 13 3 2 3 1 1 1 3 1 3 1 3 1 3 1 3 1 3 1 3 3 Definition A number 1 is prime if it has no other factors besides 1 and itself Each number can be factored into primes in a unique way Euclid Theorem Each natural has a unique factorization into primes written in non decreasing order Definition A number 1 is prime if it has no other factors besides 1 and itself Primes 2 3 5 7 11 13 17 Factorizations 42 2 3 7 84 2 2 3 7 13 13 Multiplication might just be a one way function Multiplication is fast to compute Reverse multiplication is apparently slow We have a feasible method to multiply 1000 bit numbers Egyptian multiplication Factoring the product of two random 1000 bit primes has no known feasible approach Grade School GCD algorithm GCD A B is the greatest common divisor i e the largest number that goes evenly into both A and B What is the GCD of 12 and 18 12 22 3 18 2 32 Common factors 21 and 31 Answer 6 How to find GCD A B A Na ve method Factor A into prime powers Factor B into prime powers Create GCD by multiplying together each common prime raised to the highest power that goes into both A and B Hang on This requires factoring A and B No one knows a particularly fast way to factor numbers in general EUCLID had a much better way to compute GCD Ancient Recursion Euclid s GCD algorithm Euclid A B If B 0 then return A else return Euclid B A mod B A small example Euclid A B If B 0 then return A else return Euclid B A mod B Note GCD 67 29 1 Euclid 67 29 Euclid 29 9 Euclid 9 2 Euclid 2 1 0 67 mod 29 9 29 mod 9 2 9 mod 2 1 2 mod 1 Important questions to ask Is the algorithm correct Does the algorithm stop How many steps does the algorithm run for But is it correct Euclid A B If B 0 then return A else return Euclid B A mod B Claim GCD A B GCD B A mod B But is it correct Euclid A B If B 0 then return A else return Euclid B A mod B Claim GCD A B GCD B A mod B value of GCD is an invariant But is it correct Euclid A B If B 0 then return A else return Euclid B A mod B Claim GCD A B GCD B A mod B d A and d B d A kB The set of common divisors of A B equals the set of common divisors of B A kB Does the algorithm stop Euclid A B If B 0 then return A else return Euclid B A mod B Claim After first step A B 0 Does the algorithm stop Euclid A B If B 0 then return A else return Euclid B A mod B Claim A mod B A Proof If B A then A mod B A B A If B A then any X Mod B B A If B A then A mod B 0 Does the algorithm stop Euclid A B If B 0 then return A else return Euclid B A mod B GCD A B calls GCD B A mod B Less than of A Euclid s GCD Termination Euclid A B If B 0 then return A else return Euclid B A mod B GCD A B calls GCD B A Euclid s GCD Termination Euclid A B If B 0 then return A else return Euclid B A mod B GCD A B calls GCD B A which calls GCD A B mod A Less than of A Euclid s GCD Termination Euclid A B If B 0 then return A else return Euclid B A mod B Every two recursive calls the input numbers drop by half Euclid s GCD Termination Euclid A B If B 0 then return A else return Euclid B A mod B Theorem If two input numbers have an n bit binary representation Euclid s Algorithm will not take more than 2n calls to terminate Important questions to ask Is the algorithm correct Does the algorithm stop How many steps does the algorithm run for Trick Question If X and Y are less than n what is a reasonable upper bound on the number of recursive calls that Euclid X Y will make Answer If X and Y are less than n Euclid X Y will make no more than 2log2n calls Euclid A B If B 0 then return A else return Euclid B A mod B Euclid 67 29 Euclid 29 9 Euclid 9 2 Euclid 2 1 Euclid 1 0 outputs 1 67 2 29 67 mod 29 9 29 3 9 29 mod 9 2 9 4 2 9 mod 2 1 2 2 1 2 mod 1 0 Let r s denote the number r 67 s 29 Calculate all intermediate values in this representation 67 1 0 Euclid 67 29 1 2 Euclid 29 9 2 3 7 Euclid 9 2 1 13 30 Euclid 2 1 29 67 29 0 1 9 1 0 2 0 1 9 2 0 1 3 1 2 1 1 2 4 3 7 0 3 7 2 13 30 0 Euclid s Extended GCD algorithm Input X Y Output r s d such that rX sY d GCD X Y 29 0 1 Euclid 67 29 Euclid 29 9 Euclid 9 2 Euclid 2 1 67 1 0 9 67 2 29 9 1 2 2 29 3 9 2 3 7 1 9 4 2 1 13 30 0 2 2 1 0 29 67 Euclid 1 0 outputs 1 13 67 30 29 The multiplicative inverse of y 2 Zn is the unique z 2 Zn such that y n z n 1 The unique inverse of a must exist because the y row contains a permutation of the elements and hence contains a unique 1 Z5 1 z 3 4 1 1 2 3 4 2 2 4 1 3 y 3 1 4 2 4 4 3 2 1 The multiplicative inverse of y 2 Zn is the unique z 2 Zn such that y n z n 1 To quickly compute the inverse of y Run ExtendedEuclid x n returns a b and d such that ay bn d But d GCD y n 1 so ay bn 1 Hence ay 1 mod n Thus a is the multiplicative inverse of y The RSA story Pick 2 distinct random 1000 bit primes p and q Multiply them to get n p q Multiply p 1 and q 1 to compute n Randomly pick an e s t GCD e …
View Full Document
Unlocking...