Karim Belabas on Mon, 08 Jul 2024 16:50:35 +0200


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

Re: Are there known false positives for GP ispseudoprime() ? 

* hermann@stamm-wilbrandt.de [2024-07-08 16:01]:
[...]
> Btw, I found a small inconsistency in PARI/GP user guide vs. source:
> https://pari.math.u-bordeaux.fr/pub/pari/manuals/2.15.5/users.pdf#page=206
> "If flag = 0, checks whether x has no small prime divisors (up to 101
> included) ..."
> 
> src/basemath/ispower.c has "static ulong tinyprimes[] = {2, 3, ..., 197,
> 199};"

Nope: this 'tinyprimes' table is only used in ispower().

The quoted documentation for ispseudoprime(, 0) is correct; see
  basemath/prime.c:BPSW_psp()
lines 436-451.

> I was interested in which test was used in creating this error message:
> 
> ? sqrt(Mod(-1,85))
>   ***   at top-level: sqrt(Mod(-1,85))
>   ***                 ^----------------
>   *** sqrt: not a prime number in sqrt [modulus]: 85.
[...]
> So BPSW_psp() is directly called, and ispseudoprime() flag is irrelevant for
> that code path.

ispseudoprime is never used in the PARI library; we usually use BPSW_psp()
[ which guarantees that a negative result is correct but may miss 
(for know unkown) composites > 2^64 ].

The implementations follow the following general principle: we run an
"infinite" loop (usually making random choices) that is expected to halt
quickly if the precondition "p is prime" is met. After a "large
enough" number of failed tests, we perform a single BPSW_psp() test,
which is expected to quickly detect composites.

In practice, if "p" is indeed prime, the loop halts before the
BPSW_psp() test is run. And if not, we either trigger the aforementioned
pari_err_PRIME / e_PRIME exception, or the loop runs forever
[no instance known]

Cheers,

    K.B.
-- 
Pr. Karim Belabas, U. Bordeaux, Vice-président en charge du Numérique
Institut de Mathématiques de Bordeaux UMR 5251 - (+33) 05 40 00 29 77
http://www.math.u-bordeaux.fr/~kbelabas/