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

Re: Proposition for a better p-1 and p+1 test

Expand Messages
  • djbroadhurst
    ... So remove point (5) to allow primes p = 1 mod 4. Then it s /very/ easy to find a pseudoprime: {p=3281;x=1062;y=1600; if(kronecker(3,p)==-1&&
    Message 1 of 14 , Sep 14 5:32 PM
    • 0 Attachment
      Bernhard Helmes wrote:

      > > As remarked, no prime p = 1 mod 4 passes the test.
      > I would like to add that only the point 5. causes the trouble.

      So remove point (5) to allow primes p = 1 mod 4.
      Then it's /very/ easy to find a pseudoprime:

      {p=3281;x=1062;y=1600;
      if(kronecker(3,p)==-1&&
      Mod(3,p)^((p-1)/2)==-1&&
      x^2-3*y^2==Mod(1,p)&&
      Mod(Mod(1,p)*(x+y*A),A^2-3)^p==x-y*A&&
      !isprime(p),print(" fooled"));}

      fooled

      David
    • djbroadhurst
      ... The gremlins now have more than 23,000 pseudoprimes that fool Bernhard s test. But before revealing them, they await a response to the very simple case,
      Message 2 of 14 , Sep 20 11:04 AM
      • 0 Attachment
        --- In primenumbers@yahoogroups.com,
        "djbroadhurst" <david.broadhurst@...> wrote:

        > {p=3281;x=1062;y=1600;
        > if(kronecker(3,p)==-1&&
        > Mod(3,p)^((p-1)/2)==-1&&
        > x^2-3*y^2==Mod(1,p)&&
        > Mod(Mod(1,p)*(x+y*A),A^2-3)^p==x-y*A&&
        > !isprime(p),print(" fooled"));}
        >
        > fooled

        The gremlins now have more than 23,000 pseudoprimes
        that fool Bernhard's test. But before revealing them,
        they await a response to the very simple case, above.

        David
      • bhelmes_1
        Dear David, the amount of counterexamples sounds impressively. I suppose that there are a lot of p=1 mod 4. I think that i will publish soon a test which
        Message 3 of 14 , Sep 21 3:32 AM
        • 0 Attachment
          Dear David,

          the amount of counterexamples sounds impressively.
          I suppose that there are a lot of p=1 mod 4.
          I think that i will publish soon a test which separates between p=1 mod 4 and p=3 mod 4,
          but i would like to check first some list by myself in order to save some time for you and to get
          some more informations.

          How does it feel to be a "keeper" of such a lot of interesting gremlins :-)

          A new and better proposition:

          A. Let p an element of N with p=3 mod 4,
             m the greatest power of 2 with 2^m*r=p+1
             and 2^m < r
           
          1. choose a prime a with jacobi (a, p)=-1
          2. Verify a^(p-1)/2=-1 mod p
          3. Depending on the a choose the pell solution of x, y with
             x^2-ay^2=1 mod p
             http://mathworld.wolfram.com/PellEquation.html
          4. Verify that (x+yA)^(2^m)<>1 mod p  with A=sqrt (a)
             because gcd (p-1, p+1) = 2
          5. Calculate and verify (x+yA)^p=x-yA mod p
          6. Calculate (x+yA)^r=x(r)+y(r)A mod p and
             verify that  gcd (y(r), p)=1

             (The point 6. derives of a factorisation test, is cheap and powerful
              because gcd (y(n), p) > 1 results gcd (y(m), p) > 1 with m=n*t)

          if 1.-6. is ok. then p is a prime.

          David, you will realize that i abstain form the choose of the smallest a
          and that i add the point 4. for good reasons

          I wish you a peaceful and pleasant weekend
          Bernhard
        • djbroadhurst
          ... The gremlins refuse to consider a test that is not true for primes. Consider, for example, the prime p = 1037*2^8-1 = 265471 and set a = 3, x = 2, y = 1.
          Message 4 of 14 , Sep 21 4:50 AM
          • 0 Attachment
            Bernhard Helmes wrote:

            > A new and better proposition

            The gremlins refuse to consider a
            test that is not true for primes.

            Consider, for example, the prime
            p = 1037*2^8-1 = 265471
            and set a = 3, x = 2, y = 1.

            Then this prime fails your latest wriggle:

            > (x+yA)^(2^m)<>1 mod p with A=sqrt(a)

            print(Mod(Mod(1,265471)*(2+A),A^2-3)^(2^8));
            Mod(Mod(1, 265471), A^2 - 3)

            Please do not post probable primality "tests"
            that are failed by primes.

            David (trying to control the grumpy gremlins:-)
          • bhelmes_1
            A peaceful day for all group members, dear David, I changed only the point 3. Is this changement a sharper condition or is this mathematically seen the same ?
            Message 5 of 14 , Oct 12, 2013
            • 0 Attachment

              A peaceful day for all group members,

              dear David,


              I changed only the point 3.

              Is this changement a sharper condition or is this mathematically seen the same ?


              I. For p=3 mod 4


              1. choose the smallest prime a with jacobi (a, p)=-1
              2. Verify a^(p-1)/2=-1 mod p
                  [This is the p-1 test which proves that a is a non quadric residuum]
              3. Depending on the a choose the pell solution of x, y with
                  x^2-ay^2=-1 mod p (the minus is the change :-)
              4. Calculate and verify (x+yA)^p=x-yA mod p with A=sqrt (a)
              5. m the greatest power of 2 with 2^m*r=p+1 and 2^m < r

                  Calculate (x+yA)^r=x(r)+y(r)A mod p and
                 verify that  gcd (y(r), p)=1
                 [This is a strong p+1 test with a solution of the according pell equation]
               
              if 1. - 5. is true then p should be a prime


              I think that this "wriggle" will include that there exist a cycle group with order t > 2 and t | r

              There is no need to hurry up for the gremlins,
              the prime numbers will exist a little longer. ;-)

              Friendly greetings from the primes
              Bernhard

            • djbroadhurst
              ... For a=3 mod 4 there is no such thing. Please do not post tests that refer to non-existent entities. David
              Message 6 of 14 , Oct 12, 2013
              • 0 Attachment

                 Bernhard Helmes wrote:

                 

                > the pell solution of x, y with x^2-ay^2=-1

                 

                For a=3 mod 4 there is no such thing.

                 

                Please do not post "tests" that refer
                to non-existent entities.

                 

                David

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