Firas Kraiem on Sat, 28 Sep 2013 18:37:42 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: Fermat pseudoprime test


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