From: rgep@pmms.cam.ac.uk (Richard Pinch)
Newsgroups: sci.math
Subject: Re: Incontrovertible primality proof
Date: 8 Dec 1995 12:36:38 GMT

In article <4a77gh$amv@decaxp.harvard.edu>, 
blom@kkobayas-2.student.harvard.edu (Eric Edgerton Blom) writes:
|> I hear that it has been proven that primality/composition is both NP and 
|> co-NP.  That would imply that certificates of both composition and 
|> primality which are checkable in polynomial time must exist for all numbers.
|> 
|> For composition, that's obvious: a pair (x,y) such that xy=N.
|> 
|> But for primes, it's less than obvious.  What is a 
|> polynomially-checkable, but incontrovertible, proof of primality?  Would 
|> a primitive root work, or would the Carmichael numbers give us a problem?

A primitive root would work, but you have to show that it's primitive:
that means you have to show that it doesn't have any smaller order.  The
details are extracted from my lecture notes.

Richard Pinch;	Queens' College, Cambridge

% Primality is in NP - Richard Pinch - Queens' College, Cambridge - 9/xii/95
\input mssymb
\def\nl{\smallskip\noindent}
\def\result#1.{\bigbreak\noindent{\bf #1 \ }\par \sl }
\def\proof{\par\medbreak\noindent\bf Proof:\  \rm }\def\qed{\hfill$\square$\nl}
\def\hcf{\mathop{\rm hcf}}\def\Hcf#1{{\hcf\left\lbrace{#1}\right\rbrace}}
\def\congruent{\equiv}\def\mod{\bmod}\def\divides{\mid}

\result Proposition.
Suppose that $N-1$ has prime power
factorisation $N-1 = \prod_{i=1}^d q_i^{e_i}$.
If there exists $a_i$ for $i = 1,\ldots,d$ such that
$$
a_i^{N-1} \congruent 1 \mod N
$$
and
$$
\Hcf{a_i^{N-1 \over q_i} - 1, N} = 1
$$
then $N$ is prime.
\proof
Let $p$ be a prime factor of $N$.
The conditions on $a_i$ imply that $a_i^{N-1} \congruent 1 \mod p$ and
$a_i^{(N-1)/q_i} \not\congruent 1 \mod p$.
Hence $b_i = a_i^{(N-1)/     q_i^{e_i}}$ is also not $1 \mod p$.
So $b_i$ is an element of order exactly $q_i^{e_i}$ modulo $p$,
and so $p \congruent 1 \mod q_i^{e_i}$.  Since this is true for all $i$,
we have $N - 1 \divides p - 1$, so $N = p$ is prime.
\qed
\result Theorem.
The question ``Is $N$ prime?'' can be answered in non-deterministic
polynomial time.
\proof
Put $l = \log_2 N$.  We claim that there is a certificate of length at
most $2 l^3$ which can be used to verify the primality of $N$ in time
polynomial in $l$.  We may assume $l \ge 4$.

We apply the previous result to a certificate consisting of a list
comprising the
factors $q_i$, the corresponding $a_i$, and the certificates for each of
the $q_i > 2$: the claim is that this certificate has length at most $2l^3$.
We proceed by induction on $N$.  Put $l_i = \log_2 q_i$.

The number of distinct prime factors $N-1$ is at most $l$, so the number of
$q_i$ and $a_i$ is at most $l$ and the number of bits in
each $a_i$ is at most $l + 1$.
By the induction hypothesis, the length of the certificate for each $q_i$ is of
length at most $2 l_i^3$.  Since we
may assume $N$ odd, we have $\sum_{i>1} l_i \le l - 1$.  So
$$
\sum_{i>1} l_i^3 \le \left(\sum_{i>1} l_i\right)^3 \le (l-1)^3
 \le l^3 - 2l^2 - l
$$
for $l \ge 4$
and the total length of the certificate for $N$ is at
most $2(l^3 - 2l^2 - l) + 2l(l+1) = 2l^3$, as required.

Since the requirements on the $a_i$ can clearly be checked in polynomial time,
the result follows.
\qed

\end