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

25230Re: Fermat+Euler+Frobenius

Expand Messages
  • djbroadhurst
    Jul 18, 2013
    • 0 Attachment
      --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:

      > strong tests

      When n = 3 mod 4, Euler is identical to Miller-Rabin,
      since (n-1)/2 is odd.

      Now suppose that n = 3 mod 8 and kronecker(Q,n) = +1.
      Then the only stengthening of Lucas is to show that
      L^((n+1)/4) (mod all that other stuff) is +1 or -1.
      since (n+1)/4 is odd.

      {wriggle(a,n)=local(v=[a,3*a^2+1,5*a^2-1,13*a^2-1,7*a^2-3]);
      sum(k=1,#v,gcd(v[k],n)>1)==0;}

      {tst3mod8(n,a)=local(Q=3*a^2+1);kronecker(a^2-1,n)==-1&&wriggle(a,n)&&
      !isprime(n)&&n%8==3&&kronecker(Q,n)==1&& \\ just to keep Paul happy
      Mod(a,n)^((n-1)/2)==kronecker(a,n)&&
      Mod(a-1,n)^((n-1)/2)==kronecker(a-1,n)&&
      Mod(a+1,n)^((n-1)/2)==kronecker(a+1,n)&&
      Mod(Q,n)^((n-1)/2)==kronecker(Q,n)&&(
      Mod(Mod(1,n)*L,L^2-lift(Mod((10*a^2-2)/Q,n))*L+1)^((n+1)/4)==+1||
      Mod(Mod(1,n)*L,L^2-lift(Mod((10*a^2-2)/Q,n))*L+1)^((n+1)/4)==-1);}

      {if(tst3mod8(1080534578729388602707,3487806307751356235),
      print(" Done!"));}

      Done!

      David
    • Show all 24 messages in this topic