1 // Number theoretic operations.
3 #ifndef _CL_NUMTHEORY_H
4 #define _CL_NUMTHEORY_H
7 #include "cl_integer.h"
8 #include "cl_modinteger.h"
9 #include "cl_condition.h"
11 // jacobi(a,b) returns the Jacobi symbol
15 // a, b must be integers, b > 0, b odd. The result is 0 iff gcd(a,b) > 1.
16 extern int jacobi (sint32 a, sint32 b);
17 extern int jacobi (const cl_I& a, const cl_I& b);
19 // isprobprime(n), n integer > 0,
20 // returns true when n is probably prime.
21 // This is pretty quick, but no caching is done.
22 extern cl_boolean isprobprime (const cl_I& n);
24 // nextprobprime(x) returns the smallest probable prime >= x.
25 extern const cl_I nextprobprime (const cl_R& x);
28 // primitive_root(R) of R = Z/pZ, with p a probable prime,
30 // either a generator of (Z/pZ)^*, assuming p is prime, or
31 // a proof that p is not prime, maybe even a non-trivial factor of p.
32 struct primitive_root_t {
33 cl_composite_condition* condition;
36 primitive_root_t (cl_composite_condition* c) : condition (c) {}
37 primitive_root_t (const cl_MI& g) : condition (NULL), gen (g) {}
39 extern const primitive_root_t primitive_root (const cl_modint_ring& R);
42 // sqrt_mod_p(R,x) where x is an element of R = Z/pZ, with p a probable prime,
44 // either the square roots of x in R, assuming p is prime, or
45 // a proof that p is not prime, maybe even a non-trivial factor of p.
47 cl_composite_condition* condition;
49 int solutions; // 0,1,2
50 cl_I factor; // zero or non-trivial factor of p
51 cl_MI solution[2]; // max. 2 solutions
54 sqrt_mod_p_t (cl_composite_condition* c) : condition (c) {}
55 sqrt_mod_p_t (int s) : condition (NULL), solutions (s) {}
56 sqrt_mod_p_t (int s, const cl_MI& x0) : condition (NULL), solutions (s)
58 sqrt_mod_p_t (int s, const cl_MI& x0, const cl_MI& x1) : condition (NULL), solutions (s)
59 { solution[0] = x0; solution[1] = x1; }
61 extern const sqrt_mod_p_t sqrt_mod_p (const cl_modint_ring& R, const cl_MI& x);
63 // cornacchia1(d,p) solves x^2 + d*y^2 = p.
64 // cornacchia4(d,p) solves x^2 + d*y^2 = 4*p.
65 // d is an integer > 0, p is a probable prime.
67 // either a nonnegative solution (x,y), if it exists, assuming p is prime, or
68 // a proof that p is not prime, maybe even a non-trivial factor of p.
70 cl_composite_condition* condition;
73 // If solutions=1 and d > 4 (d > 64 for cornacchia4):
74 // All solutions are (x,y), (-x,y), (x,-y), (-x,-y).
75 cl_I solution_x; // x >= 0
76 cl_I solution_y; // y >= 0
79 cornacchia_t (cl_composite_condition* c) : condition (c) {}
80 cornacchia_t (int s) : condition (NULL), solutions (s) {}
81 cornacchia_t (int s, const cl_I& x, const cl_I& y) : condition (NULL), solutions (s), solution_x (x), solution_y (y) {}
83 extern const cornacchia_t cornacchia1 (const cl_I& d, const cl_I& p);
84 extern const cornacchia_t cornacchia4 (const cl_I& d, const cl_I& p);
86 #endif /* _CL_NUMTHEORY_H */