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 (b), what is the smallest value of k such that the probability x is prime is at least 1 - 1/n?

Explanation / Answer

a)

Number to be prime = 1/n

Probability of Algorithm to print ouput prime = if number is actually prime

                                                               = 1/n

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

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