Primes and Probability. In this problem, you will use the following facts: (1) any integer can be uniquely factored into primes; (2) the number of primes less than any number m is (m/log m) (this is the prime number theorem). We will also make use of the following notation for integers r and y: 1) y means that a "divides y, which means that there is no remainder when you divide y by I. and 2) 1 = y (mod p) means that r and y have the same remainder when divided by p, or in other words, px - y). (a) Show that for any integer 1, x factors into at most log o unique primes. Hint: 2 is the smallest prime. (b) Let & be some positive integer and let p be a prime chosen uni- formly at random from all primes less than or equal to m. Use the prime number theorem to show that the probability that po is ((log x)(log m)/m). (c) Now let and y both be positive integers less than n, such that I + y, and let p be a prime chosen uniformly at ran- dom from all primes less than or equal to m. Using the pre- vious result, show that the probability that x = y (mod p) is ((log n) (log m)/m)). (d) If m = logn in the previous problem, then what is the prob- ability that x = y (mod p). Hint: If you're on the right track, you should be able to show that this probability is "small", i.e. it goes to 0 as n gets large. (e) Finally, show how to apply this result to the following problem. Alice and Bob both have large numbers u and y where u and y are both at most than n, for n a very large number. They want to check to see if their numbers are the same, but Alice does not want to have to send her entire number to Bob. What is an efficient randomized algorithm for Alice and Bob that has "small" probability of failure? How many bits does Alice need to send to Bob as a function of n, and what is the probability of failure, where failure means that this algorithm says r and y are equal, but in fact they are different