1 // -*- C++ -*-
2 //==============================================================================================
3 //
4 // This file is part of LiDIA --- a library for computational number theory
5 //
6 // Copyright (c) 1994--2001 the LiDIA Group. All rights reserved.
7 //
8 // See http://www.informatik.tu-darmstadt.de/TI/LiDIA/
9 //
10 //----------------------------------------------------------------------------------------------
11 //
12 // $Id$
13 //
14 // Author :
15 // Changes : See CVS log
16 //
17 //==============================================================================================
18
19
20 #ifndef LIDIA_RATIONAL_FACTORIZATION_H_GUARD_
21 #define LIDIA_RATIONAL_FACTORIZATION_H_GUARD_
22
23
24
25 #ifndef LIDIA_COMPARATOR_H_GUARD_
26 # include "LiDIA/comparator.h"
27 #endif
28 #ifndef LIDIA_SORT_VECTOR_H_GUARD_
29 # include "LiDIA/sort_vector.h"
30 #endif
31 #ifndef LIDIA_BIGMOD_H_GUARD_
32 # include "LiDIA/bigmod.h"
33 #endif
34 #ifndef LIDIA_BIGRATIONAL_H_GUARD_
35 # include "LiDIA/bigrational.h"
36 #endif
37 #ifndef LIDIA_ECM_PRIMES_H_GUARD_
38 # include "LiDIA/base/ecm_primes.h"
39 #endif
40
41
42
43 #ifdef LIDIA_NAMESPACE
44 namespace LiDIA {
45 # define IN_NAMESPACE_LIDIA
46 #endif
47
48
49
50 class ecm_primes;
51 class rational_factorization;
52
53 class rf_single_factor
54 {
55 friend class rational_factorization;
56 friend std::istream & operator >> (std::istream &, rational_factorization &);
57
58 private:
59 bigint single_base;
60 unsigned int factor_state;
61 int single_exponent;
62
state(unsigned int x)63 static unsigned int state(unsigned int x)
64 {
65 return (x & 3);
66 }
67
68 public:
rf_single_factor()69 rf_single_factor() {};
~rf_single_factor()70 ~rf_single_factor() {};
71 rf_single_factor & operator = (const rf_single_factor &);
72
73 friend void swap(rf_single_factor & a, rf_single_factor & b);
74
75 static const unsigned int dont_know;
76 static const unsigned int prime;
77 static const unsigned int not_prime;
78
79 private:
80
81 friend bool operator < (const rf_single_factor & a, const rf_single_factor & b);
82 friend bool operator <= (const rf_single_factor & a, const rf_single_factor & b);
83 friend bool operator == (const rf_single_factor & a, const rf_single_factor & b);
84
85 friend std::istream & operator >> (std::istream &, rf_single_factor &);
86 friend std::ostream & operator << (std::ostream &, const rf_single_factor &);
87 };
88
89 void swap(rf_single_factor & a, rf_single_factor & b);
90
91
92 class rational_factorization
93 {
94
95 private:
96 sort_vector< rf_single_factor > factors;
97 int isign;
98 static int info;
99 unsigned int decomp_state;
100
101 void compose();
sort()102 void sort()
103 {
104 factors.sort();
105 }
106
107 void trialdiv(lidia_size_t index, unsigned int lower_bound,
108 unsigned int upper_bound, ecm_primes & prim);
109
110 void ecm(lidia_size_t index, int jobs_avail, int job_buffer[30][5],
111 ecm_primes & prim);
112
113 void ecm(lidia_size_t index, int rest_number_of_factors, int jobs_avail,
114 int job_buffer[30][5], ecm_primes & prim);
115
116 static const unsigned int ecm_params[29][3];
117 unsigned int ecm_read_max(int stell);
118 int ecm_job_planing(int strat[30], int buf[30][5]);
119
120 static const float qs_params[66][7];
121 rational_factorization & mpqs_impl(lidia_size_t index,
122 ecm_primes & prim);
123 rational_factorization & mpqs(lidia_size_t index, ecm_primes & prim);
124
125 void qs_read_par(unsigned int stellen, double &T, unsigned int &M,
126 unsigned int &groesse_FB, unsigned int &P_ONCE,
127 unsigned int &POLY, unsigned int &P_TOTAL,
128 unsigned int &smallstart);
129 int create_FB(unsigned int groesse, const bigint &kN, int **FB,
130 ecm_primes &prim);
131 bool qs_build_factors(const bigint & N, const bigint & kN,
132 unsigned int index, int *FB);
133 int compute_multiplier(const bigint & N, int bis, ecm_primes &prim);
134 static void compose(sort_vector< rf_single_factor > & v);
135 static void refine2(sort_vector< rf_single_factor > & v, rf_single_factor & sf,
136 const rf_single_factor & a, const rf_single_factor & b);
137
138 double zeitqs(unsigned int i, bool t = false);
139
140 public:
141
142 rational_factorization();
143 rational_factorization(int n, int exp = 1);
144 rational_factorization(unsigned int n, int exp = 1);
145 rational_factorization(long n, int exp = 1);
146 rational_factorization(unsigned long n, int exp = 1);
147 rational_factorization(const bigint & n, int exp = 1);
148 rational_factorization(const bigrational & n, int exp = 1);
149 rational_factorization(const rational_factorization &, int exp = 1);
150 ~rational_factorization();
151
152 rational_factorization & operator = (const rational_factorization &);
153
154 #ifndef HEADBANGER
155 void assign (long n, int exp = 1);
156 void assign (const bigint & n, int exp = 1);
157 void assign (const bigrational & n, int exp = 1);
158 void assign (const rational_factorization & f, int exp = 1);
159 #endif
160
161
162 void convert(base_vector< bigint > & basis, base_vector< int > & exponent);
163 bigint base(lidia_size_t index) const;
164 int exponent(lidia_size_t index) const;
165 void set_exponent(lidia_size_t index, int expo);
166
sign()167 int sign() const
168 {
169 return isign;
170 }
171
verbose(int a)172 void verbose(int a)
173 {
174 info = a;
175 }
176
no_of_comp()177 lidia_size_t no_of_comp() const
178 {
179 return factors.size();
180 }
181
182 bool is_prime_factor(lidia_size_t index);
183 bool is_prime_factorization();
184
185 //
186 // input / output
187 //
188
189 void pretty_print(std::ostream &);
190
191 friend std::istream & operator >> (std::istream &, rational_factorization &);
192 friend std::ostream & operator << (std::ostream &, const rational_factorization &);
193
194 //
195 // functions for computing with rational_factorizations
196 //
197
198 void invert();
199 void square();
200 friend void multiply (rational_factorization &,
201 const rational_factorization &,
202 const rational_factorization &);
203 friend void divide (rational_factorization &,
204 const rational_factorization &,
205 const rational_factorization &);
206
207 void refine();
208 bool refine(const bigint &);
209 bool refine_comp(lidia_size_t index, const bigint &);
210
211 friend bool operator == (const rational_factorization &,
212 const rational_factorization &);
213
214 //
215 // factoring functions
216 //
217
218
219 void trialdiv_comp(lidia_size_t index,
220 unsigned int upper_bound = 1000000,
221 unsigned int lower_bound = 1);
222 void trialdiv(unsigned int upper_bound = 1000000,
223 unsigned int lower_bound = 1);
224
225 void ecm_comp(lidia_size_t index, int upper_bound = 34,
226 int lower_bound = 6, int step = 3);
227 void ecm(int upper_bound = 34, int lower_bound = 6, int step = 3);
228
229 rational_factorization & mpqs_comp(lidia_size_t index);
230
231 void factor_comp(lidia_size_t index, int upper_bound = 34);
232 void factor(int upper_bound = 34);
factor_completely()233 void factor_completely()
234 {
235 while (!is_prime_factorization())
236 factor();
237 }
238
239 friend rational_factorization trialdiv(const bigint & N,
240 unsigned int upper_bound,
241 unsigned int lower_bound);
242 friend rational_factorization ecm(const bigint & N, int upper_bound,
243 int lower_bound, int step);
244 friend rational_factorization mpqs(const bigint & N);
245 friend rational_factorization factor(const bigint & N);
246 friend rational_factorization factor_completely(const bigint & N);
247
248 friend bigrational evaluate(const rational_factorization & r);
249 friend bigint evaluate_to_bigint(const rational_factorization & r);
250
251 };
252
253 std::istream & operator >> (std::istream &, rational_factorization &);
254 std::ostream & operator << (std::ostream &, const rational_factorization &);
255
256 inline
invert(rational_factorization & f,const rational_factorization & a)257 void invert(rational_factorization & f,
258 const rational_factorization & a)
259 {
260 f.assign(a);
261 f.invert();
262 }
263
264 inline
square(rational_factorization & f,const rational_factorization & a)265 void square(rational_factorization & f,
266 const rational_factorization & a)
267 {
268 f.assign(a);
269 f.square();
270 }
271
272 inline
273 rational_factorization operator *(const rational_factorization & a,
274 const rational_factorization & b)
275 {
276 rational_factorization c;
277
278 multiply(c, a, b);
279 return c;
280 }
281
282 inline
283 rational_factorization operator / (const rational_factorization & a,
284 const rational_factorization & b)
285 {
286 rational_factorization c;
287
288 divide(c, a, b);
289 return c;
290 }
291
292 bool operator == (const rational_factorization &,
293 const rational_factorization &);
294
295 inline
296 bool operator != (const rational_factorization & a,
297 const rational_factorization & b)
298 {
299 return !(a == b);
300 }
301
302 rational_factorization trialdiv(const bigint & N,
303 unsigned int upper_bound = 1000000,
304 unsigned int lower_bound = 1);
305 rational_factorization ecm(const bigint & N, int upper_bound = 34,
306 int lower_bound = 6, int step = 3);
307 rational_factorization mpqs(const bigint & N);
308 rational_factorization factor(const bigint & N);
309 rational_factorization factor_completely(const bigint & N);
310
311 bigrational evaluate(const rational_factorization & r);
312 bigint evaluate_to_bigint(const rational_factorization & r);
313
314
315
316
317 #ifdef LIDIA_NAMESPACE
318 } // end of namespace LiDIA
319 # undef IN_NAMESPACE_LIDIA
320 #endif
321
322
323
324 #endif // LIDIA_RATIONAL_FACTORIZATION_H_GUARD_
325