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