## Re: double frobenius with gcds

Expand Messages
• ... {tst(n,x,a)=2
Message 1 of 8 , Dec 3, 2012
• 0 Attachment
"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 2 of 8 , Dec 3, 2012
• 0 Attachment
>
>
>
> "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 3 of 8 , Dec 4, 2012
• 0 Attachment
"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);}