src/numtheory/cl_nt_isprobprime.cc

   1 // isprobprime().
   2
   3 // General includes.
   4 #include "cl_sysdep.h"
   5
   6 // Specification.
   7 #include "cln/numtheory.h"
   8
   9
  10 // Implementation.
  11
  12 #include "cl_IF.h"
  13 #include "cln/abort.h"
  14
  15 namespace cln {
  16
  17 cl_boolean isprobprime (const cl_I& n)
  18 {
  19         if (!(n > 0))
  20                 cl_abort();
  21         // With a Miller-Rabin count = 50 the final error probability is
  22         // 4^-50 < 10^-30.
  23         var int count = 50;
  24         // Step 1: Trial division (rules out 87% of all numbers quickly).
  25         const uint32 trialdivide_limit = 70;
  26         var uintL l = integer_length(n);
  27         if (l <= 32) {
  28                 var uint32 nn = cl_I_to_UL(n);
  29                 if (nn <= cl_small_prime_table_limit) {
  30                         // Table lookup.
  31                         var uintL i = cl_small_prime_table_search(nn);
  32                         if (i < cl_small_prime_table_size
  33                             && ((unsigned int) cl_small_prime_table[i] == nn
  34                                 || nn == 2))
  35                                 return cl_true;
  36                         else
  37                                 return cl_false;
  38                 }
  39                 if ((nn % 2) == 0 || cl_trialdivision(nn,1,trialdivide_limit))
  40                         return cl_false;
  41                 // For small n, only few Miller-Rabin tests are needed.
  42                 if (nn < 2000U) count = 1; // {2}
  43                 else if (nn < 1300000U) count = 2; // {2,3}
  44                 else if (nn < 25000000U) count = 3; // {2,3,5}
  45                 else if (nn < 3200000000U) count = 4; // {2,3,5,7}
  46         } else if (l <= 64) {
  47                 var uint32 nhi = cl_I_to_UL(ldb(n,cl_byte(32,32)));
  48                 var uint32 nlo = cl_I_to_UL(ldb(n,cl_byte(32,0)));
  49                 if ((nlo % 2) == 0 || cl_trialdivision(nhi,nlo,1,trialdivide_limit))
  50                         return cl_false;
  51         } else {
  52                 if (evenp(n) || cl_trialdivision(n,1,trialdivide_limit))
  53                         return cl_false;
  54         }
  55         // Step 2: Miller-Rabin test.
  56         return cl_miller_rabin_test(n,count,NULL);
  57 }
  58
  59 }  // namespace cln