You are given a probabilistic algorithm for testing whether an n bit number is p

Question

You are given a probabilistic algorithm for testing whether an n bit number is prime. If the input is prime, the algorithm always outputs "prime." If it is not a prime then with probability 1/2 the algorithm outputs "prime", and with probability 1/2 it outputs "not prime." Suppose only 1/n of all n bit numbers are prime. If the algorithm outputs "prime" on a given input, what is the probability that this input is actually prime Suppose you run the algorithm k times on a given input x, and the algorithm outputs "prime" on all k runs. What is the probability that x is actually prime For your answer to part what is the smallest value of k such that the probability x is prime is at least 1 - 1/n

Explanation / Answer

total count of numbers with n-bits = 2^n

total actual prime numbers = (2^n)/n

P(prime and number is actually prime) = 1

P(prime and number is actually not-prime) = 1/2

P(not-prime and number is actually not-prime) = 1/2

(a).
P(prime) = (1/n)*1 + (1 - 1/n)*1/2 = (n+1)/2n
P(actually prime) = (1/n) / P(prime)
       = 2/(n+1)

(b).
It is same as P(prime) = (n+1)/2n

(c).
Since it is known that all the iterations of algorithm gives output as "Prime".
Also the P(prime) is given as below :-
P(prime) = (1/n)*1 + (1 - 1/n)*1/2 = (n+1)/2n

So, to have atleast (1 - 1/n), we need to deal with value of 'n' and not 'k'.
Thus smallest value can be 1.

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.