double frobenius with gcds

Expand Messages
• Hi, I have a new composite test for odd n with any x and a: 2
Message 1 of 8 , Dec 2 2:46 PM
Hi,

I have a new composite test for odd n with any x and a:
2<x<(n+1)/2
1<a<(n+1)/2:
kronecker(x^2-4,n)==-1
gcd(a^3-a,n)==1
gcd(a,x)==1

with sub-tests:
(L+a)^(n+1)==a*x+a^2+1 (mod n, L^2-x*L+1)
(L-a)^(n+1)==-a*x+a^2+1 (mod n, L^2-x*L+1)

(If x and a are small this is a 2+2 selfridge test.)

I have done a shallow (triple loop) verification for n<4000

Can you find a counterexample?

a=x+1 can be verified with a double loop :-) True for n<42000

Paul
• ... {tst(n,x,a)=2
Message 2 of 8 , Dec 2 9:48 PM
"paulunderwooduk" <paulunderwood@...> wrote:

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

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

{F=[[33877678503145357571, 3952030303250180277, 966200491166451083],
[295057250504883381551, 127751371818177523954, 8822853390661898603],
[429749641620836200211, 69208918734832269040, 200208504884456069347]];
print(sum(k=1,#F,tst(F[k][1],F[k][2],F[k][3]))" counterexamples");}

3 counterexamples

David
• ... I notice these 3 have kronecker(x,n)==1. So I wriggle with this test: kronecker(x^2-4,n)==-1 kronecker(x,n)==-1 gcd(a,n)==1 (L+a)^(n+1)==a*x+a^2+1 (mod n,
Message 3 of 8 , Dec 3 12:38 PM
>
>
>
> "paulunderwooduk" <paulunderwood@> wrote:
>
> > 2<x<(n+1)/2
> > 1<a<(n+1)/2:
> > kronecker(x^2-4,n)==-1
> > gcd(a^3-a,n)==1
> > gcd(a,x)==1
> > (L+a)^(n+1)==a*x+a^2+1 (mod n, L^2-x*L+1)
> > (L-a)^(n+1)==-a*x+a^2+1 (mod n, L^2-x*L+1)
>
> {tst(n,x,a)=2<x&&x<(n+1)/2&&1<a&&a<(n+1)/2&&
> kronecker(x^2-4,n)==-1&&gcd(a^3-a,n)==1&&gcd(a,x)==1&&
> Mod(Mod(1,n)*(L+a),L^2-x*L+1)^(n+1)==(a^2+1+a*x)&&
> Mod(Mod(1,n)*(L-a),L^2-x*L+1)^(n+1)==(a^2+1-a*x)&&!isprime(n);}
>
> {F=[[33877678503145357571, 3952030303250180277, 966200491166451083],
> [295057250504883381551, 127751371818177523954, 8822853390661898603],
> [429749641620836200211, 69208918734832269040, 200208504884456069347]];
> print(sum(k=1,#F,tst(F[k][1],F[k][2],F[k][3]))" counterexamples");}
>
> 3 counterexamples

I notice these 3 have kronecker(x,n)==1. So I wriggle with this test:

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

Putting a=1 with x small is most efficient,

Paul
• ... Last minute wriggle: gcd(a^3-a,n)==1 Paul
Message 4 of 8 , Dec 3 1:01 PM
--- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:
>
>
>
> >
> >
> >
> > "paulunderwooduk" <paulunderwood@> wrote:
> >
> > > 2<x<(n+1)/2
> > > 1<a<(n+1)/2:
> > > kronecker(x^2-4,n)==-1
> > > gcd(a^3-a,n)==1
> > > gcd(a,x)==1
> > > (L+a)^(n+1)==a*x+a^2+1 (mod n, L^2-x*L+1)
> > > (L-a)^(n+1)==-a*x+a^2+1 (mod n, L^2-x*L+1)
> >
> > {tst(n,x,a)=2<x&&x<(n+1)/2&&1<a&&a<(n+1)/2&&
> > kronecker(x^2-4,n)==-1&&gcd(a^3-a,n)==1&&gcd(a,x)==1&&
> > Mod(Mod(1,n)*(L+a),L^2-x*L+1)^(n+1)==(a^2+1+a*x)&&
> > Mod(Mod(1,n)*(L-a),L^2-x*L+1)^(n+1)==(a^2+1-a*x)&&!isprime(n);}
> >
> > {F=[[33877678503145357571, 3952030303250180277, 966200491166451083],
> > [295057250504883381551, 127751371818177523954, 8822853390661898603],
> > [429749641620836200211, 69208918734832269040, 200208504884456069347]];
> > print(sum(k=1,#F,tst(F[k][1],F[k][2],F[k][3]))" counterexamples");}
> >
> > 3 counterexamples
>
> I notice these 3 have kronecker(x,n)==1. So I wriggle with this test:
>
> kronecker(x^2-4,n)==-1
> kronecker(x,n)==-1
> gcd(a,n)==1
> (L+a)^(n+1)==a*x+a^2+1 (mod n, L^2-x*L+1)
> (L-a)^(n+1)==-a*x+a^2+1 (mod n, L^2-x*L+1)
>

Last minute wriggle:
gcd(a^3-a,n)==1

Paul
• ... n==3281 lead to the above wriggle. I could have used the following wriggle instead: gcd(x^2-1,n), which would allow a==1 Paul
Message 5 of 8 , Dec 3 1:30 PM
> > kronecker(x^2-4,n)==-1
> > kronecker(x,n)==-1
> > gcd(a,n)==1
> > (L+a)^(n+1)==a*x+a^2+1 (mod n, L^2-x*L+1)
> > (L-a)^(n+1)==-a*x+a^2+1 (mod n, L^2-x*L+1)
> >
>
> Last minute wriggle:
> gcd(a^3-a,n)==1

n==3281 lead to the above wriggle. I could have used the following wriggle instead:

gcd(x^2-1,n), which would allow a==1

Paul
• ... {tst(n,x,a)=2
Message 6 of 8 , Dec 3 2:27 PM
"paulunderwooduk" <paulunderwood@...> wrote:

> I wriggle with this test:
> kronecker(x,n)==-1

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

{if(tst(429749641620836200211,69208918734832269040,
200208504884456069347),print("fooled"));}

fooled

David
• ... Well done. Thanks, Paul
Message 7 of 8 , Dec 3 3:11 PM
>
>
>
> "paulunderwooduk" <paulunderwood@> wrote:
>
> > I wriggle with this test:
> > kronecker(x,n)==-1
>
> {tst(n,x,a)=2<x&&x<(n+1)/2&&1<a&&a<(n+1)/2&&
> kronecker(x^2-4,n)==-1&&gcd(a^3-a,n)==1&&gcd(a,x)==1&&
> Mod(Mod(1,n)*(L+a),L^2-x*L+1)^(n+1)==(a^2+1+a*x)&&
> Mod(Mod(1,n)*(L-a),L^2-x*L+1)^(n+1)==(a^2+1-a*x)&&!isprime(n);}
>
> {if(tst(429749641620836200211,69208918734832269040,
> 200208504884456069347),print("fooled"));}
>
> fooled
>

Well done. Thanks,

Paul
• ... After I worked out to how to forge one counterexample, the gremlins were able to find more than 21,000: {tst(n,x,a)=2
Message 8 of 8 , Dec 4 7:49 AM
"paulunderwooduk" <paulunderwood@...> wrote:

> > {if(tst(429749641620836200211,69208918734832269040,
> > 200208504884456069347),print("fooled"));}
> > fooled
> Well done. Thanks

After I worked out to how to forge one counterexample,
the gremlins were able to find more than 21,000:

{tst(n,x,a)=2<x&&x<(n+1)/2&&1<a&&a<(n+1)/2&&
kronecker(x^2-4,n)==-1&&gcd(a^3-a,n)==1&&gcd(a,x)==1&&
kronecker(x,n)==-1&& \\ added wriggle from Paul
Mod(2,n)^(n-1)==1&&n%12==11&& \\ by construction
Mod(Mod(1,n)*(L+a),L^2-x*L+1)^(n+1)==(a^2+1+a*x)&&
Mod(Mod(1,n)*(L-a),L^2-x*L+1)^(n+1)==(a^2+1-a*x)&&!isprime(n);}