Sorry, an error occurred while loading the content.

## Re: mod quartic composite tests

Expand Messages
• ... I have verified this test for all x for all n
Message 1 of 26 , Jan 10 10:28 AM
--- In primenumbers@yahoogroups.com, "paulunderwooduk" wrote:

> gcd(x^3-x,n)==1
> kronecker(x^2-4,n)==-1
> gcd(x^2-2,n)==1
> (L+x^2-2)^n==-L^3+(x^2-2)*L+(x^2-2) (mod n, (L^2-x*L+1)*(L^2+x*L+1))

I have verified this test for all x for all n<10^6 co-prime to 30,

Paul
• ... ? {tst(n,x)=kronecker(x^2-4,n)==-1&& gcd(x^3-x,n)==1&& gcd(x^2-2,n)==1&& Mod(Mod(1,n)*(L+x^2-2),(L^2-x*L+1)*(L^2+x*L+1))^(n)==-L^3+(x^2-2)*L+x^2-2;} ?
Message 2 of 26 , Jan 11 12:17 PM
--- In primenumbers@yahoogroups.com, "paulunderwooduk" wrote:
>
>
>
> --- In primenumbers@yahoogroups.com, "paulunderwooduk" wrote:
>
> > gcd(x^3-x,n)==1
> > kronecker(x^2-4,n)==-1
> > gcd(x^2-2,n)==1
> > (L+x^2-2)^n==-L^3+(x^2-2)*L+(x^2-2) (mod n, (L^2-x*L+1)*(L^2+x*L+1))
>
> I have verified this test for all x for all n<10^6 co-prime to 30,
>

? {tst(n,x)=kronecker(x^2-4,n)==-1&&
gcd(x^3-x,n)==1&&
gcd(x^2-2,n)==1&&
Mod(Mod(1,n)*(L+x^2-2),(L^2-x*L+1)*(L^2+x*L+1))^(n)==-L^3+(x^2-2)*L+x^2-2;}

? {tstfile("underw297.txt");}
2/297 counterexamples left in underw297.txt
? {tstfile("underw65.txt");}
5146/12846 counterexamples left in underw65.txt

Paul
• ... Adding gcd(x^2-3,n)==1 makes sense because x^2-2==1 (mod x^2-3). So the resurrected test is: {tst(n,x)=kronecker(x^2-4,n)==-1&& gcd(x^3-x,n)==1&&
Message 3 of 26 , Jan 11 6:11 PM
--- In primenumbers@yahoogroups.com, "paulunderwooduk" wrote:

>
> ? {tst(n,x)=kronecker(x^2-4,n)==-1&&
> gcd(x^3-x,n)==1&&
> gcd(x^2-2,n)==1&&
> Mod(Mod(1,n)*(L+x^2-2),(L^2-x*L+1)*(L^2+x*L+1))^(n)==-L^3+(x^2-2)*L+x^2-2;}
>
> ? {tstfile("underw297.txt");}
> 2/297 counterexamples left in underw297.txt
> ? {tstfile("underw65.txt");}
> 5146/12846 counterexamples left in underw65.txt
>

Adding gcd(x^2-3,n)==1 makes sense because x^2-2==1 (mod x^2-3). So the resurrected test is:

{tst(n,x)=kronecker(x^2-4,n)==-1&&
gcd(x^3-x,n)==1&&
gcd(x^2-2,n)==1&&
gcd(x^2-3,n)==1&&
Mod(Mod(1,n)*(L+x^2-2),(L^2-x*L+1)*(L^2+x*L+1))^(n)==-L^3+(x^2-2)*L+x^2-2;}

Then checking David's files at:
http://physics.open.ac.uk/~dbroadhu/cert/

{tstfile(file)=local(c,n,x,v=readvec(file));
for(k=1,#v,n=v[k][1];x=v[k][2];
if(tst(n,x)&&!isprime(n),c++));
print(c"/"#v" counterexamples left in "file);c;}

? {tstfile("underbh4.txt");}
0/33445 counterexamples left in underbh4.txt
? {tstfile("underbh6.txt");}
0/308619 counterexamples left in underbh6.txt
? {tstfile("underw97.txt");}
0/97 counterexamples left in underw97.txt
? {tstfile("underw297.txt");}
0/297 counterexamples left in underw297.txt
? {tstfile("underw65.txt");}
0/12846 counterexamples left in underw65.txt
? {tstfile("underw65x.txt");}
0/10220 counterexamples left in underw65x.txt
? {tstfile("underwg.txt");}
0/100000 counterexamples left in underwg.txt

Paul
• ... n=2672279 and x=89805 forms a near-counterexample, saved only by gcd(x^3-x,n)==2672279. Since gcd(x^3-x,n)==1 is required I do not have to verify numbers
Message 4 of 26 , Jan 15 12:31 PM
--- In primenumbers@yahoogroups.com, "paulunderwooduk" wrote:

> {tst(n,x)=kronecker(x^2-4,n)==-1&&
> gcd(x^3-x,n)==1&&
> gcd(x^2-2,n)==1&&
> gcd(x^2-3,n)==1&&
> Mod(Mod(1,n)*(L+x^2-2),(L^2-x*L+1)*(L^2+x*L+1))^(n)==-L^3+(x^2-2)*L+x^2-2;}
>

n=2672279 and x=89805 forms a near-counterexample, saved only by gcd(x^3-x,n)==2672279.

Since gcd(x^3-x,n)==1 is required I do not have to verify numbers divisible by 2 or 3, and with kronecker(x^2-4,n)==-1, I do not have to verify numbers divisible by 5. Also the squares modulo 7 are 0, 1, 4, and 2, and because I am checking gcd(x^3-x,n)==1, kronecker(x^2-4,n)==-1 and gcd(x^2-2,n)==1, I can skip numbers divisible by 7. All in all, I need only verify numbers co-prime to 210,

Paul
• ... That should read gcd(x^2-3,n)==2672279. Paul
Message 5 of 26 , Jan 15 12:35 PM
--- In primenumbers@yahoogroups.com, "paulunderwooduk" wrote:

> n=2672279 and x=89805 forms a near-counterexample, saved only by gcd(x^3-x,n)==2672279.

That should read gcd(x^2-3,n)==2672279.

Paul
• ... A wise wriggle :-) Without it, you left yourself wide open to fraud. With it, you seem to be much more secure. I believe, yet cannot show, that there are
Message 6 of 26 , Jan 15 2:30 PM
--- In primenumbers@yahoogroups.com,
"paulunderwooduk" wrote:

> Adding gcd(x^2-3,n)==1

A wise "wriggle" :-)

Without it, you left yourself wide open to fraud.
With it, you seem to be much more secure.

I believe, yet cannot show, that there are zillions of
counterexamples to your single-parameter, double-Frobenius
test, yet the prospects of finding one, now that you
have bolted the stable door, seem to be minuscule.

Thanks, Paul, for your responsiveness.

David
• ... http://physics.open.ac.uk/~dbroadhu/cert/underwqd.txt.gz provides 352869 such frauds: {tst(n,x)=kronecker(x^2-4,n)==-1&&gcd(x^3-x,n)==1&&gcd(x^2-2,n)==1&&
Message 7 of 26 , Jan 17 5:28 AM
--- In primenumbers@yahoogroups.com,
"paulunderwooduk" wrote:

> n=2672279 and x=89805

http://physics.open.ac.uk/~dbroadhu/cert/underwqd.txt.gz
provides 352869 such frauds:

{tst(n,x)=kronecker(x^2-4,n)==-1&&gcd(x^3-x,n)==1&&gcd(x^2-2,n)==1&&
Mod(Mod(1,n)*(L+x^2-2),(L^2-x*L+1)*(L^2+x*L+1))^n==-L^3+(x^2-2)*L+x^2-2;}

{tstfile(file)=local(v=readvec(file),c);
c=sum(k=1,#v,tst(v[k][1],v[k][2])&&!isprime(v[k][1]));
print(c"/"#v" counterexamples left in "file);c;}

tstfile("underwqd.txt");

352869/352869 counterexamples left in underwqd.txt

All are trapped by Paul's latest wriggle,
which requires x^2-3 to be coprime to n.

David
• ... Thanks for these, David. Is it a comprehensive list for all n
Message 8 of 26 , Jan 17 9:29 AM
--- In primenumbers@yahoogroups.com, "djbroadhurst" wrote:

> http://physics.open.ac.uk/~dbroadhu/cert/underwqd.txt.gz

>
> 352869/352869 counterexamples left in underwqd.txt
>
> All are trapped by Paul's latest wriggle,
> which requires x^2-3 to be coprime to n.
>

Thanks for these, David. Is it a comprehensive list for all n <= 97847746461047271599?

Paul
• ... By no means. However the updated file http://physics.open.ac.uk/~dbroadhu/cert/underwqd.txt.gz now has more:
Message 9 of 26 , Jan 17 1:23 PM
--- In primenumbers@yahoogroups.com,
"paulunderwooduk" wrote:

> Is it a comprehensive list for all n <= 97847746461047271599?

By no means. However the updated file
http://physics.open.ac.uk/~dbroadhu/cert/underwqd.txt.gz
now has more:

{tst(n,x)=kronecker(x^2-4,n)==-1&&gcd(x^3-x,n)==1&&gcd(x^2-2,n)==1&&
Mod(Mod(1,n)*(L+x^2-2),(L^2-x*L+1)*(L^2+x*L+1))^n==-L^3+(x^2-2)*L+x^2-2;}

{tstfile(file)=local(v=readvec(file),c);
c=sum(k=1,#v,tst(v[k][1],v[k][2])&&!isprime(v[k][1]));
print(c"/"#v" counterexamples left in "file);c;}

tstfile("underwqd.txt");

422355/422355 counterexamples left in underwqd.txt

Challenge: Find a composite 10^10-smooth positive
integer, n, such that:
1) there exist an integer x that passes tst(n,x),
2) n is not in underwqd.txt.

Comment: I do not know of any such integer. Nor do I know
how to search for one. So I guess that means my gremlins
are comprehensively exhausted, though the question is not.

David
• ... Exercise: Show that Paul s test Mod(Mod(1,n)*(L+x^2-2),(L^2-x*L+1)*(L^2+x*L+1))^n==-L^3+(x^2-2)*L+x^2-2 requires n to be a Fermat pseudoprime in base
Message 10 of 26 , Jan 18 12:47 AM
> All are trapped by Paul's latest wriggle,
> which requires x^2-3 to be coprime to n.

Exercise: Show that Paul's test
Mod(Mod(1,n)*(L+x^2-2),(L^2-x*L+1)*(L^2+x*L+1))^n==-L^3+(x^2-2)*L+x^2-2
requires n to be a Fermat pseudoprime in base 1+(x^2-3)*(x^2-2)^3
and thus loses (at least) one selfridge of potency for x^2 = 3 mod n.

David
• ... ? M=[0,(x^2-2),0,-1;1,0,0,0;0,1,0,0;0,0,1,0];matdet(M+x^2-2)==1+(x^2-3)*(x^2-2)^3 1 Thanks for the insight. This can be split into 2 Fermat tests: ?
Message 11 of 26 , Jan 18 1:23 AM
--- In primenumbers@yahoogroups.com, "djbroadhurst" wrote:
>
>
>
> > All are trapped by Paul's latest wriggle,
> > which requires x^2-3 to be coprime to n.
>
> Exercise: Show that Paul's test
> Mod(Mod(1,n)*(L+x^2-2),(L^2-x*L+1)*(L^2+x*L+1))^n==-L^3+(x^2-2)*L+x^2-2
> requires n to be a Fermat pseudoprime in base 1+(x^2-3)*(x^2-2)^3
> and thus loses (at least) one selfridge of potency for x^2 = 3 mod n.
>

? M=[0,(x^2-2),0,-1;1,0,0,0;0,1,0,0;0,0,1,0];matdet(M+x^2-2)==1+(x^2-3)*(x^2-2)^3
1

Thanks for the insight.

This can be split into 2 Fermat tests:

? M=[x,-1;1,0];matdet(M+x^2-2)
x^4 + x^3 - 4*x^2 - 2*x + 5
? M=[-x,-1;1,0];matdet(M+x^2-2)
x^4 - x^3 - 4*x^2 + 2*x + 5

which are equal to:

? M=[x,-1;1,0];matdet(M+x^2-2)==(x^2-2)*(x+2)*(x-1)+1
1
? M=[-x,-1;1,0];matdet(M+x^2-2)==(x^2-2)*(x-2)*(x+1)+1
1

Paul
• ... Exercise 2: Show that the test loses 3 selfrides for x^2 = 3 mod n. Comment 2: Hence the happy gremlins, in this case. Exercise 3: Show that the test loses
Message 12 of 26 , Jan 18 3:56 AM
--- In primenumbers@yahoogroups.com, "paulunderwooduk" wrote:

> > loses (at least) one selfridge of potency for x^2 = 3 mod n.
> Thanks for the insight.

Exercise 2: Show that the test loses 3 selfrides for x^2 = 3 mod n.
Comment 2: Hence the happy gremlins, in this case.

Exercise 3: Show that the test loses 1 selfride for 2*x^2 = 5 mod n.
Comment 3: The gremlins were not able to fool it in this case.

David
• ... Exercise 4: Show that the test loses 2 selfridges for 2*x^2 = 5 mod n. David
Message 13 of 26 , Jan 18 4:06 AM
--- In primenumbers@yahoogroups.com, "djbroadhurst" wrote:
> Exercise 3: Show that the test loses 1 selfridge for 2*x^2 = 5 mod n.

Exercise 4: Show that the test loses 2 selfridges for 2*x^2 = 5 mod n.

David
• ... Exercise 5: Show that the test loses 3 selfridges for 2*x^2 = 5 mod n, degenerating to a 1-selfridge Euler test, with base -15/16, plus a 2-selfridge Lucas
Message 14 of 26 , Jan 18 4:43 AM
--- In primenumbers@yahoogroups.com, "djbroadhurst" wrote:

> Exercise 4: Show that the test loses 2 selfridges for 2*x^2 = 5 mod n.

Exercise 5: Show that the test loses 3 selfridges for 2*x^2 = 5 mod n,
degenerating to a 1-selfridge Euler test, with base -15/16, plus a
2-selfridge Lucas test with P = 2/5 and Q = 1, and thus costs the same as BPSW.

Comment: As in the case of BPSW, the gremlins cannot defraud this case.

David
• I failed to solve any of David s exercises... but I have done some shallow verification, n
Message 15 of 26 , Jan 19 8:35 AM
I failed to solve any of David's exercises... but I have done some shallow verification, n<2.5*10^5, for yet another test:

{tst(n,x)=kronecker(x^2-4,n)==-1&&
gcd(x+1,n)==1&&
Mod(Mod(1,n)*(L+x+1),(L^2-x*L+1)*(L^2+x*L+1))^(n)==-L^3+(x^2-2)*L+x+1;}

It looks as though when "gcd(x+1,n)==1" is needed then n==5 (mod 6), and any of gcd(x-1,n), gcd(x,n), gcd(x^2-2,n) and gcd(x^3-3,n) greater than 1 is also a prime equal to 5 (mod 6) when "gcd(x+1,n)==1" is required,

Paul -- subject to gcd wriggles
• ... Further, it seems that if gcd(x+1,n) is needed then it is equal to 1 (mod 6) Paul
Message 16 of 26 , Jan 19 9:22 AM
--- In primenumbers@yahoogroups.com, "paulunderwooduk" wrote:
>
>
> I failed to solve any of David's exercises... but I have done some shallow verification, n<2.5*10^5, for yet another test:
>
> {tst(n,x)=kronecker(x^2-4,n)==-1&&
> gcd(x+1,n)==1&&
> Mod(Mod(1,n)*(L+x+1),(L^2-x*L+1)*(L^2+x*L+1))^(n)==-L^3+(x^2-2)*L+x+1;}
>
> It looks as though when "gcd(x+1,n)==1" is needed then n==5 (mod 6), and any of gcd(x-1,n), gcd(x,n), gcd(x^2-2,n) and gcd(x^3-3,n) greater than 1 is also a prime equal to 5 (mod 6) when "gcd(x+1,n)==1" is required,
>

Further, it seems that if "gcd(x+1,n)" is needed then it is equal to 1 (mod 6)

Paul
• ... These ancillary statements are mostly false, except that maybe when gcd(x+1,n) needs to be checked then gcd(x-1,n), gcd(x,n), gcd(x^2-2,n) and
Message 17 of 26 , Jan 19 9:44 AM
--- In primenumbers@yahoogroups.com, "paulunderwooduk" wrote:
>
>
>
> --- In primenumbers@yahoogroups.com, "paulunderwooduk" wrote:
> >
> >
> > I failed to solve any of David's exercises... but I have done some shallow verification, n<2.5*10^5, for yet another test:
> >
> > {tst(n,x)=kronecker(x^2-4,n)==-1&&
> > gcd(x+1,n)==1&&
> > Mod(Mod(1,n)*(L+x+1),(L^2-x*L+1)*(L^2+x*L+1))^(n)==-L^3+(x^2-2)*L+x+1;}
> >
> > It looks as though when "gcd(x+1,n)==1" is needed then n==5 (mod 6), and any of gcd(x-1,n), gcd(x,n), gcd(x^2-2,n) and gcd(x^3-3,n) greater than 1 is also a prime equal to 5 (mod 6) when "gcd(x+1,n)==1" is required,
> >
>
> Further, it seems that if "gcd(x+1,n)" is needed then it is equal to 1 (mod 6)
>

These ancillary statements are mostly false, except that maybe when "gcd(x+1,n)" needs to be checked then gcd(x-1,n), gcd(x,n), gcd(x^2-2,n) and gcd(x^3-3,n) are either 1 or prime,

Paul
• ... Please accept my apology for my previous statements about this composite test. I am actually running tests for: (mod n, L^2-x*L+1) and (mod n, L^2+x*L+1);
Message 18 of 26 , Jan 19 1:05 PM
--- In primenumbers@yahoogroups.com, "paulunderwooduk" wrote:

> > >
> > > {tst(n,x)=kronecker(x^2-4,n)==-1&&
> > > gcd(x+1,n)==1&&
> > > Mod(Mod(1,n)*(L+x+1),(L^2-x*L+1)*(L^2+x*L+1))^(n)==-L^3+(x^2-2)*L+x+1;}
> > >

Please accept my apology for my previous statements about this composite test. I am actually running tests for:
(mod n, L^2-x*L+1) and (mod n, L^2+x*L+1); not the product of these. If the main test is passed then gcds with n of x-1, x, x+1, x^2-2 and x^2-3 are logged.

Now for some speculation about the results so far:

1) taking the mod with "the product" implies gcd(x,n)==1.

2) for "the product", gcds of n with x-1, x^2-2 and x^2-3 are either 1 or a prime congruent to 5 (mod 6) where "gcd(x+1,n)" is logged.

3) logged gcd(x+1,n) is not 1

4) the logged n are all congruent to 5 (mod 6).

Paul
• ... Here is another test, on the same theme, for which I cannot also easily find a fraud: {tst(n,x)=kronecker(x^2-4,n)==-1&& gcd(x^2-1,n)==1&&
Message 19 of 26 , Jan 21 3:27 AM
--- In primenumbers@yahoogroups.com, "paulunderwooduk" wrote:

>
> > > >
> > > > {tst(n,x)=kronecker(x^2-4,n)==-1&&
> > > > gcd(x+1,n)==1&&
> > > > Mod(Mod(1,n)*(L+x+1),(L^2-x*L+1)*(L^2+x*L+1))^(n)==-L^3+(x^2-2)*L+x+1;}
> > > >
>

Here is another test, on the same theme, for which I cannot also easily find a fraud:

{tst(n,x)=kronecker(x^2-4,n)==-1&&
gcd(x^2-1,n)==1&&
Mod(Mod(1,n)*(L+x^2-1),(L^2-x*L+1)*(L^2+x*L+1))^(n)==-L^3+(x^2-2)*L+x^2-1;}

Paul
• ... n=2953711;x=285843 is a near-counterexample that comes from me testing over the two quadratics that form the quartic. gcd(x,n)==95281 and
Message 20 of 26 , Jan 27 2:23 AM
--- In primenumbers@yahoogroups.com, "paulunderwooduk" wrote:

> Here is another test, on the same theme, for which I cannot also easily find a fraud:
>
> {tst(n,x)=kronecker(x^2-4,n)==-1&&
> gcd(x^2-1,n)==1&&
> Mod(Mod(1,n)*(L+x^2-1),(L^2-x*L+1)*(L^2+x*L+1))^(n)==-L^3+(x^2-2)*L+x^2-1;}
>

n=2953711;x=285843 is a near-counterexample that comes from me testing over the two quadratics that form the quartic. gcd(x,n)==95281 and gcd(x^2-2,n)==31,

Paul
• ... n=1934765;x=1219266 has gcd(x-1,n)==265. So 2) might be 1 or a product of primes each congruent 5 (mod 6) , but as greater n get tested I guess this rule
Message 21 of 26 , Jan 30 1:18 PM
> --- In primenumbers@yahoogroups.com, "paulunderwooduk" wrote:
>
>
> > > >
> > > > {tst(n,x)=kronecker(x^2-4,n)==-1&&
> > > > gcd(x+1,n)==1&&
> > > > Mod(Mod(1,n)*(L+x+1),(L^2-x*L+1)*(L^2+x*L+1))^(n)==-L^3+(x^2-2)*L+x+1;}
> > > >
>
> Please accept my apology for my previous statements about this composite test. I am actually running tests for:
> (mod n, L^2-x*L+1) and (mod n, L^2+x*L+1); not the product of these. If the main test is passed then gcds with n of x-1, x, x+1, x^2-2 and x^2-3 are logged.
>
> Now for some speculation about the results so far:
>
> 1) taking the mod with "the product" implies gcd(x,n)==1.
>
> 2) for "the product", gcds of n with x-1, x^2-2 and x^2-3 are either 1 or a prime congruent to 5 (mod 6) where "gcd(x+1,n)" is logged.
>

n=1934765;x=1219266 has gcd(x-1,n)==265. So 2) might be "1 or a product of primes each congruent 5 (mod 6)", but as greater n get tested I guess this rule will break too...

> 3) logged gcd(x+1,n) is not 1
>
> 4) the logged n are all congruent to 5 (mod 6).
>

I have verified all n<1.95*10^6

Paul
Your message has been successfully submitted and would be delivered to recipients shortly.