Primality testing and primality certificates

The number $n=2^h+1$, $h\geq 2$ is a prime number if and only if

Prove that the following integers are primes: $293,587,65537,214177$.

Prime is in NP.

Prove that 683 is a prime.

• Show that PRIMES $=\left\{ m \mid m\text{ is a prime number in binary }\right\} \in \mathrm{NP}$. (Hint: For $p>1$, the multiplicative group $Z_{p}^{*}=\left\{ x \mid x\text{ is relatively prime to }p\text{ and }1 \leq x<p\right\}$ is both cyclic and of order $p-1$ iff $p$ is prime. You may use this fact without justifying it. The stronger statement PRIMES $\in \mathrm{P}$ is now known to be true, but it is more difficult to prove.)

Show that 12 is not pseudoprime because it fails some Fermat test.

• ᴬ Prove that for any integer $p>1$, if $p$ isn't pseudoprime, then $p$ fails the Fermat test for at least half of all numbers in $\mathcal{Z}_{p}^{+}$.