Function: primecert
Section: number_theoretical
C-Name: primecert
Prototype: GD0,L,
Help: primecert(N, {flag=0}): If N is a prime, return a Primality Certificate.
Return 0 otherwise. If flag = 0 return an ECPP certificate (Atkin-Morain);
if flag = 1 return an N-1 certificate (Pocklington-Lehmer)
Doc:
If N is a prime, return a PARI Primality Certificate for the prime $N$,
as described below. Otherwise, return 0. A Primality Certificate
$c$ can be checked using \tet{primecertisvalid}$(c)$.
If $\fl = 0$ (default), return an ECPP certificate (Atkin-Morain)
A PARI ECPP Primality Certificate for the prime $N$ is either a prime
integer $N < 2^{64}$ or a vector \kbd{C} of length $\ell$ whose $i$th
component \kbd{C[i]} is a vector of length $5$ containing $N_i$, $t_i$,
$s_i$, $a_i$, $P_i$ (in that order) where $N_1 = N$. It is said to be valid
if for each $i = 1, \ldots, \ell$, all of the following conditions are
satisfied
\item $N_i$ is a positive integer
\item $t_i$ is an integer such that $t_i < 4N_i^2$
\item $s_i$ is a positive integer which divides $m_i$ where
$m_i = N_i + 1 - t_i$
\item If we set $q_i = \dfrac{m_i}{s_i}$, then
\quad\item $q_i > (N_i^{1/4}+1)^2$
\quad\item $q_i = N_{i+1}$ if $1 \leq i < l$
\quad\item $q_\ell \leq 2^{64}$ is prime
\item $a_i$ is an integer
\quad\item \kbd{P[i]} is a vector of length $2$ representing the affine
point $P_i = (x_i, y_i)$ on the elliptic curve $E: y^2 = x^3 + a_ix + b_i$
modulo $N_i$ where $b_i = y_i^2 - x_i^3 - a_ix_i$ satisfying the following:
\quad\item $m_i P_i = \infty$
\quad\item $s_i P_i \neq \infty$
\misctitle{Theorem} If $N$ is an integer and there exist positive integers
$m, q$ and a point $P$ on the elliptic curve $E: y^2 = x^3 + ax + b$ defined
modulo $N$ such that $q > (N^{1/4} + 1)^2$, $q$ is a prime divisor of $m$,
$mP = \infty$ and $\dfrac{m}{q}P \neq \infty$, then $N$ is prime.
Using the above theorem, the data in the vector \kbd{C} can be used to
certify the primality of $N$ assuming $q_\ell$ is prime.
\bprog
? primecert(10^35 + 69)
%1 = [[100000000000000000000000000000000069, 5468679110354
52074, 2963504668391148, 0, [60737979324046450274283740674
208692, 24368673584839493121227731392450025]], [3374383076
4501150277, -11610830419, 734208843, 0, [26740412374402652
72 4, 6367191119818901665]], [45959444779, 299597, 2331, 0
, [18022351516, 9326882 51]]]
? primecert(nextprime(2^64))
%2 = [[18446744073709551629, -8423788454, 160388, 1, [1059
8342506117936052, 2225259013356795550]]]
? primecert(6)
%3 = 0
? primecert(41)
%4 = 41
@eprog\smallskip
If $\fl = 1$ (very slow), return an $N-1$ certificate (Pocklington Lehmer)
A PARI $N-1$ Primality Certificate for the prime $N$ is either a prime
integer $N < 2^{64}$ or a pair $[N, C]$, where $C$ is a vector with $\ell$
elements which are either a single integer $p_i < 2^{64}$ or a
triple $[p_i,a_i,C_i]$ with $p_i > 2^{64}$ satisfying the following
properties:
\item $p_i$ is a prime divisor of $N - 1$;
\item $a_i$ is an integer such that $a_i^{N-1} \equiv 1 \pmod{N}$ and
$a_i^{(N-1)/p_i} - 1$ is coprime with $N$;
\item $C_i$ is an $N-1$ Primality Certificate for $p_i$
\item The product $F$ of the $p_i^{v_{p_i}(N-1)}$ is strictly larger than
$N^{1/3}$. Provided that all $p_i$ are indeed primes, this implies that any
divisor of $N$ is congruent to $1$ modulo $F$.
\item The Billhart, Lehmer, Selfridge criterion is satisfied: when we write
$N = 1 + c_1 F + c_2 F^2$ in base $F$ the polynomial $1 + c_1 X + c_2 X^2$
is irreducible over $\Z$, i.e. $c_1^2 - 4c_2$ is not a square. This
implies that $N$ is prime.
This algorithm requires factoring partially $p-1$ for various prime integers
$p$ with an unfactored parted $\leq p^{2/3}$ and this may be exceedingly
slow compared to the default.
The algorithm fails if one of the pseudo-prime factors is not prime, which is
exceedingly unlikely and well worth a bug report. Note that if you monitor
the algorithm at a high enough debug level, you may see warnings about
untested integers being declared primes. This is normal: we ask for partial
factorizations (sufficient to prove primality if the unfactored part is not
too large), and \kbd{factor} warns us that the cofactor hasn't been tested.
It may or may not be tested later, and may or may not be prime. This does
not affect the validity of the whole Primality Certificate.