Browse Groups

• ... but meant to write x^2-4, not x^4-2
Message 1 of 26 , Jan 9
View Source
> With kronecker(x^4-2,n) = -1
but meant to write x^2-4, not x^4-2
• ... Thanks for the algebra -- it was worrying me. Yes, the gremlins will not like this test: gcd(x^3-x,n) kronecker(x^2-4,n)==-1 gcd(x^2-2,n)==1
Message 1 of 26 , Jan 9
View Source
>
>
>
> Paul Underwood wrote:
>
> > (L+2)^n==-L^3+(x^2-2)*L+2 (mod n, (L^2-x*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^2-4,n) = -1 and prime n, we have
>
> (L+a)^n = a+x-L mod(n, L^2-L*x+1) ... [1]
> (L+a)^n = a-x-L 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^2-2)*L and observe
> from simple algebra (no modularity involved) that
>
> f(x,L) + a = (a+x-L) - (L+x)*(L^2-x*L+1)
> f(x,L) + a = (a-x-L) - (L-x)*(L^2+x*L+1)
>
> Hence [1] and [2] imply that
>
> (L+a)^n = f(x,L) + a mod(n, (L^2-x*L+1)*(L^2+x*L+1)) ... [3]
>
> and Paul has set a = 2 in [3].
>
> Since this is a double-Frobenius test, the gremlins
> reserve the right to choose /both/ parameters (a,x) in [3].
>

Thanks for the algebra -- it was worrying me.

Yes, the gremlins will not like this test:

gcd(x^3-x,n)
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))

Paul
• ... I have verified this test for all x for all n
Message 1 of 26 , Jan 10
View Source

> 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 1 of 26 , Jan 11
View Source
>
>
>
> --- 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 1 of 26 , Jan 11
View Source

>
> ? {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:

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 1 of 26 , Jan 15
View Source

> {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 1 of 26 , Jan 15
View Source

> n=2672279 and x=89805 forms a near-counterexample, saved only by gcd(x^3-x,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 1 of 26 , Jan 15
View Source
"paulunderwooduk" wrote:

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
test, yet the prospects of finding one, now that you
have bolted the stable door, seem to be minuscule.

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 1 of 26 , Jan 17
View Source
"paulunderwooduk" wrote:

> n=2672279 and x=89805

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;}

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 1 of 26 , Jan 17
View Source

>
> 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 1 of 26 , Jan 17
View Source
"paulunderwooduk" wrote:

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

By no means. However the updated file
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;}

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 1 of 26 , Jan 18
View Source
> 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 1 of 26 , Jan 18
View Source
>
>
>
> > 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 1 of 26 , Jan 18
View Source

> > 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 1 of 26 , Jan 18
View Source
> 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 1 of 26 , Jan 18
View Source

> 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 1 of 26 , Jan 19
View Source
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 1 of 26 , Jan 19
View Source
>
>
> 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 1 of 26 , Jan 19
View Source
>
>
>
> --- 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 1 of 26 , Jan 19
View Source

> > >
> > > {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;}
> > >

(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 1 of 26 , Jan 21
View Source

>
> > > >
> > > > {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 1 of 26 , Jan 27
View Source

> 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 1 of 26 , Jan 30
View Source
> --- 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;}
> > > >
>
> (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.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.