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

On Mon, Jul 8, 2024 at 10:01 AM <hermann@stamm-wilbrandt.de> wrote:

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.