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

Puzzle: Counterexample for a 1+1+2 Selfridge prime test

Expand Messages
  • bhelmes_1
    Dear David, i checked the following test with a list of Pseudoprimes
    Message 1 of 7 , Mar 9, 2014
      Dear David,

      i checked the following test with a list of Pseudoprimes < 10^16 and did not found a counterexample

      David, please, can you look for one counterexample, if there exists one.
       
      the test has an easy structure and has the following conditions :
       
      1. p should not be a square and  p=3 mod 4 and p=1 mod 6
      2. choose a with jac (a, p)=-1 and check a^[(p-1)/2]=-1 mod p
          if this test fails p is definitly not a prime, this is a p-1 test.
      3. try to find a 3. root of 1 by making a similar Rabbin-Miller test with exponent 3 instead of 2
         ( a^[(p-1)/3]=x mod p and x <>1)
         The chance to find a 3. root is 2/3, perhaps there is a more sophisticated way to calculate
         this.
         if  x=1 repeat step 2. and 3 . which can be combined so that the costs are only one selfridge
      4. Calculate in the complex field (x^2+x*i)^[(p+1)/2]=-1 or = 1 mod p resp.
                        (x^2+x*i)^[(p+1)/4]= a+bi mod p where a=0
         The norm of |x^2+x*i|=(x^2+x*i)(x^2-x*i) =
                                          x^4+x^2 =           with x^3=1
                                          x + x^2 = -1 mod p  with  x^2+x+1 = 0 mod p
        is -1 mod p
        This is a p+1 test with a reduction to a base with norm= -1, where p+1 is not divisible by 3
        and which cost 2 selfridges.

      Paul mentionned that this test would cost 1+1+2 Selfridges
      which is too much for a probablistic test as i know.

      This test should be a candidate for me to give a sufficient test
      and should be stronger than my test before
      because the norm of (x^2+x*i)=-1 instead of the test before with norm = 1

      Besides : all primes with p=3 mod 4 and p=1 mod 6 and < 10^9 passes the test,
      where the point 1., 2., 3. is easy to prove, but for the point 4.  i am looking for an explication.

      David, it would be nice from you, if you give me a gentle mathematic response,
      perhaps with some explication, why the test could fail.

      I wish you a peaceful evening and a good start in the week,
      primes are beautiful flowers in the universe and
      i appreciate really a fair mathematical discussion in order to learn a little bit more.

      Thanks in advance from the primes to the gremlins
      Bernhard
    • djbroadhurst
      ... Hence p = 7 mod 12. ... Hence x^2+x+1 = 0 mod p. ... False for primes! The result is +/- i mod p. My gremlins cannot solve badly stated problems. David
      Message 2 of 7 , Mar 9, 2014
        Bernhard Helmes wrote:

        > p=3 mod 4 and p=1 mod 6

        Hence p = 7 mod 12.

        > a^[(p-1)/2]= -1 mod p
        > a^[(p-1)/3] = x mod p and x <> 1

        Hence x^2+x+1 = 0 mod p.
         
        > (x^2+x*i)^[(p+1)/2] = -1 or = 1 mod p

        False for primes! The result is +/- i mod p.

        My gremlins cannot solve badly stated problems.

        David
      • djbroadhurst
        Proposed primality test: 1) p = 7 mod 12 is not a square, 2) kronecker(a,p) = - 1, 3) a^((p-1)/2) = -1 mod p, 4) gcd(x-1,p) = 1, where x = a^((p-1)/3), 5)
        Message 3 of 7 , Mar 10, 2014
          Proposed primality test:

          1) p = 7 mod 12 is not a square,
          2) kronecker(a,p) = - 1,
          3) a^((p-1)/2) = -1 mod p,
          4) gcd(x-1,p) = 1, where x = a^((p-1)/3),
          5) (x^2+i*x)^(p+1) = -1 mod p.

          It's quite easy to find pseudoprimes.

          {tst(p, a, x) =
          p%12 == 7 && !issquare(p) &&
          kronecker(a,p) == -1 &&
          Mod(a,p)^((p-1)/2) == -1 &&
          gcd(x-1,p) == 1 && Mod(a,p)^((p-1)/3) == x &&
          (Mod(x,p)*(x+I))^(p+1) == -1;}

          {if(tst(271*8161, 7260, 682620), print("Fooled"));}

          Fooled
           
          David
        • bhelmes_1
          Dear David, i thank you for your work and successful search for the counterexample. Does it make any difference if the test is limited to p = 3 mod 8 in
          Message 4 of 7 , Mar 12, 2014
            Dear David,

            i thank you for your work and successful search for the counterexample.
            Does it make any difference if the test is limited to p = 3 mod 8 in addition ?

            > Proposed primality test:

            > 1) p = 7 mod 12 is not a square,
            > 2) kronecker(a,p) = - 1,
            > 3) a^((p-1)/2) = -1 mod p,
            > 4) gcd(x-1,p) = 1, where x = a^((p-1)/3),
            5) (x^2+i*x)^[(p+1)/2] = i, -i mod p.
                                         
            The best greetings to the gremlins
            Bernhard
          • djbroadhurst
            Bernhard Helmes asked: . Does it make any difference if the test is limited to p = 3 mod 8 in addition ? No. Here is a counterexample with composite p = 19
            Message 5 of 7 , Mar 12, 2014

              Bernhard Helmes asked:

               

              .> Does it make any difference if the test is limited to p = 3 mod 8 in addition ?

              No. Here is a counterexample with composite p = 19 mod 24.

               

               

              {p=
              675961081605237787645326669827132867421964707102288445595128\
              306767364368922625365751637387079135941412241725625718182659\
              797220975595414553817336272156315877518713459900369575786759\
              069060577760998993405179409380771964650863026553544931148603\
              852397726534883765167569700179809784567165598901315490849439\
              643483131;}

              {a=
              143183781681819085621274459662205664353066281708044561938474\
              561078078825094915532720327449936152812575165723359597491154\
              987675822372398122684609431293757111072607893728179485857573\
              561016496252852435832824395580172292440970359198725505460012\
              729132839536797444771147293062929495356986071030574294827961\
              789589258;}

              {test(p,a)=local(m,x,r,t);
              if(p%24==19&&!issquare(p)&&kronecker(a,p)==-1,
              m=Mod(a,p)^((p-1)/6);x=m^2;
              if(m^3==-1&&gcd(lift(x)-1,p)==1,r=(x^2+I*x)^((p+1)/2);
              if(r==I||r==-I,t=1)));t;}

              {if(test(p,a)&&!isprime(p),
              print(" Fooled at "#Str(p)" digits"));}

               Fooled at 309 digits
               
              Challenge for Paul Underwood: how did I choose a ?
              Challenge for Kermit Rose: can you factorize p ?
              Clue for both: p = 1 mod 137.

              David (per proxy the 300 digit gremlins)

            • paulunderwooduk
              I can not say exactly how you chose a . In general terms, you used your usual trickery -- which I should have studied more than I did -- and CRT, which is
              Message 6 of 7 , Mar 12, 2014
                I can not say exactly how you chose "a". In general terms, you used your usual trickery -- which I should have studied more than I did -- and CRT, which is guaranteed to work with any such test that has at most one lucas component.

                However, I am still mindlessly testing my double lucas tests and the 2-selfridge test. The latter has reached 7*10^13 and 10^15 is in the pipeline,

                Paul
              • djbroadhurst
                ... In the past you were more shrewd and sought for an exponent k such that a^k-1 is not coprime to p. This should work again. However (if I did not err) you
                Message 7 of 7 , Mar 12, 2014
                  Paul Underwood wrote:

                  > I can not say exactly how you chose "a".

                  In the past you were more shrewd and sought for
                  an exponent k such that a^k-1  is not coprime to p.

                  This should work again. However (if I did not err)
                  you will not be able to use that result, directly, to factorize
                  the semiprime p, as was possible in many previous cases.

                  Factorization of p should be within the scope of Kermit,
                  whose has been training his code on previous semiprimes,
                  albeit at less than 300 digits.

                  > guaranteed to work with any such test that has at most one lucas component.

                  Yes, provided that there is a free parameter (in this case, a) to adjust.
                  I wish Bernhard would accept this and stop asking to be stomped
                  on by my gremlins, who by now regard him as a very soft target.

                  David (licensed gremlin tamer)


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