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

[hermann@stamm-wilbrandt.de]

On 2024-07-08 14:09, Karim Belabas wrote:
> * hermann@stamm-wilbrandt.de [2024-07-08 13:11]:
> > Are there known non-prime numbers where GP ispseudoprime returns 1
> > without passing flag?
>
> No.
Thanks, just learned that you can still earn 30$ price money from 1980
for providing an example, the price was still open in 2014 according 
wikipedia:
https://en.wikipedia.org/wiki/Baillie%E2%80%93PSW_primality_test

> > Or with other flag values?
>
> It's probably relatively easy to find one with flag = 1, and fixed
> setrand() of course.
Yes, as shown by Bill:

On 2024-07-08 14:46, Bill Allombert wrote:
> On Mon, Jul 08, 2024 at 01:11:32PM +0200, hermann@stamm-wilbrandt.de 
> wrote:
> > Or with other flag values?
>
> Yes, but they depend on the random seed;
>
> ? for(N=1,oo,setrand(1);if(ispseudoprime(N,1)&&!isprime(N),return(N)))
> %22 = 51
> ? for(N=1,oo,setrand(1);if(ispseudoprime(N,2)&&!isprime(N),return(N)))
> %23 = 949
> ? for(N=1,oo,setrand(1);if(ispseudoprime(N,3)&&!isprime(N),return(N)))
> %24 = 22028203


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};"



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.

Found it in basemath/src/trans1.c:

GEN
gsqrt(GEN x, long prec)
{
...
    case t_INTMOD:
    {
      GEN p = gel(x,1), a;
      y = cgetg(3,t_INTMOD); gel(y,1) = icopy(p);
      a = Fp_sqrt(gel(x,2),p);
      if (!a)
      {
        if (!BPSW_psp(p)) pari_err_PRIME("sqrt [modulus]",p);

So BPSW_psp() is directly called, and ispseudoprime() flag is irrelevant 
for that code path.

Regards,

Hermann.