2 #include "chinrem_gcd.h"
3 #include <cln/integer.h>
5 #include "collect_vargs.h"
6 #include "primes_factory.h"
7 #include "divide_in_z_p.h"
13 static cln::cl_I extract_integer_content(ex& Apr, const ex& A)
15 static const cln::cl_I n1(1);
16 const numeric icont_ = A.integer_content();
17 const cln::cl_I icont = cln::the<cln::cl_I>(icont_.to_cl_N());
19 Apr = (A/icont_).expand();
27 ex chinrem_gcd(const ex& A_, const ex& B_, const exvector& vars)
30 const cln::cl_I a_icont = extract_integer_content(A, A_);
31 const cln::cl_I b_icont = extract_integer_content(B, B_);
32 const cln::cl_I c = cln::gcd(a_icont, b_icont);
34 const cln::cl_I a_lc = integer_lcoeff(A, vars);
35 const cln::cl_I b_lc = integer_lcoeff(B, vars);
36 const cln::cl_I g_lc = cln::gcd(a_lc, b_lc);
38 const ex& x(vars.back());
39 int n = std::min(A.degree(x), B.degree(x));
40 const cln::cl_I A_max_coeff = to_cl_I(A.max_coefficient());
41 const cln::cl_I B_max_coeff = to_cl_I(B.max_coefficient());
42 const cln::cl_I lcoeff_limit = (cln::cl_I(1) << n)*cln::abs(g_lc)*
43 std::min(A_max_coeff, B_max_coeff);
49 primes_factory pfactory;
51 bool has_primes = pfactory(p, g_lc);
53 throw chinrem_gcd_failed();
55 const numeric pnum(p);
58 ex Cp = pgcd(Ap, Bp, vars, p);
60 const cln::cl_I g_lcp = smod(g_lc, p);
61 const cln::cl_I Cp_lc = integer_lcoeff(Cp, vars);
62 const cln::cl_I nlc = smod(recip(Cp_lc, p)*g_lcp, p);
63 Cp = (Cp*numeric(nlc)).expand().smod(pnum);
64 int cp_deg = Cp.degree(x);
73 ex H_next = chinese_remainder(H, q, Cp, p);
76 } else if (cp_deg < n) {
77 // all previous homomorphisms are unlucky
82 // dp_deg > d_deg: current prime is bad
86 continue; // don't bother to do division checks
88 extract_integer_content(C, H);
89 if (divide_in_z_p(A, C, dummy1, vars, 0) &&
90 divide_in_z_p(B, C, dummy2, vars, 0))
91 return (numeric(c)*C).expand();
92 // else: try more primes