hermann on Mon, 08 Jul 2024 16:00:58 +0200


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

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


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.