Re: Primality Testing

[Karim BELABAS <Karim.Belabas@math.u-psud.fr>]

[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
--
PARI/GP Home Page: http://www.parigp-home.de/