1 #include "cado.h" // IWYU pragma: keep
2
3 #include <inttypes.h> // for PRId64, PRIu64 // IWYU pragma: keep
4 #include <array> // for array, array<>::value_type
5 #include <cstdint> // for uint8_t
6 #include <mutex> // for lock_guard, mutex
7 #include <vector> // for vector
8
9 #include <gmp.h> // for mpz_srcptr, gmp_fprintf, mpz_c...
10
11 #include "las-cofac-standalone.hpp" // for cofac_standalone
12 #include "gcd.h" // for bin_gcd_int64_safe // IWYU pragma: keep
13 #include "ecm/batch.hpp" // for cofac_list
14 #include "las-cofactor.hpp" // for factor_both_leftover_norms
15 #include "las-coordinates.hpp" // for NxToAB
16 #include "las-divide-primes.hpp" // for factor_list_t
17 #include "las-siever-config.hpp" // for siever_config::side_config
18 #include "las-threads-work-data.hpp" // for nfs_work_cofac
19 #include "las-todo-entry.hpp" // for las_todo_entry
20 #include "las-where-am-i-proxy.hpp" // for extern_trace_on_spot_ab
21 #include "lock_guarded_container.hpp" // for lock_guarded_container
22 #include "relation.hpp" // for relation
23
24 struct qlattice_basis; // IWYU pragma: keep
25
26 /* This is one input to the late cofactoring process (aka ECM). Here, we
27 * mean the stuff that is done detached from the rest of the siever
28 * stuff: we no longer care about purging buckets and so on, these may
29 * safely be used for later work.
30 */
cofac_standalone()31 cofac_standalone::cofac_standalone() : a(0), b(0) {/*{{{*/
32 S[0] = S[1] = 0;
33 #ifdef SUPPORT_LARGE_Q
34 mpz_set_ui(az, 0);
35 mpz_set_ui(bz, 0);
36 #endif
37 }/*}}}*/
cofac_standalone(int N,size_t x,int logI,qlattice_basis const & Q)38 cofac_standalone::cofac_standalone(int N, size_t x, int logI, qlattice_basis const & Q) {/*{{{*/
39 S[0] = S[1] = 0;
40 NxToAB (a, b, N, x, logI, Q);
41 #ifdef SUPPORT_LARGE_Q
42 NxToABmpz (az, bz, N, x, logI, Q);
43 #endif
44 }/*}}}*/
trace_on_spot() const45 bool cofac_standalone::trace_on_spot() const {/*{{{*/
46 return extern_trace_on_spot_ab(a, b);
47 }/*}}}*/
gcd_coprime_with_q(las_todo_entry const & E)48 bool cofac_standalone::gcd_coprime_with_q(las_todo_entry const & E) {/*{{{*/
49 /* Since the q-lattice is exactly those (a, b) with
50 a == rho*b (mod q), q|b ==> q|a ==> q | gcd(a,b) */
51 /* In case of composite sq, have to check all factors... */
52 /* FIXME: fast divisibility test here! */
53 if (E.is_prime()) {
54 #ifndef SUPPORT_LARGE_Q
55 if (b == 0 || (mpz_cmp_ui(E.p, b) <= 0 && b % mpz_get_ui(E.p) == 0))
56 #else
57 if ((mpz_cmp_ui(bz, 0) == 0) ||
58 (mpz_cmp(E.p, bz) <= 0 &&
59 mpz_divisible_p(bz, E.p)))
60 #endif
61 return false;
62 } else {
63 #ifdef SUPPORT_LARGE_Q
64 if (mpz_cmp_ui(bz, 0) == 0)
65 return false;
66 for (auto const& facq : E.prime_factors) {
67 if ((mpz_cmp_ui(bz, facq) >= 0) && (mpz_divisible_ui_p(bz, facq))) {
68 return false;
69 }
70 }
71 #else
72 if (b == 0)
73 return false;
74 for (auto const& facq : E.prime_factors) {
75 if (facq <= b && b % facq == 0) {
76 return false;
77 }
78 }
79 #endif
80 }
81 return true;
82 }/*}}}*/
ab_coprime() const83 bool cofac_standalone::ab_coprime() const {/*{{{*/
84 #ifndef SUPPORT_LARGE_Q
85 return bin_gcd_int64_safe(a,b) == 1;
86 #else
87 cxx_mpz g;
88 mpz_gcd(g, az, bz);
89 return mpz_cmp_ui(g, 1) == 0;
90 #endif
91 }/*}}}*/
print_as_survivor(FILE * f)92 void cofac_standalone::print_as_survivor(FILE * f) {/*{{{*/
93 #ifndef SUPPORT_LARGE_Q
94 gmp_fprintf(f, "%" PRId64 " %" PRIu64 " %Zd %Zd\n", a, b,
95 (mpz_srcptr) norm[0],
96 (mpz_srcptr) norm[1]);
97 #else
98 gmp_fprintf(f, "%Zd %Zd %Zd %Zd\n",
99 (mpz_srcptr) az,
100 (mpz_srcptr) bz,
101 (mpz_srcptr) norm[0],
102 (mpz_srcptr) norm[1]);
103 #endif
104 }/*}}}*/
get_relation(las_todo_entry const & doing)105 relation cofac_standalone::get_relation(las_todo_entry const & doing) {/*{{{*/
106 #ifndef SUPPORT_LARGE_Q
107 relation rel(a, b);
108 #else
109 relation rel(az, bz);
110 #endif
111
112 /* Note that we explicitly do not bother about storing r in
113 * the relations below */
114 for (int side = 0; side < 2; side++) {
115 for (auto const& z : factors[side])
116 rel.add(side, z, 0);
117 for (auto const& z : lps[side])
118 rel.add(side, z, 0);
119 }
120 if (doing.is_prime()) {
121 rel.add(doing.side, doing.p, 0);
122 } else {
123 for (auto const& facq : doing.prime_factors)
124 rel.add(doing.side, facq, 0);
125 }
126
127 rel.compress();
128 return rel;
129 }/*}}}*/
transfer_to_cofac_list(lock_guarded_container<cofac_list> & L,las_todo_entry const & doing)130 void cofac_standalone::transfer_to_cofac_list(lock_guarded_container<cofac_list> & L, las_todo_entry const & doing) {/*{{{*/
131 std::lock_guard<std::mutex> foo(L.mutex());
132 /* "doing" must be an object that lives in the main todo list,
133 * and will stay alive until the end of the program. Yes, it's a
134 * bit dangerous. */
135 L.emplace_back(a, b, norm, &doing);
136 #if 0
137 /* make sure threads don't write the cofactor list at the
138 * same time !!! */
139 #warning "possible contention"
140 static pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
141 pthread_mutex_lock(&lock);
142 cofac_list_add (L, a, b, norm, doing.side, doing.p);
143 pthread_mutex_unlock(&lock);
144 #endif
145 }/*}}}*/
factor_both_leftover_norms(nfs_work_cofac & wc)146 int cofac_standalone::factor_both_leftover_norms(nfs_work_cofac & wc) {/*{{{*/
147 /* This proxies to las-cofactor.cpp */
148 return ::factor_both_leftover_norms(norm,
149 lps,
150 {{ wc.sc.sides[0].lim, wc.sc.sides[1].lim }},
151 wc.strategies);
152 }/*}}}*/
153
154