src/numtheory/cl_IF.h

   1 // Integer factorization and primality testing.
   2
   3 #ifndef _CL_IF_H
   4 #define _CL_IF_H
   5
   6 #include "cln/number.h"
   7 #include "cln/integer.h"
   8
   9 namespace cln {
  10
  11 // Table of primes > 2, < 2^16
  12 const uint32 cl_small_prime_table_limit = 65536;
  13 const int cl_small_prime_table_size = 6541;
  14 extern uint16 cl_small_prime_table[cl_small_prime_table_size];
  15
  16 // Given 0 < d <= cl_small_prime_table_limit, return the smallest index i
  17 // such that  cl_small_prime_table[i] >= d.  (Or i = cl_small_prime_table_size
  18 // if none exists.)
  19 inline uintL cl_small_prime_table_search (uint32 d)
  20 {
  21         var uintL i1 = 0;
  22         var uintL i2 = cl_small_prime_table_size;
  23         if (cl_small_prime_table[i1] >= d)
  24                 return i1;
  25         loop {
  26                 // Here i1 < i2 and
  27                 // cl_small_prime_table[i1] < d <= cl_small_prime_table[i2].
  28                 var uintL i3 = floor(i1+i2,2);
  29                 if (i3 == i1) // (i2-i1 == 1) ?
  30                         return i2;
  31                 if (cl_small_prime_table[i3] >= d)
  32                         i2 = i3;
  33                 else
  34                         i1 = i3;
  35         }
  36 }
  37
  38 // Trial division.
  39 // Divides n > 0 by the primes in the range d1 <= d <= d2
  40 // (0 < d1 <= d2 <= min(isqrt(n),cl_small_prime_table_limit))
  41 // and returns the divisor d if found, or 0 if no divisor found.
  42 extern uint32 cl_trialdivision (uint32 n, uint32 d1, uint32 d2);
  43 extern uint32 cl_trialdivision (uint32 nhi, uint32 nlo, uint32 d1, uint32 d2);
  44 extern uint32 cl_trialdivision (const cl_I& n, uint32 d1, uint32 d2);
  45
  46 // Miller-Rabin compositeness test.
  47 // Performs count times the Miller-Rabin test on n > 1 odd.
  48 // Returns true if n looks like a prime (with error probability < 4^-count).
  49 // Returns false if n is definitely composite, and then sets factor = some
  50 // nontrivial factor or 0.
  51 extern cl_boolean cl_miller_rabin_test (const cl_I& n, int count, cl_I* factor);
  52
  53 }  // namespace cln
  54
  55 #endif /* _CL_IF_H */