## Re: single frobenius and double fermat

Expand Messages
• ... I edited the sign typo. Paul
Message 1 of 24 , Dec 9 6:59 AM
> The test I am now verifying is:
>
> gcd(x^3-x,n)==1
> kronecker(x^2-4,n)==-1
> (x-2)^((n-1)/2)==kronecker(x-2,n) (mod n)
> (x+2)^((n-1)/2)==kronecker(x+2,n) (mod n)
> (x*L^3+1)^(n+1)==(x^2-1)^2 (mod n, L^2-x*L+1)
>

I edited the sign typo.

Paul
• ... I think the frobenius sub-test can be simplified to: ((x^2-1)*L)^(n+1)==(x^2-1)^2 (mod n, L^2-x*L+1) Paul
Message 2 of 24 , Dec 9 8:01 AM
--- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:
>
>
> > The test I am now verifying is:
> >
> > gcd(x^3-x,n)==1
> > kronecker(x^2-4,n)==-1
> > (x-2)^((n-1)/2)==kronecker(x-2,n) (mod n)
> > (x+2)^((n-1)/2)==kronecker(x+2,n) (mod n)
> > (x*L^3+1)^(n+1)==(x^2-1)^2 (mod n, L^2-x*L+1)
> >
>

I think the frobenius sub-test can be simplified to:

((x^2-1)*L)^(n+1)==(x^2-1)^2 (mod n, L^2-x*L+1)

Paul
• ... {tst(n,x)=gcd(x^3-x,n)==1&&kronecker(x^2-4,n)==-1&& Mod(x-2,n)^((n-1)/2)==kronecker(x-2,n)&& Mod(x+2,n)^((n-1)/2)==kronecker(x+2,n)&&
Message 3 of 24 , Dec 10 7:25 AM
"paulunderwooduk" <paulunderwood@...> wrote:

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

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

print(sum(k=1,#v,tst(v[k][1],v[k][2]))" counterexamples");}

19959 counterexamples

David
• ... Thanks again, David. I had an mistake in one of my equations that caused erroneous checking of your files. I have another test. For small x, and choosing
Message 4 of 24 , Dec 10 1:28 PM
>
>
>
> "paulunderwooduk" <paulunderwood@> wrote:
>
> > gcd(x^3-x,n)==1
> > kronecker(x^2-4,n)==-1
> > (x-2)^((n-1)/2)==kronecker(x-2,n) (mod n)
> > (x+2)^((n-1)/2)==kronecker(x+2,n) (mod n)
> > (x*L^3+1)^(n+1)==(x^2-1)^2 (mod n, L^2-x*L+1)
>
> {tst(n,x)=gcd(x^3-x,n)==1&&kronecker(x^2-4,n)==-1&&
> Mod(x-2,n)^((n-1)/2)==kronecker(x-2,n)&&
> Mod(x+2,n)^((n-1)/2)==kronecker(x+2,n)&&
> Mod(Mod(1,n)*(x*L^3+1),L^2-x*L+1)^(n+1)==(x^2-1)^2;}
>
> print(sum(k=1,#v,tst(v[k][1],v[k][2]))" counterexamples");}
>
> 19959 counterexamples
>

Thanks again, David. I had an mistake in one of my equations that caused erroneous checking of your files.

I have another test. For small x, and choosing where possible x==3 or x==6, the test is on average 3.25 selfridge. For n co-prime to 30 find any x:

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

I this tested against your files:

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

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
• ... should be: ((x^3-x)*(L^2-4))^(n+1)==(x^3-x)^2*(25-4*x^2) (mod n, L^2-x*L+1) Paul
Message 5 of 24 , Dec 10 1:32 PM
> (x^3-x)*(L^2-4)^(n+1)==(x^3-x)^2*(25-4*x^2) (mod n, L^2-x*L+1)

should be:

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

Paul
• ... {tst(n,x)=kronecker(x^2-4,n)==-1&&gcd(x^3-x,n)==1&& Mod(x-2,n)^((n-1)/2)==kronecker(x-2,n)&& Mod(x+2,n)^((n-1)/2)==kronecker(x+2,n)&&
Message 6 of 24 , Dec 10 3:23 PM
"paulunderwooduk" <paulunderwood@...> wrote:

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

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

{if(tst(115886944289,3692152318),print("fooled"));}

fooled

David
• ... Thanks. Here is another composite test: {tst(n,x)=kronecker(x^2-4,n)==-1&&gcd(x^3-x,n)==1&&kronecker(x^2-1,n)==-1&&
Message 7 of 24 , Dec 10 3:44 PM
>
>
>
> "paulunderwooduk" <paulunderwood@> wrote:
>
> > gcd(x^3-x,n)==1
> > kronecker(x^2-4,n)==-1
> > (x-2)^((n-1)/2)==kronecker(x-2,n) (mod n)
> > (x+2)^((n-1)/2)==kronecker(x+2,n) (mod n)
> > (x^3-x)*(L^2-4)^(n+1)==(x^3-x)^2*(25-4*x^2) (mod n, L^2-x*L+1)
>
> {tst(n,x)=kronecker(x^2-4,n)==-1&&gcd(x^3-x,n)==1&&
> Mod(x-2,n)^((n-1)/2)==kronecker(x-2,n)&&
> Mod(x+2,n)^((n-1)/2)==kronecker(x+2,n)&&
> Mod(Mod(1,n)*(x^3-x)*(L^2-4),L^2-x*L+1)^(n+1)==
> (x^3-x)^2*(25-4*x^2);}
>
> {if(tst(115886944289,3692152318),print("fooled"));}
>
> fooled
>

Thanks. Here is another composite test:

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

It's on average about 5 selfridge for carefully chosen x,

Paul
• ... Generically, that is 7 selfridges: 4 Euler tests and one Frobenius. However, it s reasonably easy to fool:
Message 8 of 24 , Dec 10 4:18 PM
"paulunderwooduk" <paulunderwood@...> wrote:

> Here is another composite test
> It's on average about 5 selfridge

Generically, that is 7 selfridges: 4 Euler tests
and one Frobenius. However, it's reasonably easy to fool:

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

{if(tst(312432294658994604401,2805168083964928859),
print(fooled));}

fooled

David

> It's on average about 5 selfridge for carefully chosen x,
>
> Paul
>
• ... Thanks once more. Now a last ditch test: {tst(n,x)=kronecker(x^2-4,n)==-1&&gcd(x^3-x,n)==1&& kronecker(x^2-1,n)==-1&&
Message 9 of 24 , Dec 10 4:30 PM
>
> "paulunderwooduk" <paulunderwood@> wrote:
>
> > Here is another composite test
> > It's on average about 5 selfridge
>
> Generically, that is 7 selfridges: 4 Euler tests
> and one Frobenius. However, it's reasonably easy to fool:
>
> {tst(n,x)=kronecker(x^2-4,n)==-1&&gcd(x^3-x,n)==1&&
> kronecker(x^2-1,n)==-1&&
> Mod(x-2,n)^((n-1)/2)==kronecker(x-2,n)&&
> Mod(x+2,n)^((n-1)/2)==kronecker(x+2,n)&&
> Mod(x-1,n)^((n-1)/2)==kronecker(x-1,n)&&
> Mod(x+1,n)^((n-1)/2)==kronecker(x+1,n)&&
> Mod(Mod(1,n)*x*(L^2-4),L^2-x*L+1)^(n+1)==x^2*(25-4*x^2);}
>
> {if(tst(312432294658994604401,2805168083964928859),
> print(fooled));}
>
> fooled
>

Thanks once more. Now a last ditch test:

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

Paul
• ... That s 5 + 3 = 8 selfrideges, but still easy to fool: {tst(n,x)=kronecker(x^2-4,n)==-1&&gcd(x^3-x,n)==1&& kronecker(x^2-1,n)==-1&&
Message 10 of 24 , Dec 10 4:41 PM
"paulunderwooduk" <paulunderwood@...> wrote:

> Now a last ditch test

That's 5 + 3 = 8 selfrideges, but still easy to fool:

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

{if(tst(28928708996670209,9176237087918226),
print(fooled));}
• ... Moreover, we may allow 7 Euler tests before the Frobenius test and still obtain a counterexample: {tst(n,x)=kronecker(x^2-4,n)==-1&&gcd(x^3-x,n)==1&&
Message 11 of 24 , Dec 11 8:32 AM

> > Now a last ditch test
> That's 5 + 3 = 8 selfridges, but still easy to fool

Moreover, we may allow 7 Euler tests before the
Frobenius test and still obtain a counterexample:

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

{if(tst(500813768599682335601,104655233442347018047),
print(fooled));}

fooled

David
• I have another new composite test for odd n: {tst(n,x)=kronecker(x^2-4,n)==-1&&gcd(x,n)==1&& Mod(x-2,n)^((n-1)/2)==kronecker(x-2,n)&&
Message 12 of 24 , Dec 11 8:44 AM
I have another new composite test for odd n:

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

Since for x==1,3 or 6 it is 3 selfridge, a single test with carefully chosen small x is on average 3.125 selfridge,

Paul
• ... {tst(n,x)=kronecker(x^2-4,n)==-1&&gcd(x,n)==1&& Mod(x-2,n)^((n-1)/2)==kronecker(x-2,n)&& Mod(x+2,n)^((n-1)/2)==kronecker(x+2,n)&&
Message 13 of 24 , Dec 11 9:53 AM
"paulunderwooduk" <paulunderwood@...> wrote:

> I have another new composite test

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

{quote=" Vain are the thousand creeds that move men's hearts,
unutterably vain, worthless as wither'd weeds.";
if(tst(10538495213,2237176843),print(quote));}

Vain are the thousand creeds that move men's hearts,
unutterably vain, worthless as wither'd weeds.

David (per proxy Emily)
• Here yet another new composite test. This time there is a sneaky use of 2: {tst(n,x)=kronecker(x^2-4,n)==-1&&gcd(x,n)==1&&
Message 14 of 24 , Dec 11 1:02 PM
Here yet another new composite test. This time there is a sneaky use of 2:

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

Paul
• ... But still easy to fool: {tst(n,x)=kronecker(x^2-4,n)==-1&&gcd(x,n)==1&& Mod(x-2,n)^((n-1)/2)==kronecker(x-2,n)&& Mod(x+2,n)^((n-1)/2)==kronecker(x+2,n)&&
Message 15 of 24 , Dec 11 2:40 PM
"paulunderwooduk" <paulunderwood@...> wrote:

> Here yet another new composite test.
> This time there is a sneaky use of 2

But still easy to fool:

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

{if(tst(37423804289,10332300710),print(fooled));}

fooled

David
• ... Thanks David. However, I am going to be even more devious with this 3.5 selfridge test for small x: {tst(n,x)=kronecker(x^2-4,n)==-1&&gcd(x,n)==1&&
Message 16 of 24 , Dec 11 3:48 PM

> fooled

Thanks David. However, I am going to be even more devious with this 3.5 selfridge test for small x:

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

Paul
• ... Maybe I can make this 3.125 selfridge for small x by removing the first multiplier 4 and using x=1,3 and 6 where possible Paul
Message 17 of 24 , Dec 11 4:15 PM
--- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:
>
>
>
>
> > fooled
>
> Thanks David. However, I am going to be even more devious with this 3.5 selfridge test for small x:
>
> {tst(n,x)=kronecker(x^2-4,n)==-1&&gcd(x,n)==1&&
> Mod(4*(x-2),n)^((n-1)/2)==kronecker(x-2,n)&&
> Mod(4*(x+2),n)^((n-1)/2)==kronecker(x+2,n)&&
> Mod(Mod(1,n)*2*(L^2-4),L^2-x*L+1)^(n+1)==4*(25-4*x^2);}
>

Maybe I can make this 3.125 selfridge for small x by removing the first multiplier 4 and using x=1,3 and 6 where possible

Paul
• ... Not really. Sticking in powers of 2 does not make forgery any harder. {tst(n,x)=kronecker(x^2-4,n)==-1&&gcd(x,n)==1&&
Message 18 of 24 , Dec 12 2:23 AM
"paulunderwooduk" <paulunderwood@...> wrote:

> I am going to be even more devious

Not really. Sticking in powers of 2 does not
make forgery any harder.

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

{if(tst(115886944289,3692152318),print(fooled));}

fooled

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