# Why is this verifier for primality wrong?

We are provided with the following verifier of primality:

Verifier for prime

Input: integer n ≥ 1
integer d

if 1 < d < n and d divides exactly n then
return ’no’
else
return ’yes’


But the answer is that it is wrong:

Note that in order to be a verifier it is required that for every n, n is a positive instance (that is, n is a prime) if and only if there exists one d such that the verifier with input n and d returns ’yes’. However, in the algorithm for Primes we have that n is a negative instance if and only if there exists one d such that the verifier with input n and d returns ’no’.

But I do not understand this answer or why "in order to be a verifier it is required that for every n, n is a positive instance (that is, n is a prime) if and only if there exists one d such that the verifier with input n and d returns ’yes’"

• Suppose the input is n=4 and d= 3. – John L. Apr 14 '20 at 14:42

Here are the semantics of a verifier for primality. The verifier gets two inputs, an integer $$n$$ and a witness $$w$$. The following two properties must hold"

• Soundness: if the verifier accepts $$n$$ and $$w$$, then $$n$$ is prime.
• Completeness: if $$n$$ is prime, then there is a witness $$w$$ such that the verifier accepts $$n$$ and $$w$$.

We also usually ask that the verifier run in polynomial time in $$n$$.

Your verifier isn't sound (take any odd composite $$n$$ and $$d = 2$$) but is complete.

However, if you flip the return value, you do get a verifier for compositeness:

• If $$d \mid n$$ and $$1 < d < n$$ then $$n$$ is composite.
• If $$n$$ is composite then there exists $$d$$ such that $$d \mid n$$ and $$1 < d < n$$.

The notion of a verifier is asymmetric. Your verifier works for compositeness, but not for its complement, which is primality.