Great Theoretical Ideas In Computer Science Steven Rudich John Lafferty Lecture 22 Nov 9 2005 CS 15 251 Fall 2005 Carnegie Mellon University Randomness and Computation Some Prime Examples Checking Our Work Suppose we want to check p x q x r x where p q and r are three polynomials x 1 x3 x2 x 1 x4 1 If the polynomials are long this requires O n2 work by elementary school algorithms or O n log n work with fancy techniques like the Fast Fourier transform Can we check if p x q x r x more efficiently Great Idea Evaluating on Random Inputs Let f x p x q x r x Is f zero Idea Evaluate f on a random input z If we get f z 0 this is evidence that f is zero everywhere If f x is a degree 2n polynomial it can only have 2n roots We re unlikely to guess one of these by chance Equality checking by random evaluation 1 Choose sample space S z1 z2 zm with arbitrary points zi for m 2n 2 Select z from S with probability 1 m 3 Evaluate p z q z r z f z 4 If f z 0 output equal otherwise output not equal Equality checking by random evaluation What is the probability the algorithm outputs correct when in fact f 0 Let A z z is a root of f Then A 2n Therefore P A 2n m We take to be small Equality checking by random evaluation By repeating this procedure k times we are fooled by the event f z1 f z2 f zk 0 when actually f x 0 with probability no bigger than P A 2n k mk k Wow That idea could be used for testing equality of lots of different types of functions Yes It s a very powerful technique For example a matrix is just a special kind of function Suppose we do a matrix multiplication of two nxn matrices AB C The idea of random evaluation can be used to efficiently check the Just evaluate the function C on a random input vector r In fact we can take r to be a random bit vector r 1 0 0 1 0 T So to test if AB C we compute x Br y Ax and z Cr If y z we take this as evidence that the calculation was correct The amount of work is only O n2 Claim If AB C and r is a random n bit vector then Pr ABr Cr So if a complicated fancy algorithm is used to compute AB in time O n2 it can be efficiently checked with only O n2 extra work using randomness Earth has huge file X that she transferred to Moon Moon gets Y Did you get that file ok Was the transmission accurate Uh yeah EARTH X MOON Y Let n be the number of primes between 1 and n I wonder how fast n grows Conjecture 1750 p n lim 1 n n ln n Eule Hadamard 1900 The Prime Density Theorem p n lim 1 n n ln n The Prime Density Theorem This theorem remains one of the celebrated achievements of number theory In fact an even sharper conjecture remains one of the great open problems of mathematics The Riemann Hypothesis 1859 p n n ln n lim 0 n n Riemann For EC on Homework The Theta Version Of The Prime Density Theorem n n ln n n n 1 ln n The probability that a randomly selected n bit number is prime is 1 n Explicitly n n 1 2logn Random logn bit number is a random number from 1 n n n 1 2logn means that a random logn bit number has at least a 1 2logn chance of being prime Random k bit number is a random number from 1 2k 2k 2k 1 2k means that a random k bit number has at least a 1 2k chance of being prime A random k bit number has at least a 1 2k chance of being prime A random k bit number has at least a 1 2k chance of being prime Hence if we pick 2k random k bit numbers the expected number of primes on the list is 1 Picking A Random Prime Many modern cryptosystems e g RSA include the instructions Pick a uniformly chosen n bit prime How can this be done efficiently Picking A Random Prime Pick a uniformly chosen n bit prime Strategy 1 Generate random n bit numbers 2 Test each one for primality more on this to later in the lecture Picking A Random Prime Pick a uniformly chosen n bit prime 1 Generate kn random n bit numbers Each trial has a 1 2n chance of being prime Probability that we get all composites 1 1 2n kn 1 1 2n 2n k 2 1 ek 2 Theorem Let X and Y be n bit numbers If X Y then at least half the 2logn bit primes p satisfy X Y mod p Theorem Let X and Y be distinct n bit numbers Let p be a random 2logn bit prime Prob X Y mod p 1 2 Are X and Y the same n bit numbers P random 2logn bit prime X mod p Answer to X Y mod p EARTH X MOON Y Are X and Y the same n bit numbers k random 2logn bit primes P1 P2 Pk X mod Pi for 1 i k k answers to X Y mod Pi EARTH X MOON Y If X Y Earth and Moon will always accept If X Y then Earth and Moon have a chance of catching it for each of k iterations If X Y Prob X Y mod Pi for all i 1 2 k Picking A Random Prime Pick a uniformly chosen n bit prime 1 Generate random n bit numbers 2 Test each one for primality How can we test primality efficiently Primality Testing Trial Division On Input n Trial division up to n for k 2 to n do if k n then return n is not prime otherwise return n is prime O n logn 2 time if division is O logn 2 On input n trial division uses O n logn 2 time Is that efficient No The input length is logn Let k log n In terms of k we are using 2k 2 k2 time The time is EXPONENTIAL in the input length Do the primes have a polynomialtime decision algorithm Euclid gave us a fast GCD algorithm Surely he tried to give a faster primality test than trial division Euclid Euler and Gauss all failed In 2002 Agrawal Saxena and Kayal AKS gave a deterministic primality test that runs in time O n12 This was the first deterministic polynomial time algorithm that didn t depend on some unproven conjecture like the Riemann Hypothesis But so many cryptosystems like RSA and PGP use fast primality testing as part of their subroutine to generate a random n bit prime What is …
View Full Document
Unlocking...