printprime
print 2, 3
n = 5
repeat
if RepeatMillRabin( n, floor(lg n)) then print
n
n = n + 2
end
Clearly, every prime number will eventually be printed by this program.
One might also expect composite number to be produced errorneously once
in a while. Prove that this is unlikely to happen. More precisely,
prove that the probability is better than 99% that no composite number
larger than 100 will ever be produced, regardless of how long the program
is allowed to run.
Note : This figure of 99% is very conservative as it would still
hold even if MillRab(n) had a flat 25% chance of failure on each composite
integer.
2 Let A and B be two biased Monte Carlo algorithms for solving the same decision problem. Algorithm A is p-correct but its answer is quaranteed when it is true; algorithm B is q-correct but its answer is quaranteed when it is false. Show how to combine A and B into a Las Vegas algorithm LV(x,y,success) to solve the same problem. One call on LV should not take significantly more time than a call on A followed by a call on B. If your Las Vegas algorithm succeeds with probability at least r whatever the instance, what is the best value of r you can obtain?
3 Let X be a finite set whose elements are easy to enumerate and let Y be a nonempty subset of X of unknown cardinality. Assume you can decide, given x in X, whether or not x in Y. How would you chosse a random element of Y according to the uniform distribution? The obvious solution is to make a first pass through X to count the number of n of elements in Y, then choose a random integer k = uniform(1..n), and finally locat the k-th element of Y by going through X again, unless you kept the elements of Y in an array during the first pass through X. Surprisingly, this problem can be solved with a single pass through X, without additional storage, and without first counting the elements in Y. Consider the following algorithm :
draw ( X, Y )
n = 0
for each x in X do
if x in Y then n = n + 1
if uniform(1..n) = n then z = x
if n > 0 then return z
else
return "error Y is empty".
Prove by mathematical induction on the number of elements in Y that
this algorithm finds an element of Y randomly according to the uniform
distribution.