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

Re: sufficient test for primes with certificate

Expand Messages
  • djbroadhurst
    ... Here are some [g, a, p] certificates that falsely declare composite p to be prime, using your 1-selfridge test: [1018080, 30271, 1048351] [74061, 13880,
    Message 1 of 33 , Jul 16, 2012
      --- In primenumbers@yahoogroups.com,
      "bhelmes_1" <bhelmes@...> wrote:

      > thanks a lot that you reveal a hole in the proof
      > and in the algorithm.
      >
      > You will surely remark that both counterexample are
      > of the form a=16 and a=121 and that they are squares.

      Here are some [g, a, p] "certificates" that
      falsely declare composite p to be prime,
      using your 1-selfridge test:

      [1018080, 30271, 1048351]
      [74061, 13880, 1060459]
      [218703, 77606, 1072567]
      [1023125, 73658, 1096783]
      [135574, 98605, 1052651]
      [1009768, 51051, 1060819]
      [160165, 1722, 1073071]
      [844366, 240957, 1085323]
      [1046524, 63303, 1109827]
      [449585, 90843, 1113911]
      [280945, 175930, 1093891]
      [1015244, 58043, 1073287]
      [903680, 182003, 1085683]
      [823106, 274973, 1098079]
      [1069351, 53520, 1122871]
      [890564, 220127, 1110691]
      [1030548, 105079, 1135627]
      [175930, 31150, 1115111]
      [993015, 130504, 1123519]
      [336493, 1244, 1148743]
      [14473, 34607, 1157551]
      [1075413, 60934, 1136347]
      [922341, 239518, 1161859]
      [666074, 495929, 1162003]
      [1064431, 123660, 1188091]

      In each case:
      p = 3 mod 4,
      kronecker(a,p) = 1,
      the "witness" a is /not/ a square in Z,
      a^((p-1)/2) = 1 mod p
      g^2*a = 1 mod p
      and p is /not/ prime.

      {cert(g,a,p) =
      p%4 == 3 &&
      kronecker(a,p) ==1 &&
      !issquare(a) &&
      Mod(a,p)^((p-1)/2) == 1 &&
      Mod(g,p)^2*a == 1 &&
      !isprime(p);}

      v=readvec("helmes1.out");f=0;
      for(k=1,#v,u=v[k];f+=cert(u[1],u[2],u[3]));
      print(f" counterexamples in "#v" attempts");

      25 counterexamples in 25 attempts

      Each of these 25 counterexamples destroys your
      1-selfridge claim, even with your latest "wriggle"
      that the "witness" a must not be a square in Z.

      David
    • paulunderwooduk
      ... I compiled a better version of my code with gmp 5.0.5, on a different box running at 3.6GHz and got some better timings { 17.505s pfgw (3-prp) 1m1.986s
      Message 33 of 33 , Sep 21, 2012
        --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:
        :
        > http://tech.groups.yahoo.com/group/primenumbers/files/Articles/

        > I ran various "minimal \lambda+2" tests on Gilbert Mozzo's 20,000 digit PRP, 5890*10^19996+2^66422-3 (x=1), using a 2.4GHz core:
        > {
        > 0m32.374s pfgw64 (3-prp)
        > 1m9.876s pfgw64 -t
        > 1m53.535s pfgw64 -tp
        > 3m0.483s pfgw64 -tc
        > 5m12.972s pfgw64 scriptify
        > 4m4.811s gmp (-O3/no pgo)
        > 4m9.148 pari-gp
        > 1m15s theoretical Woltman implementation
        > }
        >

        I compiled a better version of my code with gmp 5.0.5, on a different box running at 3.6GHz and got some better timings
        {
        17.505s pfgw (3-prp)
        1m1.986s pfgw -tp
        1m13.789s gmp (-O3/no pgo)
        }

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