Loading ...
Sorry, an error occurred while loading the content.

25211Re: Fermat+Euler+Frobenius

Expand Messages
  • paulunderwooduk
    Jul 17, 2013
    • 0 Attachment
      --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
      >
      >
      >
      > --- 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