15 251 Great Theoretical Ideas in Computer Science Randomness and Computation Lecture 16 October 16 2008 Super simple and powerful idea Drawing balls at random You have a bucket with n balls there are n 100 green balls good the remaining are red bad What is the probability of drawing a good ball if you draw a random ball from the bucket Now if you draw balls from the bucket at random with replacement how many draws until you draw a good ball Drawing balls at random You have a bucket with n balls there are k green balls good the remaining are red bad Probability of getting a good ball k n Expected number of draws until a good ball n k even simpler idea Repeated experiments Suppose you run a random experiment that fails with probability independent of the past What is the probability that you succeed in k steps 1 probability you fail in all k steps 1 k If probability of failure was at most then probability of success at least once in k steps is at least 1 k the following trivial question Representing numbers Question Given two numbers a and b both n how long does it take to add them together a n b n c log n d 2n Representing the number n takes log n bits Representing numbers Suppose I want to sell you for 1M an algorithm that takes as input a number n and factors them in n time should you accept my offer Factoring fast breaking RSA Finally remember this bit of algebra The Fundamental theorem of Algebra A root of a polynomial p x is a value r such that p r 0 If p x is a polynomial of degree d how many roots can it have At most d How to check your work 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 have degree n requires n2 mults by elementary school algorithms or can do faster with fancy techniques like the Fast Fourier transform Can we check if p x q x r x more Idea Evaluate on Random Inputs Let f x p x q x r x Is f zero everywhere Idea Evaluate f on a random input z If we get nonzero f z clearly f is not zero If we get f z 0 this is weak 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 Say S 1 2 4n 2 Select value z uniformly at random from S 3 Evaluate f z p z q z r z 4 If f z 0 output possibly equal otherwise output not equal Equality checking by random evaluation What is the probability the algorithm outputs not equal when in fact f 0 Zero If p x q x r x always correct Equality checking by random evaluation What is the probability the algorithm outputs maybe equal when in fact f 0 Let A z z is a root of f Recall that A degree of f 2n Therefore P picked a root 2n 4n 1 2 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 picked root k times 2 This idea can be used for testing equality of lots of different types of functions Random Fingerprinting Find a small random fingerprint of a large object e g the value f z of a polynomial at a point z This fingerprint captures the essential information about the larger object if two large objects are different their fingerprints are usually different 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 I guess Earth X How do we quickly check for accuracy More soon Moon Y How do you pick a random 1000 bit prime Picking A Random Prime Pick a random 1000 bit prime Strategy 1 Generate random 1000 bit number 2 Test each one for primality more on this later in the lecture 3 Repeat until you find a prime How many retries until we succeed Recall the balls from bucket experiment If n number of 1000 bit numbers 21000 and k number of primes in 0 21000 1 then E number of rounds n k Question How many primes are there between 1 and n approximately Let n be the number of primes between 1 and n Legendre I wonder how fast n grows Conjecture 1790s p n lim 1 n n ln n Gauss Their estimates x pi x Gauss Li Legendre x log x 1 1000 168 178 172 169 10000 1229 1246 1231 1218 100000 9592 9630 9588 9512 1000000 78498 78628 78534 78030 10000000 664579 664918 665138 661459 100000000 5761455 5762209 5769341 5740304 1000000000 50847534 50849235 50917519 50701542 10000000000 45505251 1 455055614 455743004 454011971 De la Vall e Poussin J S Hadamard Two independent proofs of the Prime Density Theorem 1896 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 still unproven Riemann The Prime Density Theorem p n lim 1 n n ln n Slightly easier to show n n 1 2 logn In other words at least 1 2B of all B bit numbers are prime So for this algo Pick a random 1000 bit prime Strategy 1 Generate random 1000 bit number 2 Test each one for primality more on this later in the lecture 3 Repeat until you find a prime the facts are these If we re picking 1000 bit numbers number of numbers is n 21000 number of primes is k n 2 log n Hence expected number of trials before we get a prime number n k 2 log n Moral of the story Picking a random B bit prime is almost as easy as picking a random B bit number Need to try at most 2 log B times in expectation Provided we can check for primality More on this later 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 Are X and Y the same N bit numbers p random 2logN bit prime Send p X mod p Answer to X Y mod p Earth X Moon Y Why is this any good Easy case If X Y then X Y mod p Why is this any good Harder case What if X Y We mess up if p X Y Define …
View Full Document
Unlocking...