Primality Testing

[Olivier Ramare <Olivier.Ramare@agat.univ-lille1.fr>]

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