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

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

Expand Messages
  • 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 1 of 14 , Sep 21, 2013
    • 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 2 of 14 , Sep 21, 2013
      • 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 3 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 4 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.