Olivier Ramare on Tue, 28 Mar 2000 15:46:15 +0200 (MET DST)

 Primality Testing


Hello,

No true primality testing in PARI/GP... It would be however nice if
isprime were using the following two theorems of Jaeschke:

\begin{theorem}
Let $p$ be an odd integer. If $p$ is strong pseudoprime for bases
2,3,5,7,11,13 and 17 and $p<3.4\times 10^{14}$, then $p$ is a prime
number.
\end{theorem}

\begin{theorem}
Let $p$ be an odd integer. If $p$ is strong pseudoprime for bases
2,13,23 and 1662803 and $p<10^{12}$, then $p$ is a prime number.
\end{theorem}

and I should maybe recall that:

\begin{definition}
Let $p$ be an odd integer and $a$ be an integer.
Let $h$ be such that $p=1+2^h.d$ with $d$ being odd. Then $p$ is a
{\em strong pseudoprime} for base $a$ if we have
either $a^d \equiv 1 \pmod{p}$,
or there exists $k$ such that $0 \leq k < h$
with $a^{2^k.d} \equiv -1 \pmod{p}$.
\end{definition}

Best,
Olivier Ramare