Re: Fermat pseudoprime test

[Firas Kraiem <firas.kraiem@etu.u-bordeaux1.fr>]

On 9/28/13 6:23 PM, Karim Belabas wrote:
> * 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() ?

If I understand correctly, Shyam is wondering why a naive Fermat test is 
*slower* than ispseudoprime(), at least on some values of N.  I suppose 
since it's a lot less reliable, it would be natural to expect it to be 
at least faster. Consider:

(16:50) gp > n = random(10^1000);
(18:29) gp > n%2
1
(18:29) gp > Mod(2,n)^(n-1) == Mod(1,n)
0
(18:29) gp > ##
  ***   last result computed in 40 ms.
(18:29) gp > ispseudoprime(n)
0
(18:29) gp > ##
  ***   last result computed in 0 ms.

Firas

> 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]
> `