include/cln/numtheory.h

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