Great Theoretical Ideas In Computer Science Steven Rudich CS 15 251 Spring 2005 Ancient Wisdom Carnegie Mellon University Primes Continued Fractions The Golden Ratio and Euclid s GCD Lecture 12 Feb 17 2005 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 Theorem Each natural has a unique factorization into primes written in non decreasing order Let n be the least counter example Hence n has at least two ways of being written as a product of primes n p1 p2 pk q1 q2 qt The p s must be totally different primes than the q s or else we could divide both sides by one of a common prime and get a smaller counter example Without loss of generality assume p 1 q1 Theorem Each natural has a unique factorization into primes written in non decreasing order Let n be the least counter example n p1 p2 pk q1 q2 qt p 1 q1 n p 1p1 p 1 q 1 1 q 1 m n p 1q1 n with since p1 hence 1 m Theorem Each natural has a unique factorization into primes written in non decreasing order Let n be the least counter example n p1 p2 pk q1 q2 qt p 1 q1 n p 1p1 p 1 q 1 1 q 1 m n p 1q1 n Notice m p1 p2 pk q1 q1 q2 qt p1 Thus p1 m and q1 m with since p1 hence 1 m Theorem Each natural has a unique factorization into primes written in non decreasing order Let n be the least counter example n p1 p2 pk q1 q2 qt p 1 q1 with n p 1p1 p 1 q 1 1 q 1 m n p 1q1 n Notice m p1 p2 pk q1 q1 q2 qt p1 since p1 hence 1 m Thus p1 m and q1 m By unique factorization of m p1q1 m Thus m p1q1z We have m n p1q1 p1 p2 pk q1 p1q1z Theorem Each natural has a unique factorization into primes written in non decreasing order Let n be the least counter example n p1 p2 pk q1 q2 qt n p 1 p1 p 1 q 1 1 m n p 1 q1 with p1 q1 since p1 q1 hence 1 m n Notice m p1 p2 pk q1 q1 q2 qt p1 Thus p1 m and q1 m By unique factorization of m p 1q1 m Thus m p1q1z We have m n p1q1 p1 p2 pk q1 p1q1z Dividing by p1 we obtain p2 pk q1 q1z p2 pk q1z q1 q1 z 1 q1 p2 pk Theorem Each natural has a unique factorization into primes written in non decreasing order Let n be the least counter example n p1 p2 pk q1 q2 qt n p1 p1 p 1 q1 1 m n p 1q1 with p1 q1 since p1 q1 hence 1 m n Notice m p1 p2 pk q1 q1 q2 qt p1 Thus p1 m and q1 m By unique factorization of m p 1q1 m Thus m p1q1z We have m n p1q1 p1 p2 pk q1 p1q1z Dividing by p1 we obtain p2 pk q1 q1z p2 pk q1z q1 q1 z 1 q1 p2 pk Now by unique factorization of p 2 pk q1 must be one of p2 pk But this contradicts the fact that the p s and q s are disjoint 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 requires A B 0 If B 0 then return A else return Euclid B A mod B A small example Euclid A B requires A B 0 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 But is it correct Euclid A B requires A B 0 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 requires A B 0 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 requires A B 0 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 requires A B 0 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 requires A B 0 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 requires A B 0 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 requires A B 0 If B 0 then return A else return Euclid B A mod B Theorem If two input numbers have an n bit …
View Full Document
Unlocking...