]> www.ginac.de Git - cln.git/blob - src/numtheory/cl_IF.h
* m4/param.m4: Add support for MinGW.
[cln.git] / 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 */