Karim BELABAS on Tue, 28 Mar 2000 16:00:23 +0200 (MET DST)

 Re: Primality Testing

[Olivier.Ramare@agat.univ-lille1.fr writes:]
>   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}

It's in there, sort of:

install(millerrabin, "lGD7,L,", IsPrime)

Now IsPrime(n) return a guaranteed answer provided n < 10^12

Well... [once 2.1 is out] it would be a good idea to include something like
that (+ Selfridge test) by default:

isprime(n) should return a guaranteed answer, and ispseudoprime should accept
an optional argument specifying the number of bases to check [ so that
old "isprime" = new "ispseudoprime(n,10)" ]

Karim.
__
Karim Belabas                    email: Karim.Belabas@math.u-psud.fr
Dep. de Mathematiques, Bat. 425
Universite Paris-Sud             Tel: (00 33) 1 69 15 57 48
F-91405 Orsay (France)           Fax: (00 33) 1 69 15 60 19
--