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