Re: Fermat pseudoprime test

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

* Firas Kraiem [2013-09-28 18:37]:
> On 9/28/13 6:23 PM, Karim Belabas wrote:
> >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.
[...]
> (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.

OK, that's easily explained: ispseudoprime() performs

* a test for prime divisors less that 101: very quick (2 divisions by a
  1-word ulong followed by a few gcd on ulongs) and eliminates most
  composites already

* a base-2 Rabin-Miller test: slightly faster than Fermat since you may
  save a few squarings at the end.

* an "expensive" Lucas test, but composites almost never reach that point.

If you want Fermat to beat ispseudoprime(), you have to try it on primes !

(18:49) gp > p = randomprime(10^1000);
(18:49) gp > ispseudoprime(p)
time = 96 ms.
%2 = 1
(18:49) gp > Mod(2,p)^(p-1) == 1
time = 40 ms.
%3 = 1

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