Re: Fermat pseudoprime test

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

* Shyam Sunder Gupta [2013-09-28 09:04]:
>  I  note that checking for Fermat  pseudoprime(base 2) from Mod(2,n)^n
>  takes long time and is almost two times than checking for strong
>  pseudoprime test using BPSW test by ispseudoprime() function . Can it
>  be commented and some function to test Fermat pseudoprime (base 2) if
>  not faster than atleast equal to ispseudoprime() function which
>  checks for strong pseudoprime test using BPSW test is required in GP
>  pari package.

I am not sure I understand. Are you complaining that a naive Fermat test
Mod(2,N)^(N-1) == 1 is about twice faster than ispseudoprime() ?

This is as documented in ??ispseudoprime: the point is to catch as many
composites as possible (no known failure to date, provably correct up to 2^64),
not to return a little faster, with a result whose failure rate is > 1/10^5.

\\ not so fast, quite a few failures
(18:14) gp > c=0;forcomposite(n=2,10^8, if(n%2 && Mod(2,n)^(n-1)==1, c++));c
time = 47,188 ms.
%1 = 2057

\\ 1 single Rabin-Miller test, with a random seed. Fater, fewer failures.
(18:18) gp > c=0;forcomposite(n=2,10^8, if(n%2 && ispseudoprime(n,1), c++));c
time = 42,372 ms.
%2 = 526

\\ Default: faster on average, no false positive
(18:15) gp > c=0;forcomposite(n=2,10^8, if(n%2 && ispseudoprime(n), c++));c
time = 36,445 ms.
%3 = 0


How would you change the documentation ?

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux1.fr/~kbelabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux1.fr/  [PARI/GP]
`