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 1980for 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.