include/cln/numtheory.h

0001 // Number theoretic operations.
0002
0003 #ifndef _CL_NUMTHEORY_H
0004 #define _CL_NUMTHEORY_H
0005
0006 #include "cln/number.h"
0007 #include "cln/integer.h"
0008 #include "cln/modinteger.h"
0009 #include "cln/condition.h"
0010
0011 namespace cln {
0012
0013 // jacobi(a,b) returns the Jacobi symbol
0014 //                       (  a  )
0015 //                       ( --- )
0016 //                       (  b  )
0017 // a, b must be integers, b > 0, b odd. The result is 0 iff gcd(a,b) > 1.
0018   extern int jacobi (sintV a, sintV b);
0019   extern int jacobi (const cl_I& a, const cl_I& b);
0020
0021 // isprobprime(n), n integer > 0,
0022 // returns true when n is probably prime.
0023 // This is pretty quick, but no caching is done.
0024   extern bool isprobprime (const cl_I& n);
0025
0026 // nextprobprime(x) returns the smallest probable prime >= x.
0027   extern const cl_I nextprobprime (const cl_R& x);
0028
0029 #if 0
0030 // primitive_root(R) of R = Z/pZ, with p a probable prime,
0031 // returns
0032 //   either a generator of (Z/pZ)^*, assuming p is prime, or
0033 //   a proof that p is not prime, maybe even a non-trivial factor of p.
0034 struct primitive_root_t {
0035     cl_composite_condition* condition;
0036     cl_MI gen;
0037     // Constructors.
0038     primitive_root_t (cl_composite_condition* c) : condition (c) {}
0039     primitive_root_t (const cl_MI& g) : condition (NULL), gen (g) {}
0040 };
0041 extern const primitive_root_t primitive_root (const cl_modint_ring& R);
0042 #endif
0043
0044 // sqrt_mod_p(R,x) where x is an element of R = Z/pZ, with p a probable prime,
0045 // returns
0046 //   either the square roots of x in R, assuming p is prime, or
0047 //   a proof that p is not prime, maybe even a non-trivial factor of p.
0048 struct sqrt_mod_p_t {
0049     cl_composite_condition* condition;
0050     // If no condition:
0051     int solutions; // 0,1,2
0052     cl_I factor; // zero or non-trivial factor of p
0053     cl_MI solution[2]; // max. 2 solutions
0054     // Constructors.
0055     sqrt_mod_p_t () {}
0056     sqrt_mod_p_t (cl_composite_condition* c) : condition (c) {}
0057     sqrt_mod_p_t (int s) : condition (NULL), solutions (s) {}
0058     sqrt_mod_p_t (int s, const cl_MI& x0) : condition (NULL), solutions (s)
0059         { solution[0] = x0; }
0060     sqrt_mod_p_t (int s, const cl_MI& x0, const cl_MI& x1) : condition (NULL), solutions (s)
0061         { solution[0] = x0; solution[1] = x1; }
0062 };
0063 extern const sqrt_mod_p_t sqrt_mod_p (const cl_modint_ring& R, const cl_MI& x);
0064
0065 // cornacchia1(d,p) solves x^2 + d*y^2 = p.
0066 // cornacchia4(d,p) solves x^2 + d*y^2 = 4*p.
0067 // d is an integer > 0, p is a probable prime.
0068 // It returns
0069 //   either a nonnegative solution (x,y), if it exists, assuming p is prime, or
0070 //   a proof that p is not prime, maybe even a non-trivial factor of p.
0071 struct cornacchia_t {
0072     cl_composite_condition* condition;
0073     // If no condition:
0074     int solutions; // 0,1
0075     // If solutions=1 and d > 4 (d > 64 for cornacchia4):
0076     // All solutions are (x,y), (-x,y), (x,-y), (-x,-y).
0077     cl_I solution_x; // x >= 0
0078     cl_I solution_y; // y >= 0
0079     // Constructors.
0080     cornacchia_t () {}
0081     cornacchia_t (cl_composite_condition* c) : condition (c) {}
0082     cornacchia_t (int s) : condition (NULL), solutions (s) {}
0083     cornacchia_t (int s, const cl_I& x, const cl_I& y) : condition (NULL), solutions (s), solution_x (x), solution_y (y) {}
0084 };
0085 extern const cornacchia_t cornacchia1 (const cl_I& d, const cl_I& p);
0086 extern const cornacchia_t cornacchia4 (const cl_I& d, const cl_I& p);
0087
0088 }  // namespace cln
0089
0090 #endif /* _CL_NUMTHEORY_H */