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

25213Re: Fermat+Euler+Frobenius

Expand Messages
  • paulunderwooduk
    Jul 17 4:45 AM
    • 0 Attachment
      --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
      >
      >
      >
      > --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@> wrote:
      >
      > > 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;}
      >
      > {n=31697716280285842787610420513509511868804379491893713448780\
      > 6358754802735691573982500580207945833235746240642215059880131;
      >
      > a=40853822175568028716278531675520419155854660549527670445689\
      > 819017030971582165228461513744662732756872644954382722169002;
      >
      > if(tst(n,a)&&!isprime(n),print(" Gremlins are still happy"));}
      >
      > Gremlins are still happy
      >

      Thanks for a quick counterexample.

      I am clutching at straws, but I notice Mod(a,n)^((n-1)/2) is neither 1 nor -1.

      I am trying to figure out how to strengthen the Frobenius PRP test...

      Paul
    • Show all 24 messages in this topic