## 25211Re: Fermat+Euler+Frobenius

Expand Messages
• Jul 17, 2013
>
>
>
> --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@> wrote:
>
> > In pari-speak:
> > {tst(n,a)=kronecker(a^2-1,n)==-1&&
> > gcd(a,n)==1&&
> > Mod(a^2-1,n)^((n-1)/2)==-1&&
> > Mod(a^2-9,n)^(n-1)==1&&
> > Mod(Mod(1,n)*(L+a),L^2-2*a*L+1)^(n+1)==3*a^2+1;}
>
> {tst(n,a)=kronecker(a^2-1,n)==-1&&gcd(a,n)==1&&
> Mod(a^2-1,n)^((n-1)/2)==-1&&Mod(a^2-9,n)^(n-1)==1&&
> Mod(Mod(1,n)*(L+a),L^2-2*a*L+1)^(n+1)==3*a^2+1;}
>
> {n=18716367291828127605803202146374280131174122610218950329243\
> 75370060752249858742800088185928944839179221397424300401208101;
>
> a=46354990728672473357718750501279519419666866604904480070651\
> 7441641353515300610340484778232167914470462548902372399325637;
>
> if(tst(n,a)&&!isprime(n),print(" Gremlins are happy"));}
>
> Gremlins are happy
>

Thanks very much for the counterexample!

I was unhappy about the way the base x^2-9 Fermat PRP test was bolted on. I have revised the test, splitting a^2-1 into two Euler PRP tests, and taking a base a Fermat PRP test:

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

Again, the Gremlins should be able to dispatch it with a counterexample,

Paul
• Show all 24 messages in this topic