2
$\begingroup$

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

$\endgroup$
1
  • 3
    $\begingroup$ Suppose the input is n=4 and d= 3. $\endgroup$ – John L. Apr 14 '20 at 14:42
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.