Randomness and Computation: Some Prime ExamplesChecking Our WorkGreat Idea: Evaluating on Random InputsEquality checking by random evaluationSlide 5Slide 6PowerPoint PresentationSlide 8Slide 9Slide 10Earth has huge file X that she transferred to Moon. Moon gets Y.Slide 12Slide 13The Prime Density TheoremSlide 15Slide 16Slide 17Slide 18Slide 19Slide 20Picking A Random PrimeSlide 22Slide 23Slide 24Are X and Y the same n-bit numbers?Slide 26If 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.Slide 28Primality Testing: Trial Division On Input nSlide 30Do the primes have a polynomial-time 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!Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Carmichael NumbersSlide 49Slide 50Slide 51Slide 52Slide 53Randomness and Computation: Some Prime ExamplesGreat Theoretical Ideas In Computer Science(Steven Rudich) John Lafferty CS 15-251 Fall 2005Lecture 22 Nov. 9, 2005 Carnegie Mellon UniversityChecking Our WorkSuppose 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-1If 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 InputsLet 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 evaluation1. Choose sample space S={z1, z2,…, zm} with arbitrary points zi, for m=2n/ .2. Select z from S with probability 1/m3. Evaluate p(z) q(z) – r(z) = f(z)4. If f(z) = 0, output “equal” otherwise output “not equal”Equality checking by random evaluationWhat 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 evaluationBy repeating this procedure k times, we are “fooled” by the event f(z1) = f(z2) = … = f(zk) = 0 when actually f(x) 0with probability no bigger than P(A) (2n)k/mk = kWow! That idea could Wow! That idea could be used for testing be used for testing equality of lots of equality of lots of different types of different types of “functions”!“functions”!Yes! It’s a very powerful Yes! It’s a very powerful technique.technique.For example, a matrix is just a For example, a matrix is just a special kind of function. Suppose special kind of function. Suppose we do a matrix multiplication of we do a matrix multiplication of two two nxnnxn matrices: matrices: AB = CAB = CThe idea of random evaluation can The idea of random evaluation can be used to efficiently check the be used to efficiently check the calculation.calculation.Just evaluate the “function” C on a random Just evaluate the “function” C on a random input vector input vector rr. In fact, we can take . In fact, we can take rr to be to be a a randomrandom bit vector bit vector : : r=(1,0,0,1,…,0)r=(1,0,0,1,…,0)TTSo to test if So to test if AB = CAB = C we compute we compute x = Br, y = Ax, and z = Crx = Br, y = Ax, and z = CrIf If y = zy = z, we take this as evidence that the , we take this as evidence that the calculation was correct. The amount of calculation was correct. The amount of work is only O(nwork is only O(n22).).Claim: If AB Claim: If AB C and r is a random n-bit C and r is a random n-bit vector, then Pr(ABr = Cr) vector, then Pr(ABr = Cr) ½. ½.So, if a complicated, So, if a complicated, fancy algorithm is used fancy algorithm is used to compute AB in time to compute AB in time O(nO(n2+2+), it can be ), it can be efficiently checked with efficiently checked with only O(nonly O(n22) extra work, ) extra work, using randomness! using randomness!Earth has huge file X that she transferred to Moon. Moon gets Y.EARTH: XEARTH: XMOON: YMOON: YDid you get that file ok? Was Did you get that file ok? Was the transmission accurate?the transmission accurate?Uh, yeah.Uh, yeah.Let (n) be the number of primes between 1 and n. I wonder how fast (n) grows? Conjecture [1750]: ( )lim 1/ lnnnn np��=EulerThe Prime Density Theorem:Hadamard [1900]Hadamard [1900]( )lim 1/ lnnnn np��=The Prime Density TheoremThis 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] Riemann( ) / lnlim 0nn n nnp��-=For EC on Homework:For EC on Homework:The Theta Version Of The Prime The Theta Version Of The Prime Density Theorem:Density Theorem:(n) = (n) = (n / ln n)(n / ln n)(n)/n = (n)/n = (1/ ln n)(1/ ln n)The probability that a randomly The probability that a randomly selected n-bit number is prime is selected n-bit number is prime is (1/n). Explicitly, (1/n). Explicitly, (n) / n (n) / n ¸¸ 1/2logn1/2lognRandom Random lognlogn bit number is bit number is a random number from a random number from 1..n1..n(n) / n (n) / n ¸¸ 1/2 1/2lognlognmeans that a random means that a random lognlogn-bit number has at -bit number has at least a 1/2least a 1/2lognlogn chance of chance of being prime.being prime.Random Random kk bit number is a bit number is a random number from 1..random number from 1..22kk((22kk) / ) / 22kk ¸¸ 1/2 1/2kkmeans that a random means that a random kk-bit number has at least a -bit number has at least a 1/21/2kk chance of being chance of being prime.prime.A random A random kk-bit number has at -bit number has at least a 1/2least a 1/2kk chance chance of being prime.of being prime.A random A random kk-bit number has at least a -bit number has at least a 1/21/2kk chance of being prime. chance of being prime.Hence, if we pick 2k random k Hence, if we pick 2k random k bit numbers the bit numbers the expected number of primes expected number of primes on the list is on the list is ¸¸ 1
View Full Document