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

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

Expand Messages
  • bhelmes_1
    A beautiful day for all group members and especially for David I propose the following unproven prime test, which needs 1+3 Selfridges. Let p be an odd element
    Message 1 of 14 , Sep 7, 2013
    • 0 Attachment
      A beautiful day for all group members and especially for David

      I propose the following unproven prime test, which needs 1+3 Selfridges.

      Let p be an odd element of N and no square number,
      m the greatest power of 2 with 2^m*r=p+1
      and 2^m < r (otherwise there exist already the proth test)
       
      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
          http://mathworld.wolfram.com/PellEquation.html
      4. Calculate and verify (x+yA)^p=x-yA mod p with A=sqrt (a)
         This can be done with a fast exponentation modulo p.
      5. 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 checked all Spsp < 10^16 and found no counterexample.

      I did not verify 5., this point could be interesting for a proof
      and may be redundant.
      I suppose that 5. shows that there are r differents solutions where y(n)<>0 of
      x(n)^2-ay(n)^2=1 mod p with n=1 up to n=r
       
      Perhaps someone is pleased by
      http://devalco.de  I. Primes 4. cycle structur of primes e)
      for a graphic description

      Is there one counterexample ?
      Has anybody a suggestion for a mathematical proof ?

      Nice greetings from the primes
      Bernhard
    • djbroadhurst
      ... We already have an industrial-grade test from BPSW, of the type: Miller-Rabin + first strong witness for Lucas . BPSW costs 1+2 selfridges and has been
      Message 2 of 14 , Sep 8, 2013
      • 0 Attachment
        <bhelmes@..> wrote:

        > I propose the following unproven prime test,
        > which needs 1+3 Selfridges.
        ....
        > 1. choose the smallest prime a with jacobi (a, p)=-1

        We already have an industrial-grade test from BPSW,
        of the type: "Miller-Rabin + first strong witness for Lucas".
        BPSW costs 1+2 selfridges and has been efficiently implemented
        Why bother to propose another test of the same sort, costing more?

        > Is there one counterexample ?

        Same answer as for BPSW: no.

        > Has anybody a suggestion for a mathematical proof ?

        Same answer as for BPSW: no.

        As remarked in
        http://en.wikipedia.org/wiki/Occam's_razor
        phrases such as
        "It is vain to do with more what can be done with fewer"
        and
        "A plurality is not to be posited without necessity"
        were commonplace in 13th-century scholastic writing.

        David
      • djbroadhurst
        ... No prime p = 1 mod 4 passes this test . David
        Message 3 of 14 , Sep 10, 2013
        • 0 Attachment
          <bhelmes@> wrote:

          > I propose the following unproven prime test

          No prime p = 1 mod 4 passes this "test".

          David
        • djbroadhurst
          ... As remarked, no prime p = 1 mod 4 passes the test. Here I show that the composite number p = 2953*5167 = 15258151 = 7 mod 16 passes the test, using its
          Message 4 of 14 , Sep 11, 2013
          • 0 Attachment
            <bhelmes@> wrote:

            > I propose the following unproven prime test

            As remarked, no prime p = 1 mod 4 passes the test.
            Here I show that the composite number
            p = 2953*5167 = 15258151 = 7 mod 16
            passes the test, using its minimal strong base, a = 3:

            {p=15258151;x=13785839;y=8920588;xr=1472312;yr=6337563;
            if(Mod(p,16)==7&&kronecker(2,p)==1&&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&&
            Mod(Mod(1,p)*(x+y*A),A^2-3)^((p+1)/8)==xr+yr*A&&
            gcd(p,yr)==1&&!isprime(p),print(" fooled with minimal base"));}

            fooled with minimal base

            The gremlins will entertain no further wriggle from Bernhard.

            David (their keeper)
          • bhelmes_1
            ... As remarked, no prime p = 1 mod 4 passes the test. Here I show that the composite number p = 2953*5167 = 15258151 = 7 mod 16 passes the test, using its
            Message 5 of 14 , Sep 13, 2013
            • 0 Attachment

               Dear David,


              thank you for your efforts to find a counterexample.

              I noticed that you did not used a solution of pell for a=3 with x^2-ay^2=1

              but the solution for x^2-ay^2=1 mod p

              I am not sure wether this makes a difference for the test.


              I wish you a pleasant and peaceful weekend

              Bernhard



              --- In primenumbers@yahoogroups.com, <david.broadhurst@...> wrote:

              <bhelmes@> wrote:

              > I propose the following unproven prime test

              As remarked, no prime p = 1 mod 4 passes the test.
              Here I show that the composite number
              p = 2953*5167 = 15258151 = 7 mod 16
              passes the test, using its minimal strong base, a = 3:

              {p=15258151;x=13785839;y=8920588;xr=1472312;yr=6337563;
              if(Mod(p,16)==7&&kronecker(2,p)==1&&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&&
              Mod(Mod(1,p)*(x+y*A),A^2-3)^((p+1)/8)==xr+yr*A&&
              gcd(p,yr)==1&&!isprime(p),print(" fooled with minimal base"));}

              fooled with minimal base

              The gremlins will entertain no further wriggle from Bernhard.

              David (their keeper)
            • djbroadhurst
              ... There is an infinity of solutions to x^2-3*y^2 = 1, with integers x and y. Here are a few: q=quadunit(12);r=1;for(k=1,20,r*=q;print([k,real(r),imag(r)]));
              Message 6 of 14 , Sep 13, 2013
              • 0 Attachment
                Bernhard Helmes wrote:

                > you did not used a solution of pell for a=3 with x^2-ay^2=1

                There is an infinity of solutions to x^2-3*y^2 = 1,
                with integers x and y.

                Here are a few:

                q=quadunit(12);r=1;for(k=1,20,r*=q;print([k,real(r),imag(r)]));

                [1, 2, 1]
                [2, 7, 4]
                [3, 26, 15]
                [4, 97, 56]
                [5, 362, 209]
                [6, 1351, 780]
                [7, 5042, 2911]
                [8, 18817, 10864]
                [9, 70226, 40545]
                [10, 262087, 151316]
                [11, 978122, 564719]
                [12, 3650401, 2107560]
                [13, 13623482, 7865521]
                [14, 50843527, 29354524]
                [15, 189750626, 109552575]
                [16, 708158977, 408855776]
                [17, 2642885282, 1525870529]
                [18, 9863382151, 5694626340]
                [19, 36810643322, 21252634831]
                [20, 137379191137, 79315912984]


                How do you intend to prove that one pair of Pell's /infinite/
                series does not correspond to my choice, modulo p?

                That might take you some time :-?

                David
              • djbroadhurst
                ... But it will not take for ever. It would be sufficient for Bernhard to study less than 960,000 integers from http://oeis.org/A001075 ... Of these, the
                Message 7 of 14 , Sep 13, 2013
                • 0 Attachment
                  --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote:

                  > How do you intend to prove that one pair of Pell's /infinite/
                  > series does not correspond to my choice, modulo p?
                  >
                  > That might take you some time :-?

                  But it will not take for ever. It would be sufficient for
                  Bernhard to study less than 960,000 integers from
                  http://oeis.org/A001075
                  > a(n) solves for x in x^2 - 3*y^2 = 1

                  Of these, the largest has less than 550,000 digits:

                  {stop=ceil(15258151/16);digs=#Str(real(quadunit(12)^stop));
                  print(stop"th Pell number has "digs" decimal digits");}

                  953635th Pell number has 545429 decimal digits

                  Happy hunting :-)

                  David
                • bhelmes_1
                  Dear David, As remarked, no prime p = 1 mod 4 passes the test. I would like to add that only the point 5. causes the trouble. and that all primes passes the
                  Message 8 of 14 , Sep 14, 2013
                  • 0 Attachment
                    Dear David,

                    >As remarked, no prime p = 1 mod 4 passes the test.

                    I would like to add that only the point 5. causes the trouble.
                    and that all primes passes the points 1. - 4.

                    >Here I show that the composite number
                    >p = 2953*5167 = 15258151 = 7 mod 16
                    >passes the test, using its minimal strong base, a = 3:

                    I feel that it was not easy for you and a lot of work for you to find one counterexample.
                    Besides i noticed that your selected x and y is kind of  (x+yA)^4=-1 mod p
                    which is very special and shows that the proposed test is not sufficient.

                    >The gremlins will entertain no further wriggle from Bernhard.

                    David, i have a huge respect for your mathematical skills,
                    nevertheless the description to entertain me is not what i expect from you.
                    This primenumber group is the only place for me to discuss some mathematical
                    ideas and to get some mathematical feedback.

                    As far as i can see a proven sufficient primetest with 4 Selfridge would be a mathematical progress
                    and the development of choosing the right parameters in order to build a proof is not a kind of "wriggle" but
                    mathematical work.

                    I appreciate deeply a fair mathematical discussion.

                    David, prime numbers are something for the eternity and there is no reason to get angry about some humble
                    mathematicians like me who try to learn some more details of number theory.

                    I wish you a pleasant and friendly weekend.
                    Bernhard



                    David (their keeper)
                  • 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 9 of 14 , Sep 14, 2013
                    • 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 10 of 14 , Sep 20, 2013
                      • 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 11 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 12 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 13 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 14 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.