Olivier Ramare on Tue, 28 Mar 2000 15:46:15 +0200 (MET DST) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
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