Prime numbers and primality testing is a Restricted Group with 1114 members.
 Prime numbers and primality testing

 Restricted Group,
 1114 members
Primary Navigation
Re: mod quartic composite tests
Expand Messages
 0 Attachment
 In primenumbers@yahoogroups.com,
"djbroadhurst" wrote:> With kronecker(x^42,n) = 1
but meant to write x^24, not x^42
 0 Attachment
 In primenumbers@yahoogroups.com, "djbroadhurst" wrote:>
Thanks for the algebra  it was worrying me.
>
>
>  In primenumbers@yahoogroups.com,
> Paul Underwood wrote:
>
> > (L+2)^n==L^3+(x^22)*L+2 (mod n, (L^2x*L+1)*(L^2+x*L+1))
> > This test is (1)+(1)+(2)+(2)+9 selfridge for small x
>
> I can do it in 6 selfridges for generic x.
> Where do your "9" selfridges come from, Paul?
>
> With (ed.) kronecker(x^24,n) = 1 and prime n, we have
>
> (L+a)^n = a+xL mod(n, L^2L*x+1) ... [1]
> (L+a)^n = axL mod(n, L^2+L*x+1) ... [2]
>
> and the two Frobenius tests cost 3+3=6 selfridges, generically.
>
> Now let f(x,L) = L^3+(x^22)*L and observe
> from simple algebra (no modularity involved) that
>
> f(x,L) + a = (a+xL)  (L+x)*(L^2x*L+1)
> f(x,L) + a = (axL)  (Lx)*(L^2+x*L+1)
>
> Hence [1] and [2] imply that
>
> (L+a)^n = f(x,L) + a mod(n, (L^2x*L+1)*(L^2+x*L+1)) ... [3]
>
> and Paul has set a = 2 in [3].
>
> Since this is a doubleFrobenius test, the gremlins
> reserve the right to choose /both/ parameters (a,x) in [3].
>
Yes, the gremlins will not like this test:
gcd(x^3x,n)
kronecker(x^24,n)==1
gcd(x^22,n)==1
(L+x^22)^n==L^3+(x^22)*L+(x^22) (mod n, (L^2x*L+1)*(L^2+x*L+1))
Paul 0 Attachment
 In primenumbers@yahoogroups.com, "paulunderwooduk" wrote:
> gcd(x^3x,n)==1
I have verified this test for all x for all n<10^6 coprime to 30,
> kronecker(x^24,n)==1
> gcd(x^22,n)==1
> (L+x^22)^n==L^3+(x^22)*L+(x^22) (mod n, (L^2x*L+1)*(L^2+x*L+1))
Paul 0 Attachment
 In primenumbers@yahoogroups.com, "paulunderwooduk" wrote:>
? {tst(n,x)=kronecker(x^24,n)==1&&
>
>
>  In primenumbers@yahoogroups.com, "paulunderwooduk" wrote:
>
> > gcd(x^3x,n)==1
> > kronecker(x^24,n)==1
> > gcd(x^22,n)==1
> > (L+x^22)^n==L^3+(x^22)*L+(x^22) (mod n, (L^2x*L+1)*(L^2+x*L+1))
>
> I have verified this test for all x for all n<10^6 coprime to 30,
>
gcd(x^3x,n)==1&&
gcd(x^22,n)==1&&
Mod(Mod(1,n)*(L+x^22),(L^2x*L+1)*(L^2+x*L+1))^(n)==L^3+(x^22)*L+x^22;}
? {tstfile("underw297.txt");}
2/297 counterexamples left in underw297.txt
? {tstfile("underw65.txt");}
5146/12846 counterexamples left in underw65.txt
Paul 0 Attachment
 In primenumbers@yahoogroups.com, "paulunderwooduk" wrote:
>
Adding gcd(x^23,n)==1 makes sense because x^22==1 (mod x^23). So the resurrected test is:
> ? {tst(n,x)=kronecker(x^24,n)==1&&
> gcd(x^3x,n)==1&&
> gcd(x^22,n)==1&&
> Mod(Mod(1,n)*(L+x^22),(L^2x*L+1)*(L^2+x*L+1))^(n)==L^3+(x^22)*L+x^22;}
>
> ? {tstfile("underw297.txt");}
> 2/297 counterexamples left in underw297.txt
> ? {tstfile("underw65.txt");}
> 5146/12846 counterexamples left in underw65.txt
>
{tst(n,x)=kronecker(x^24,n)==1&&
gcd(x^3x,n)==1&&
gcd(x^22,n)==1&&
gcd(x^23,n)==1&&
Mod(Mod(1,n)*(L+x^22),(L^2x*L+1)*(L^2+x*L+1))^(n)==L^3+(x^22)*L+x^22;}
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 0 Attachment
 In primenumbers@yahoogroups.com, "paulunderwooduk" wrote:
> {tst(n,x)=kronecker(x^24,n)==1&&
n=2672279 and x=89805 forms a nearcounterexample, saved only by gcd(x^3x,n)==2672279.
> gcd(x^3x,n)==1&&
> gcd(x^22,n)==1&&
> gcd(x^23,n)==1&&
> Mod(Mod(1,n)*(L+x^22),(L^2x*L+1)*(L^2+x*L+1))^(n)==L^3+(x^22)*L+x^22;}
>
Since gcd(x^3x,n)==1 is required I do not have to verify numbers divisible by 2 or 3, and with kronecker(x^24,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^3x,n)==1, kronecker(x^24,n)==1 and gcd(x^22,n)==1, I can skip numbers divisible by 7. All in all, I need only verify numbers coprime to 210,
Paul 0 Attachment
 In primenumbers@yahoogroups.com, "paulunderwooduk" wrote:
> n=2672279 and x=89805 forms a nearcounterexample, saved only by gcd(x^3x,n)==2672279.
That should read gcd(x^23,n)==2672279.
Paul 0 Attachment
 In primenumbers@yahoogroups.com,
"paulunderwooduk" wrote:
> Adding gcd(x^23,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 singleparameter, doubleFrobenius
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 0 Attachment
 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^24,n)==1&&gcd(x^3x,n)==1&&gcd(x^22,n)==1&&
Mod(Mod(1,n)*(L+x^22),(L^2x*L+1)*(L^2+x*L+1))^n==L^3+(x^22)*L+x^22;}
{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^23 to be coprime to n.
David 0 Attachment
 In primenumbers@yahoogroups.com, "djbroadhurst" wrote:
> http://physics.open.ac.uk/~dbroadhu/cert/underwqd.txt.gz
Thanks for these, David. Is it a comprehensive list for all n <= 97847746461047271599?
>
> 352869/352869 counterexamples left in underwqd.txt
>
> All are trapped by Paul's latest wriggle,
> which requires x^23 to be coprime to n.
>
Paul 0 Attachment
 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^24,n)==1&&gcd(x^3x,n)==1&&gcd(x^22,n)==1&&
Mod(Mod(1,n)*(L+x^22),(L^2x*L+1)*(L^2+x*L+1))^n==L^3+(x^22)*L+x^22;}
{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^10smooth 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 0 Attachment
> All are trapped by Paul's latest wriggle,
Exercise: Show that Paul's test
> which requires x^23 to be coprime to n.
Mod(Mod(1,n)*(L+x^22),(L^2x*L+1)*(L^2+x*L+1))^n==L^3+(x^22)*L+x^22
requires n to be a Fermat pseudoprime in base 1+(x^23)*(x^22)^3
and thus loses (at least) one selfridge of potency for x^2 = 3 mod n.
David 0 Attachment
 In primenumbers@yahoogroups.com, "djbroadhurst" wrote:>
? M=[0,(x^22),0,1;1,0,0,0;0,1,0,0;0,0,1,0];matdet(M+x^22)==1+(x^23)*(x^22)^3
>
>
> > All are trapped by Paul's latest wriggle,
> > which requires x^23 to be coprime to n.
>
> Exercise: Show that Paul's test
> Mod(Mod(1,n)*(L+x^22),(L^2x*L+1)*(L^2+x*L+1))^n==L^3+(x^22)*L+x^22
> requires n to be a Fermat pseudoprime in base 1+(x^23)*(x^22)^3
> and thus loses (at least) one selfridge of potency for x^2 = 3 mod n.
>
1
Thanks for the insight.
This can be split into 2 Fermat tests:
? M=[x,1;1,0];matdet(M+x^22)
x^4 + x^3  4*x^2  2*x + 5
? M=[x,1;1,0];matdet(M+x^22)
x^4  x^3  4*x^2 + 2*x + 5
which are equal to:
? M=[x,1;1,0];matdet(M+x^22)==(x^22)*(x+2)*(x1)+1
1
? M=[x,1;1,0];matdet(M+x^22)==(x^22)*(x2)*(x+1)+1
1
Paul 0 Attachment
 In primenumbers@yahoogroups.com, "paulunderwooduk" wrote:
> > loses (at least) one selfridge of potency for x^2 = 3 mod n.
Exercise 2: Show that the test loses 3 selfrides for x^2 = 3 mod n.
> Thanks for the insight.
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 0 Attachment
 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 0 Attachment
 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 1selfridge Euler test, with base 15/16, plus a
2selfridge 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 0 Attachment
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^24,n)==1&&
gcd(x+1,n)==1&&
Mod(Mod(1,n)*(L+x+1),(L^2x*L+1)*(L^2+x*L+1))^(n)==L^3+(x^22)*L+x+1;}
It looks as though when "gcd(x+1,n)==1" is needed then n==5 (mod 6), and any of gcd(x1,n), gcd(x,n), gcd(x^22,n) and gcd(x^33,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 0 Attachment
 In primenumbers@yahoogroups.com, "paulunderwooduk" wrote:>
Further, it seems that if "gcd(x+1,n)" is needed then it is equal to 1 (mod 6)
>
> 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^24,n)==1&&
> gcd(x+1,n)==1&&
> Mod(Mod(1,n)*(L+x+1),(L^2x*L+1)*(L^2+x*L+1))^(n)==L^3+(x^22)*L+x+1;}
>
> It looks as though when "gcd(x+1,n)==1" is needed then n==5 (mod 6), and any of gcd(x1,n), gcd(x,n), gcd(x^22,n) and gcd(x^33,n) greater than 1 is also a prime equal to 5 (mod 6) when "gcd(x+1,n)==1" is required,
>
Paul 0 Attachment
 In primenumbers@yahoogroups.com, "paulunderwooduk" wrote:>
These ancillary statements are mostly false, except that maybe when "gcd(x+1,n)" needs to be checked then gcd(x1,n), gcd(x,n), gcd(x^22,n) and gcd(x^33,n) are either 1 or prime,
>
>
>  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^24,n)==1&&
> > gcd(x+1,n)==1&&
> > Mod(Mod(1,n)*(L+x+1),(L^2x*L+1)*(L^2+x*L+1))^(n)==L^3+(x^22)*L+x+1;}
> >
> > It looks as though when "gcd(x+1,n)==1" is needed then n==5 (mod 6), and any of gcd(x1,n), gcd(x,n), gcd(x^22,n) and gcd(x^33,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 0 Attachment
 In primenumbers@yahoogroups.com, "paulunderwooduk" wrote:
> > >
Please accept my apology for my previous statements about this composite test. I am actually running tests for:
> > > {tst(n,x)=kronecker(x^24,n)==1&&
> > > gcd(x+1,n)==1&&
> > > Mod(Mod(1,n)*(L+x+1),(L^2x*L+1)*(L^2+x*L+1))^(n)==L^3+(x^22)*L+x+1;}
> > >
(mod n, L^2x*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 x1, x, x+1, x^22 and x^23 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 x1, x^22 and x^23 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 0 Attachment
 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^24,n)==1&&
> > > > gcd(x+1,n)==1&&
> > > > Mod(Mod(1,n)*(L+x+1),(L^2x*L+1)*(L^2+x*L+1))^(n)==L^3+(x^22)*L+x+1;}
> > > >
>
{tst(n,x)=kronecker(x^24,n)==1&&
gcd(x^21,n)==1&&
Mod(Mod(1,n)*(L+x^21),(L^2x*L+1)*(L^2+x*L+1))^(n)==L^3+(x^22)*L+x^21;}
Paul 0 Attachment
 In primenumbers@yahoogroups.com, "paulunderwooduk" wrote:
> Here is another test, on the same theme, for which I cannot also easily find a fraud:
n=2953711;x=285843 is a nearcounterexample that comes from me testing over the two quadratics that form the quartic. gcd(x,n)==95281 and gcd(x^22,n)==31,
>
> {tst(n,x)=kronecker(x^24,n)==1&&
> gcd(x^21,n)==1&&
> Mod(Mod(1,n)*(L+x^21),(L^2x*L+1)*(L^2+x*L+1))^(n)==L^3+(x^22)*L+x^21;}
>
Paul 0 Attachment
>  In primenumbers@yahoogroups.com, "paulunderwooduk" wrote:
n=1934765;x=1219266 has gcd(x1,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...
>
>
> > > >
> > > > {tst(n,x)=kronecker(x^24,n)==1&&
> > > > gcd(x+1,n)==1&&
> > > > Mod(Mod(1,n)*(L+x+1),(L^2x*L+1)*(L^2+x*L+1))^(n)==L^3+(x^22)*L+x+1;}
> > > >
>
> Please accept my apology for my previous statements about this composite test. I am actually running tests for:
> (mod n, L^2x*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 x1, x, x+1, x^22 and x^23 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 x1, x^22 and x^23 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
I have verified all n<1.95*10^6
>
> 4) the logged n are all congruent to 5 (mod 6).
>
Paul
Your message has been successfully submitted and would be delivered to recipients shortly.