Interactive Proofs

n ∉ Prime

Pr[primeprob(n,k)=T] < 1/4k

∀n∉Prime ∀D Pr( [D,B](n)=YES ) < 1/4k ≈ 0