Why is this verifier for primality wrong?

Question

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’"

Answer 1

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.