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

25402A sharper a-SPRP test ?

Expand Messages
  • bhelmes_1
    Oct 26, 2013
    • 0 Attachment
      A peaceful day for all members of the group and especially for David

      I refer to the page
      http://primes.utm.edu/prove/prove2_3.html

      Is think the following proposed test is better, results below:

      Let be p element N, odd and greater 5
      a element N, gcd (a,p)=1 and jacobi (a,p)=-1
      p-1=(2^d)*r with r>2 and d maximal
      (This test is not suitable for Mersenne numbers ;-)

      1. A pretest which is new with
      a^(2^(d-1)) <> p-1 mod p
      if this precondition fails, the test should be repeated by another a

      2. a^(2^[(d-1)*r)])=p-1 mod p (the normal Sprp test)

      1. and 2. reveal that a is a non quadratic residuum and that a primitiv root of t | r
      exist so that at least 2 factors n,m of p exist with t|n-1 and t|m-1
      A factorization of r is not needed and the test can be improved by using the Pocklington theorem so that an estimation of t can be made.

      The test is a little bit sharper than the SPRP-test.

      I know that it is only a little improvement and may be a logical consequence.
      If there are some results available, it may be friendly to give me some links or sources.
      Otherwise i will make some work to document this idea.
      If someone can give an accurate mathematical proof which should not be difficult
      i will be thankful for it.

      Friendly greetings from the primes
      Bernhard

      Especially for David in order to decrease the amount of some gremlins

      The following gremlins fool this test:
      a=2, p< 100000:

      • anz_prob_prime:=0;
        for p from 7 to 1000000 step 2 do
           a:=2;
           if numlib::jacobi (a, p)=-1 then
              k:=(p-1)/2;
              d:=1;
              while k mod 2 = 0 do
                 k:=k/2;
                 d:=d+1;
              end_while;
              res:=powermod (a, 2^(d-1), p); 
              if res<>p-1 then
                 res:=powermod (res, k, p);
                 if res=p-1 then
                    if isprime (p)=FALSE then
                      fac:=ifactor (p);
                      anz_prob_prime:=anz_prob_prime+1;
                      print (anz_prob_prime,"FALSE", p, "p-1=", ifactor (p-1), "p=",fac);
                      for i from 1 to (nops (fac)-1)/2 do
                        print (fac[2*i],"-1=", ifactor (fac[2*i]-1));
                      end_for;
                    end_if;
                 end_if;
              else
                 print ("Pretest Fails", p, d);
              end_if;
           end_if;
        end_for;
         
      
                                                2  2
                     1, "FALSE", 3277, "p-1=", 2  3  7 13, "p=", 29 113
      
                                                  2
                                      29, "-1=", 2  7
      
                                                   4
                                      113, "-1=", 2  7
      
                                               2  2
                   2, "FALSE", 29341, "p-1=", 2  3  5 163, "p=", 13 37 61
      
                                                  2
                                      13, "-1=", 2  3
      
                                                  2  2
                                      37, "-1=", 2  3
      
                                                 2
                                     61, "-1=", 2  3 5
      
                                               2  3
                   3, "FALSE", 49141, "p-1=", 2  3  5 7 13, "p=", 157 313
      
                                                 2
                                    157, "-1=", 2  3 13
      
                                                 3
                                    313, "-1=", 2  3 13
      
                                               2
                   4, "FALSE", 80581, "p-1=", 2  3 5 17 79, "p=", 61 1321
      
                                                 2
                                     61, "-1=", 2  3 5
      
                                                 3
                                   1321, "-1=", 2  3 5 11
      
                                               2
                   5, "FALSE", 88357, "p-1=", 2  3 37 199, "p=", 149 593
      
                                                  2
                                     149, "-1=", 2  37
      
                                                  4
                                     593, "-1=", 2  37
      
                                                2  4
                   6, "FALSE", 104653, "p-1=", 2  3  17 19, "p=", 229 457
      
                                                 2
                                    229, "-1=", 2  3 19
      
                                                 3
                                    457, "-1=", 2  3 19
      
                                               2  2
                  7, "FALSE", 196093, "p-1=", 2  3  13 419, "p=", 157 1249
      
                                                 2
                                    157, "-1=", 2  3 13
      
                                                  5
                                    1249, "-1=", 2  3 13
      
                                              2  3
                 8, "FALSE", 314821, "p-1=", 2  3  5 11 53, "p=", 13 61 397
      
                                                  2
                                      13, "-1=", 2  3
      
                                                 2
                                     61, "-1=", 2  3 5
      
                                                 2  2
                                    397, "-1=", 2  3  11
      
                                               2
                  9, "FALSE", 458989, "p-1=", 2  3 23 1663, "p=", 277 1657
      
                                                 2
                                    277, "-1=", 2  3 23
      
                                                 3  2
                                   1657, "-1=", 2  3  23
      
                10, "FALSE", 476971, "p-1=", 2 3 5 13 1223, "p=", 11 131 331
      
                                       11, "-1=", 2 5
      
                                     131, "-1=", 2 5 13
      
                                    331, "-1=", 2 3 5 11
      
                                               2  3
                 11, "FALSE", 489997, "p-1=", 2  3  13 349, "p=", 157 3121
      
                                                 2
                                    157, "-1=", 2  3 13
      
                                                 4
                                   3121, "-1=", 2  3 5 13
      
                                              2  4
                12, "FALSE", 800605, "p-1=", 2  3  7 353, "p=", 5 13 109 113
      
                                                   2
                                        5, "-1=", 2
      
                                                  2
                                      13, "-1=", 2  3
      
                                                  2  3
                                     109, "-1=", 2  3
      
                                                   4
                                      113, "-1=", 2  7
      
                                              2
                13, "FALSE", 838861, "p-1=", 2  3 5 11 31 41, "p=", 397 2113
      
                                                 2  2
                                    397, "-1=", 2  3  11
      
                                                  6
                                    2113, "-1=", 2  3 11
      
                                               2  4    2
                 14, "FALSE", 873181, "p-1=", 2  3  5 7  11, "p=", 661 1321
      
                                                2
                                   661, "-1=", 2  3 5 11
      
                                                 3
                                   1321, "-1=", 2  3 5 11
      
                  15, "FALSE", 877099, "p-1=", 2 3 17 8599, "p=", 307 2857
      
                                                   2
                                    307, "-1=", 2 3  17
      
                                                 3
                                   2857, "-1=", 2  3 7 17