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

Re: sufficent test for prime mod 4 = 3 ?

Expand Messages
  • djbroadhurst
    ... This looks to be hard to fool, since it is very similar to BPSW. However it is wilful nonsense to claim that such a test proves primality. Please replace
    Message 1 of 4 , Oct 24, 2010
    • 0 Attachment
      --- In primenumbers@yahoogroups.com,
      "bhelmes_1" <bhelmes@...> wrote:

      > let be b the smallest non quadric residium.
      > Necessary: b^((p-1)/2)=p-1 mod p
      > Sufficent: (b+I)^p = b^p + I^p = b - I

      This looks to be hard to fool, since it is very similar to BPSW.
      However it is wilful nonsense to claim that such a test
      proves primality. Please replace "suffic[i]ent" by "necessary".

      David
    • djbroadhurst
      ... It s very easy to fool your test, in that case: {tst(n,b)=n%4==3&&kronecker(b,n)==-1&& Mod(b,n)^((n-1)/2)==-1&& Mod(Mod(1,n)*(b+x),x^2+1)^n==b-x;}
      Message 2 of 4 , Oct 24, 2010
      • 0 Attachment
        --- In primenumbers@yahoogroups.com,
        "bhelmes_1" <bhelmes@...> wrote:

        > there might be counterexamples if you do not take the smallest b

        It's very easy to fool your test, in that case:

        {tst(n,b)=n%4==3&&kronecker(b,n)==-1&&
        Mod(b,n)^((n-1)/2)==-1&&
        Mod(Mod(1,n)*(b+x),x^2+1)^n==b-x;}

        if(tst(337*3079,298117),print(fooled));

        fooled

        David
      • djbroadhurst
        ... Wrong again. You are still using 1+3=4 selfridges. Please see Theorem 3.5.8 of Crandall and Pomerance. David
        Message 3 of 4 , Oct 24, 2010
        • 0 Attachment
          --- In primenumbers@yahoogroups.com,
          "bhelmes_1" <bhelmes@...> wrote:

          > The good news is that the test "only" need 3 Selfridges

          Wrong again. You are still using 1+3=4 selfridges.
          Please see Theorem 3.5.8 of Crandall and Pomerance.

          David
        Your message has been successfully submitted and would be delivered to recipients shortly.