1 // Integer factorization and primality testing.
7 #include "cl_integer.h"
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];
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
17 inline uintL cl_small_prime_table_search (uint32 d)
20 var uintL i2 = cl_small_prime_table_size;
21 if (cl_small_prime_table[i1] >= d)
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) ?
29 if (cl_small_prime_table[i3] >= d)
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);
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);