Line data Source code
1 : /* ecm-impl.h - header file for libecm
2 :
3 : Copyright 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011,
4 : 2012 Paul Zimmermann, Alexander Kruppa and Cyril Bouvier.
5 :
6 : This file is part of the ECM Library.
7 :
8 : The ECM Library is free software; you can redistribute it and/or modify
9 : it under the terms of the GNU Lesser General Public License as published by
10 : the Free Software Foundation; either version 3 of the License, or (at your
11 : option) any later version.
12 :
13 : The ECM Library is distributed in the hope that it will be useful, but
14 : WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
15 : or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
16 : License for more details.
17 :
18 : You should have received a copy of the GNU Lesser General Public License
19 : along with the ECM Library; see the file COPYING.LIB. If not, see
20 : http://www.gnu.org/licenses/ or write to the Free Software Foundation, Inc.,
21 : 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA. */
22 :
23 : #ifndef _ECM_IMPL_H
24 : #define _ECM_IMPL_H 1
25 :
26 : #include "config.h"
27 : #include "basicdefs.h"
28 : #include "ecm.h"
29 : #include "sp.h"
30 :
31 : #ifdef HAVE_SYS_TYPES_H
32 : #include <sys/types.h> /* needed for size_t */
33 : #endif
34 :
35 : #if HAVE_STDINT_H
36 : #include <stdint.h>
37 : /* needed for int64_t and uint64_t */
38 : /* or configure will define these for us if possible */
39 : #endif
40 :
41 : /* We do not use torsion.[ch] so far since they are not tested enough. */
42 : #define HAVE_TORSION
43 : /* We do not use addlaws.[ch] so far since they are not tested enough. */
44 : #define HAVE_ADDLAWS
45 :
46 : #include "ecm_int.h"
47 :
48 : #ifndef TUNE
49 : #include "ecm-params.h"
50 : #else
51 : extern size_t MPZMOD_THRESHOLD;
52 : extern size_t REDC_THRESHOLD;
53 : #define TUNE_MULREDC_TABLE {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
54 : #define TUNE_SQRREDC_TABLE {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
55 : #define LIST_MUL_TABLE {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
56 : #endif
57 : extern size_t mpn_mul_lo_threshold[];
58 :
59 : #define TUNE_LIST_MUL_N_MAX_SIZE 32
60 :
61 : #include <stdio.h> /* needed for "FILE *" */
62 : #include <limits.h>
63 :
64 : #if defined (__STDC__) \
65 : || defined (__cplusplus) \
66 : || defined (_AIX) \
67 : || defined (__DECC) \
68 : || (defined (__mips) && defined (_SYSTYPE_SVR4)) \
69 : || defined (_MSC_VER) \
70 : || defined (_WIN32)
71 : #define __ECM_HAVE_TOKEN_PASTE 1
72 : #else
73 : #define __ECM_HAVE_TOKEN_PASTE 0
74 : #endif
75 :
76 : #ifndef __ECM
77 : #if __ECM_HAVE_TOKEN_PASTE
78 : #define __ECM(x) __ecm_##x
79 : #else
80 : #define __ECM(x) __ecm_/**/x
81 : #endif
82 : #endif
83 :
84 : #define ECM_STDOUT __ecm_stdout
85 : #define ECM_STDERR __ecm_stderr
86 : extern FILE *ECM_STDOUT, *ECM_STDERR;
87 :
88 : /* #define TIMING_CRT */
89 :
90 : /* default B2 choice: pow (B1 * METHOD_COST / 6.0, DEFAULT_B2_EXPONENT) */
91 : #define DEFAULT_B2_EXPONENT 1.43
92 : #define PM1_COST 1.0 / 6.0
93 : #define PP1_COST 2.0 / 6.0
94 : #define ECM_COST 11.0 / 6.0
95 : /* For new P-/+1 stage 2: */
96 : #define PM1FS2_DEFAULT_B2_EXPONENT 1.7
97 : #define PM1FS2_COST 1.0 / 4.0
98 : #define PP1FS2_COST 1.0 / 4.0
99 :
100 : /* define top-level multiplication */
101 : #define KARA 2
102 : #define TOOM3 3
103 : #define TOOM4 4
104 : #define KS 5
105 : #define NTT 6
106 :
107 : /* maximal limb size of assembly mulredc */
108 : #define MULREDC_ASSEMBLY_MAX 20
109 :
110 : #include "sp.h"
111 :
112 : #include <assert.h>
113 : #define ASSERT_ALWAYS(expr) assert (expr)
114 : #ifdef WANT_ASSERT
115 : #define ASSERT(expr) assert (expr)
116 : #else
117 : #define ASSERT(expr) do {} while (0)
118 : #endif
119 :
120 : /* thresholds */
121 : #define MPN_MUL_LO_THRESHOLD 32
122 :
123 : /* base2mod is used when size(2^n+/-1) <= BASE2_THRESHOLD * size(cofactor) */
124 : #define BASE2_THRESHOLD 1.4
125 :
126 : /* default number of probable prime tests */
127 : #define PROBAB_PRIME_TESTS 1
128 :
129 : /* threshold for median product */
130 : #define KS_TMUL_THRESHOLD 8e5
131 :
132 : #define ABS(x) ((x) >= 0 ? (x) : -(x))
133 :
134 : /* getprime */
135 : #define WANT_FREE_PRIME_TABLE(p) (p < 0.0)
136 : #define FREE_PRIME_TABLE -1.0
137 :
138 : /* 2^n+-1 with n < MOD_MINBASE2 cannot use base-2 reduction */
139 : #define MOD_MINBASE2 16
140 :
141 : /* Various logging levels */
142 : /* OUTPUT_ALWAYS means print always, regardless of verbose value */
143 : #define OUTPUT_ALWAYS 0
144 : /* OUTPUT_NORMAL means print during normal program execution */
145 : #define OUTPUT_NORMAL 1
146 : /* OUTPUT_VERBOSE means print if the user requested more verbosity */
147 : #define OUTPUT_VERBOSE 2
148 : /* OUTPUT_RESVERBOSE is for printing residues (after stage 1 etc) */
149 : #define OUTPUT_RESVERBOSE 3
150 : /* OUTPUT_DEVVERBOSE is for printing internal parameters (for developers) */
151 : #define OUTPUT_DEVVERBOSE 4
152 : /* OUTPUT_TRACE is for printing trace data, produces lots of output */
153 : #define OUTPUT_TRACE 5
154 : /* OUTPUT_ERROR is for printing error messages */
155 : #define OUTPUT_ERROR -1
156 :
157 : /* Interval length for writing checkpoints in stage 1, in milliseconds */
158 : #define CHKPNT_PERIOD 600000
159 :
160 : /* Does the parametrization imply batch mode ? */
161 : #define IS_BATCH_MODE(p) ( p == ECM_PARAM_BATCH_SQUARE || \
162 : p == ECM_PARAM_BATCH_2 || \
163 : p == ECM_PARAM_BATCH_32BITS_D )
164 :
165 : typedef mpz_t mpres_t;
166 :
167 : typedef mpz_t* listz_t;
168 :
169 : typedef struct
170 : {
171 : mpres_t x;
172 : mpres_t y;
173 : } __point_struct;
174 : typedef __point_struct point;
175 :
176 : typedef struct
177 : {
178 : mpres_t x;
179 : mpres_t y;
180 : mpres_t A;
181 : /* for CM curves */
182 : int disc;
183 : mpres_t sq[10];
184 : } __curve_struct;
185 : typedef __curve_struct curve;
186 :
187 : typedef struct
188 : {
189 : unsigned long d1;
190 : unsigned long d2;
191 : mpz_t i0;
192 : int S;
193 : } __root_params_t;
194 : typedef __root_params_t root_params_t;
195 :
196 : typedef struct
197 : {
198 : unsigned long P, s_1, s_2, l;
199 : mpz_t m_1;
200 : const char *file_stem;
201 : } __faststage2_param_t;
202 : typedef __faststage2_param_t faststage2_param_t;
203 :
204 : typedef struct
205 : {
206 : unsigned int size_fd; /* How many entries .fd has, always nr * (S+1) */
207 : unsigned int nr; /* How many separate progressions there are */
208 : unsigned int next; /* From which progression to take the next root */
209 : unsigned int S; /* Degree of the polynomials */
210 : unsigned int dsieve; /* Values not coprime to dsieve are skipped */
211 : unsigned int rsieve; /* Which residue mod dsieve current .next belongs to */
212 : int dickson_a; /* Parameter for Dickson polynomials */
213 : } progression_params_t;
214 :
215 : typedef struct
216 : {
217 : progression_params_t params;
218 : point *fd;
219 : unsigned int size_T; /* How many entries T has */
220 : mpres_t *T; /* For temp values. FIXME: should go! */
221 : curve *X; /* The curve the points are on */
222 : } ecm_roots_state_t;
223 :
224 :
225 : typedef struct
226 : {
227 : progression_params_t params;
228 : mpres_t *fd;
229 : int invtrick;
230 : } pm1_roots_state_t;
231 :
232 : typedef struct
233 : {
234 : progression_params_t params;
235 : point *fd; /* for S != 1 */
236 : mpres_t tmp[4]; /* for S=1 */
237 : } pp1_roots_state_t;
238 :
239 : typedef struct
240 : {
241 : int alloc;
242 : int degree;
243 : listz_t coeff;
244 : } __polyz_struct;
245 : typedef __polyz_struct polyz_t[1];
246 :
247 : typedef struct
248 : {
249 : int repr; /* ECM_MOD_MPZ: plain modulus, possibly normalized
250 : ECM_MOD_BASE2: base 2 number
251 : ECM_MOD_MODMULN: MODMULN
252 : ECM_MOD_REDC: REDC representation */
253 : int bits; /* in case of a base 2 number, 2^k[+-]1, bits = [+-]k
254 : in case of MODMULN or REDC representation, nr. of
255 : bits b so that 2^b > orig_modulus and
256 : GMP_NUMB_BITS | b */
257 : int Fermat; /* If repr = 1 (base 2 number): If modulus is 2^(2^m)+1,
258 : i.e. bits = 2^m, then Fermat = 2^m, 0 otherwise.
259 : If repr != 1, undefined */
260 : mp_limb_t *Nprim; /* For MODMULN */
261 : mpz_t orig_modulus; /* The original modulus N */
262 : mpz_t aux_modulus; /* Used only for MPZ and REDC:
263 : - the auxiliary modulus value (i.e. normalized
264 : modulus, or -1/N (mod 2^bits) for REDC,
265 : - B^(n + ceil(n/2)) mod N for MPZ,
266 : where B = 2^GMP_NUMB_BITS */
267 : mpz_t multiple; /* The smallest multiple of N that is larger or
268 : equal to 2^bits for REDC/MODMULN */
269 : mpz_t R2, R3; /* For MODMULN and REDC, R^2 and R^3 (mod orig_modulus),
270 : where R = 2^bits. */
271 : mpz_t temp1, temp2; /* Temp values used during multiplication etc. */
272 : } __mpmod_struct;
273 : typedef __mpmod_struct mpmod_t[1];
274 :
275 : #if defined (__cplusplus)
276 : extern "C" {
277 : #endif
278 :
279 : /* getprime.c */
280 : #define getprime __ECM(getprime)
281 : double getprime ();
282 : #define getprime_clear __ECM(getprime_clear)
283 : void getprime_clear ();
284 : #define getprime_seek __ECM(getprime_seek)
285 : void getprime_seek (double);
286 :
287 : /* pm1fs2.c */
288 : #define pm1fs2_memory_use __ECM(pm1fs2_ntt_memory_use)
289 : size_t pm1fs2_memory_use (const unsigned long, const mpz_t, const int);
290 : #define pm1fs2_maxlen __ECM(pm1fs2_maxlen)
291 : unsigned long pm1fs2_maxlen (const size_t, const mpz_t, const int);
292 : #define pp1fs2_memory_use __ECM(pp1fs2_ntt_memory_use)
293 : size_t pp1fs2_memory_use (const unsigned long, const mpz_t, const int,
294 : const int);
295 : #define pp1fs2_maxlen __ECM(pp1fs2_maxlen)
296 : unsigned long pp1fs2_maxlen (const size_t, const mpz_t, const int, const int);
297 : #define choose_P __ECM(choose_P)
298 : long choose_P (const mpz_t, const mpz_t, const unsigned long,
299 : const unsigned long, faststage2_param_t *, mpz_t, mpz_t,
300 : const int, const int);
301 : #define pm1fs2 __ECM(pm1fs2)
302 : int pm1fs2 (mpz_t, const mpres_t, mpmod_t, const faststage2_param_t *);
303 : #define pm1fs2_ntt __ECM(pm1fs2_ntt)
304 : int pm1fs2_ntt (mpz_t, const mpres_t, mpmod_t, const faststage2_param_t *);
305 : #define pp1fs2 __ECM(pp1fs2)
306 : int pp1fs2 (mpz_t, const mpres_t, mpmod_t, const faststage2_param_t *);
307 : #define pp1fs2_ntt __ECM(pp1fs2_ntt)
308 : int pp1fs2_ntt (mpz_t, const mpres_t, mpmod_t, const faststage2_param_t *,
309 : const int);
310 :
311 : /* bestd.c */
312 : #define bestD __ECM(bestD)
313 : int bestD (root_params_t *, unsigned long *, unsigned long *, mpz_t,
314 : mpz_t, int, int, double, int, mpmod_t);
315 :
316 : /* ecm.c */
317 : #define choose_S __ECM(choose_S)
318 : int choose_S (mpz_t);
319 : #define add3 __ECM(add3)
320 : void add3 (mpres_t, mpres_t, mpres_t, mpres_t, mpres_t, mpres_t, mpres_t,
321 : mpres_t, mpmod_t, mpres_t, mpres_t, mpres_t);
322 : #define duplicate __ECM(duplicate)
323 : void duplicate (mpres_t, mpres_t, mpres_t, mpres_t, mpmod_t, mpres_t, mpres_t,
324 : mpres_t, mpres_t);
325 :
326 : #define ecm_mul __ECM(ecm_mul)
327 : void ecm_mul (mpres_t, mpres_t, mpz_t, mpmod_t, mpres_t);
328 : #define print_B1_B2_poly __ECM(print_B1_B2_poly)
329 : void print_B1_B2_poly (int, int, double, double, mpz_t, mpz_t, mpz_t, int S,
330 : mpz_t, int, int, mpz_t, int, unsigned int);
331 : #define set_stage_2_params __ECM(set_stage_2_params)
332 : int set_stage_2_params (mpz_t, mpz_t, mpz_t, mpz_t, root_params_t *,
333 : double, unsigned long *, const int, int, int *,
334 : unsigned long *, char *, double, int, mpmod_t);
335 : #define print_expcurves __ECM(print_expcurves)
336 : void print_expcurves (double, const mpz_t, unsigned long, unsigned long, int,
337 : int);
338 : #define print_exptime __ECM(print_exptime)
339 : void print_exptime (double, const mpz_t, unsigned long, unsigned long, int,
340 : double, int);
341 : #define montgomery_to_weierstrass __ECM(montgomery_to_weierstrass)
342 : int montgomery_to_weierstrass (mpz_t, mpres_t, mpres_t, mpres_t, mpmod_t);
343 :
344 : /* ecm2.c */
345 : #define ecm_rootsF __ECM(ecm_rootsF)
346 : int ecm_rootsF (mpz_t, listz_t, root_params_t *, unsigned long,
347 : curve *, mpmod_t);
348 : #define ecm_rootsG_init __ECM(ecm_rootsG_init)
349 : ecm_roots_state_t* ecm_rootsG_init (mpz_t, curve *, root_params_t *,
350 : unsigned long, unsigned long, mpmod_t);
351 : #define ecm_rootsG __ECM(ecm_rootsG)
352 : int ecm_rootsG (mpz_t, listz_t, unsigned long, ecm_roots_state_t *,
353 : mpmod_t);
354 : #define ecm_rootsG_clear __ECM(ecm_rootsG_clear)
355 : void ecm_rootsG_clear (ecm_roots_state_t *, mpmod_t);
356 :
357 : /* lucas.c */
358 : #define pp1_mul_prac __ECM(pp1_mul_prac)
359 : void pp1_mul_prac (mpres_t, ecm_uint, mpmod_t, mpres_t, mpres_t,
360 : mpres_t, mpres_t, mpres_t);
361 :
362 : /* stage2.c */
363 : #define stage2 __ECM(stage2)
364 : int stage2 (mpz_t, void *, mpmod_t, unsigned long, unsigned long,
365 : root_params_t *, int, char *, unsigned int, int (*)(void));
366 : #define init_progression_coeffs __ECM(init_progression_coeffs)
367 : listz_t init_progression_coeffs (mpz_t, const unsigned long, const unsigned long,
368 : const unsigned int, const unsigned int,
369 : const unsigned int, const int);
370 : #define init_roots_params __ECM(init_roots_params)
371 : void init_roots_params (progression_params_t *, const int,
372 : const unsigned long, const unsigned long,
373 : const double);
374 : #define memory_use __ECM(memory_use)
375 : double memory_use (unsigned long, unsigned int, unsigned int, mpmod_t);
376 :
377 : /* listz.c */
378 : #define list_mul_mem __ECM(list_mul_mem)
379 : int list_mul_mem (unsigned int);
380 : #define init_list __ECM(init_list)
381 : listz_t init_list (unsigned int);
382 : #define init_list2 __ECM(init_list2)
383 : listz_t init_list2 (unsigned int, unsigned int);
384 : #define clear_list __ECM(clear_list)
385 : void clear_list (listz_t, unsigned int);
386 : #define list_inp_raw __ECM(list_inp_raw)
387 : int list_inp_raw (listz_t, FILE *, unsigned int);
388 : #define list_out_raw __ECM(list_out_raw)
389 : int list_out_raw (FILE *, listz_t, unsigned int);
390 : #define print_list __ECM(print_list)
391 : void print_list (listz_t, unsigned int);
392 : #define list_set __ECM(list_set)
393 : void list_set (listz_t, listz_t, unsigned int);
394 : #define list_revert __ECM(list_revert)
395 : void list_revert (listz_t, unsigned int);
396 : #define list_swap __ECM(list_swap)
397 : void list_swap (listz_t, listz_t, unsigned int);
398 : #define list_neg __ECM(list_neg)
399 : void list_neg (listz_t, listz_t, unsigned int, mpz_t);
400 : #define list_mod __ECM(list_mod)
401 : void list_mod (listz_t, listz_t, unsigned int, mpz_t);
402 : #define list_add __ECM(list_add)
403 : void list_add (listz_t, listz_t, listz_t, unsigned int);
404 : #define list_sub __ECM(list_sub)
405 : void list_sub (listz_t, listz_t, listz_t, unsigned int);
406 : #define list_mul_z __ECM(list_mul_z)
407 : void list_mul_z (listz_t, listz_t, mpz_t, unsigned int, mpz_t);
408 : #define list_mulup __ECM(list_mulup)
409 : void list_mulup (listz_t, unsigned int, mpz_t, mpz_t);
410 : #define list_zero __ECM(list_zero)
411 : void list_zero (listz_t, unsigned int);
412 : #define list_mul __ECM(list_mul)
413 : void list_mul (listz_t, listz_t, unsigned int, listz_t,
414 : unsigned int, int, listz_t);
415 : #define list_mul_high __ECM(list_mul_high)
416 : void list_mul_high (listz_t, listz_t, listz_t, unsigned int);
417 : #define list_mulmod __ECM(list_mulmod)
418 : void list_mulmod (listz_t, listz_t, listz_t, listz_t, unsigned int,
419 : listz_t, mpz_t);
420 : #define PolyFromRoots __ECM(PolyFromRoots)
421 : void PolyFromRoots (listz_t, listz_t, unsigned int, listz_t, mpz_t);
422 : #define PolyFromRoots_Tree __ECM(PolyFromRoots_Tree)
423 : int PolyFromRoots_Tree (listz_t, listz_t, unsigned int, listz_t, int,
424 : mpz_t, listz_t*, FILE*, unsigned int);
425 :
426 : #define ntt_PolyFromRoots __ECM(ntt_PolyFromRoots)
427 : void ntt_PolyFromRoots (mpzv_t, mpzv_t, spv_size_t, mpzv_t, mpzspm_t);
428 : #define ntt_PolyFromRoots_Tree __ECM(ntt_PolyFromRoots_Tree)
429 : int ntt_PolyFromRoots_Tree (mpzv_t, mpzv_t, spv_size_t, mpzv_t,
430 : int, mpzspm_t, mpzv_t *, FILE *);
431 : #define ntt_polyevalT __ECM(ntt_polyevalT)
432 : int ntt_polyevalT (mpzv_t, spv_size_t, mpzv_t *, mpzv_t, mpzspv_t,
433 : mpzspm_t, char *);
434 : #define ntt_mul __ECM(ntt_mul)
435 : void ntt_mul (mpzv_t, mpzv_t, mpzv_t, spv_size_t, mpzv_t, int, mpzspm_t);
436 : #define ntt_PrerevertDivision __ECM(ntt_PrerevertDivision)
437 : void ntt_PrerevertDivision (mpzv_t, mpzv_t, mpzv_t, mpzspv_t, mpzspv_t,
438 : spv_size_t, mpzv_t, mpzspm_t);
439 : #define ntt_PolyInvert __ECM(ntt_PolyInvert)
440 : void ntt_PolyInvert (mpzv_t, mpzv_t, spv_size_t, mpzv_t, mpzspm_t);
441 :
442 : #define PrerevertDivision __ECM(PrerevertDivision)
443 : int PrerevertDivision (listz_t, listz_t, listz_t, unsigned int, listz_t,
444 : mpz_t);
445 : #define PolyInvert __ECM(PolyInvert)
446 : void PolyInvert (listz_t, listz_t, unsigned int, listz_t, mpz_t);
447 :
448 : #define RecursiveDivision __ECM(RecursiveDivision)
449 : void RecursiveDivision (listz_t, listz_t, listz_t, unsigned int,
450 : listz_t, mpz_t, int);
451 :
452 : /* polyeval.c */
453 : #define polyeval __ECM(polyeval)
454 : void polyeval (listz_t, unsigned int, listz_t*, listz_t, mpz_t, unsigned int);
455 : #define polyeval_tellegen __ECM(polyeval_tellegen)
456 : int polyeval_tellegen (listz_t, unsigned int, listz_t*, listz_t,
457 : unsigned int, listz_t, mpz_t, char *);
458 : #define TUpTree __ECM(TUpTree)
459 : void TUpTree (listz_t, listz_t *, unsigned int, listz_t, int, unsigned int,
460 : mpz_t, FILE *);
461 :
462 : /* ks-multiply.c */
463 : #define list_mul_n_basecase __ECM(list_mul_n_basecase)
464 : void list_mul_n_basecase (listz_t, listz_t, listz_t, unsigned int);
465 : #define list_mul_n_karatsuba __ECM(list_mul_n_karatsuba)
466 : void list_mul_n_karatsuba (listz_t, listz_t, listz_t, unsigned int);
467 : #define list_mul_n_KS1 __ECM(list_mul_n_KS1)
468 : void list_mul_n_KS1 (listz_t, listz_t, listz_t, unsigned int);
469 : #define list_mul_n_KS2 __ECM(list_mul_n_KS2)
470 : void list_mul_n_KS2 (listz_t, listz_t, listz_t, unsigned int);
471 : #define list_mult_n __ECM(list_mult_n)
472 : void list_mult_n (listz_t, listz_t, listz_t, unsigned int);
473 : #define TMulKS __ECM(TMulKS)
474 : int TMulKS (listz_t, unsigned int, listz_t, unsigned int, listz_t,
475 : unsigned int, mpz_t, int);
476 : #define ks_wrapmul_m __ECM(ks_wrapmul_m)
477 : unsigned int ks_wrapmul_m (unsigned int, unsigned int, mpz_t);
478 : #define ks_wrapmul __ECM(ks_wrapmul)
479 : unsigned int ks_wrapmul (listz_t, unsigned int, listz_t, unsigned int,
480 : listz_t, unsigned int, mpz_t);
481 :
482 : /* mpmod.c */
483 : /* Define MPRESN_NO_ADJUSTMENT if mpresn_add, mpresn_sub and mpresn_addsub
484 : should perform no adjustment step. This yields constraints on N. */
485 : /* #define MPRESN_NO_ADJUSTMENT */
486 : #define isbase2 __ECM(isbase2)
487 : int isbase2 (const mpz_t, const double);
488 : #define mpmod_init __ECM(mpmod_init)
489 : int mpmod_init (mpmod_t, const mpz_t, int);
490 : #define mpmod_init_MPZ __ECM(mpmod_init_MPZ)
491 : void mpmod_init_MPZ (mpmod_t, const mpz_t);
492 : #define mpmod_init_BASE2 __ECM(mpmod_init_BASE2)
493 : int mpmod_init_BASE2 (mpmod_t, const int, const mpz_t);
494 : #define mpmod_init_MODMULN __ECM(mpmod_init_MODMULN)
495 : void mpmod_init_MODMULN (mpmod_t, const mpz_t);
496 : #define mpmod_init_REDC __ECM(mpmod_init_REDC)
497 : void mpmod_init_REDC (mpmod_t, const mpz_t);
498 : #define mpmod_clear __ECM(mpmod_clear)
499 : void mpmod_clear (mpmod_t);
500 : #define mpmod_init_set __ECM(mpmod_init_set)
501 : void mpmod_init_set (mpmod_t, const mpmod_t);
502 : #define mpmod_pausegw __ECM(mpmod_pausegw)
503 : void mpmod_pausegw (const mpmod_t modulus);
504 : #define mpmod_contgw __ECM(mpmod_contgw)
505 : void mpmod_contgw (const mpmod_t modulus);
506 : #define mpres_equal __ECM(mpres_equal)
507 : int mpres_equal (const mpres_t, const mpres_t, mpmod_t);
508 : #define mpres_pow __ECM(mpres_pow)
509 : void mpres_pow (mpres_t, const mpres_t, const mpz_t, mpmod_t);
510 : #define mpres_ui_pow __ECM(mpres_ui_pow)
511 : void mpres_ui_pow (mpres_t, const unsigned long, const mpres_t, mpmod_t);
512 : #define mpres_mul __ECM(mpres_mul)
513 : void mpres_mul (mpres_t, const mpres_t, const mpres_t, mpmod_t) ATTRIBUTE_HOT;
514 : #define mpres_sqr __ECM(mpres_sqr)
515 : void mpres_sqr (mpres_t, const mpres_t, mpmod_t) ATTRIBUTE_HOT;
516 : #define mpres_mul_z_to_z __ECM(mpres_mul_z_to_z)
517 : void mpres_mul_z_to_z (mpz_t, const mpres_t, const mpz_t, mpmod_t);
518 : #define mpres_set_z_for_gcd __ECM(mpres_set_z_for_gcd)
519 : void mpres_set_z_for_gcd (mpres_t, const mpz_t, mpmod_t);
520 : #define mpres_set_z_for_gcd_fix __ECM(mpres_set_z_for_gcd_fix)
521 : void mpres_set_z_for_gcd_fix (mpres_t, const mpres_t, const mpz_t, mpmod_t);
522 : #define mpres_div_2exp __ECM(mpres_div_2exp)
523 : void mpres_div_2exp (mpres_t, const mpres_t, const unsigned int, mpmod_t);
524 : #define mpres_add_ui __ECM(mpres_add_ui)
525 : void mpres_add_ui (mpres_t, const mpres_t, const unsigned long, mpmod_t);
526 : #define mpres_add __ECM(mpres_add)
527 : void mpres_add (mpres_t, const mpres_t, const mpres_t, mpmod_t) ATTRIBUTE_HOT;
528 : #define mpres_sub_ui __ECM(mpres_sub_ui)
529 : void mpres_sub_ui (mpres_t, const mpres_t, const unsigned long, mpmod_t);
530 : #define mpres_ui_sub __ECM(mpres_ui_sub)
531 : void mpres_ui_sub (mpres_t, const unsigned long, const mpres_t, mpmod_t);
532 : #define mpres_sub __ECM(mpres_sub)
533 : void mpres_sub (mpres_t, const mpres_t, const mpres_t, mpmod_t) ATTRIBUTE_HOT;
534 : #define mpres_set_z __ECM(mpres_set_z)
535 : void mpres_set_z (mpres_t, const mpz_t, mpmod_t);
536 : #define mpres_get_z __ECM(mpres_get_z)
537 : void mpres_get_z (mpz_t, const mpres_t, mpmod_t);
538 : #define mpres_set_ui __ECM(mpres_set_ui)
539 : void mpres_set_ui (mpres_t, const unsigned long, mpmod_t);
540 : #define mpres_set_si __ECM(mpres_set_si)
541 : void mpres_set_si (mpres_t, const long, mpmod_t);
542 : #define mpres_init __ECM(mpres_init)
543 : void mpres_init (mpres_t, const mpmod_t);
544 : #define mpres_clear __ECM(mpres_clear)
545 : void mpres_clear (mpres_t, const mpmod_t);
546 : #define mpres_realloc __ECM(mpres_realloc)
547 : void mpres_realloc (mpres_t, const mpmod_t);
548 : #define mpres_mul_ui __ECM(mpres_mul_ui)
549 : void mpres_mul_ui (mpres_t, const mpres_t, const unsigned long, mpmod_t);
550 : #define mpres_mul_2exp __ECM(mpres_mul_2exp)
551 : void mpres_mul_2exp (mpres_t, const mpres_t, const unsigned long, mpmod_t);
552 : #define mpres_muldivbysomething_si __ECM(mpres_muldivbysomething_si)
553 : void mpres_muldivbysomething_si (mpres_t, const mpres_t, const long, mpmod_t);
554 : #define mpres_neg __ECM(mpres_neg)
555 : void mpres_neg (mpres_t, const mpres_t, mpmod_t);
556 : #define mpres_invert __ECM(mpres_invert)
557 : int mpres_invert (mpres_t, const mpres_t, mpmod_t);
558 : #define mpres_gcd __ECM(mpres_gcd)
559 : void mpres_gcd (mpz_t, const mpres_t, const mpmod_t);
560 : #define mpres_out_str __ECM(mpres_out_str)
561 : void mpres_out_str (FILE *, const unsigned int, const mpres_t, mpmod_t);
562 : #define mpres_is_zero __ECM(mpres_is_zero)
563 : int mpres_is_zero (const mpres_t, mpmod_t);
564 : #define mpres_set(a,b,n) mpz_set (a, b)
565 : #define mpres_swap(a,b,n) mpz_swap (a, b)
566 : #define mpresn_mul __ECM(mpresn_mul)
567 : void mpresn_mul (mpres_t, const mpres_t, const mpres_t, mpmod_t);
568 : #define mpresn_addsub __ECM(mpresn_addsub)
569 : void mpresn_addsub (mpres_t, mpres_t, const mpres_t, const mpres_t, mpmod_t);
570 : #define mpresn_pad __ECM(mpresn_pad)
571 : void mpresn_pad (mpres_t R, mpmod_t N);
572 : #define mpresn_unpad __ECM(mpresn_unpad)
573 : void mpresn_unpad (mpres_t R);
574 : #define mpresn_sqr __ECM(mpresn_sqr)
575 : void mpresn_sqr (mpres_t, const mpres_t, mpmod_t);
576 : #define mpresn_add __ECM(mpresn_add)
577 : void mpresn_add (mpres_t, const mpres_t, const mpres_t, mpmod_t);
578 : #define mpresn_sub __ECM(mpresn_sub)
579 : void mpresn_sub (mpres_t, const mpres_t, const mpres_t, mpmod_t);
580 : #define mpresn_mul_1 __ECM(mpresn_mul_ui)
581 : void mpresn_mul_1 (mpres_t, const mpres_t, const mp_limb_t, mpmod_t);
582 :
583 : /* mul_lo.c */
584 : #define ecm_mul_lo_n __ECM(ecm_mul_lo_n)
585 : void ecm_mul_lo_n (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t);
586 : #define ecm_mul_lo_basecase __ECM(ecm_mul_lo_basecase)
587 : void ecm_mul_lo_basecase (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t);
588 :
589 : /* median.c */
590 : #define TMulGen __ECM(TMulGen)
591 : int
592 : TMulGen (listz_t, unsigned int, listz_t, unsigned int, listz_t,
593 : unsigned int, listz_t, mpz_t);
594 : #define TMulGen_space __ECM(TMulGen_space)
595 : unsigned int TMulGen_space (unsigned int, unsigned int, unsigned int);
596 :
597 : /* schoen_strass.c */
598 : #define DEFAULT 0
599 : #define MONIC 1
600 : #define NOPAD 2
601 : #define F_mul __ECM(F_mul)
602 : unsigned int F_mul (mpz_t *, mpz_t *, mpz_t *, unsigned int, int,
603 : unsigned int, mpz_t *);
604 : #define F_mul_trans __ECM(F_mul_trans)
605 : unsigned int F_mul_trans (mpz_t *, mpz_t *, mpz_t *, unsigned int,
606 : unsigned int, unsigned int, mpz_t *);
607 : #define F_clear __ECM(F_clear)
608 : void F_clear ();
609 :
610 : /* rho.c */
611 : #define rhoinit __ECM(rhoinit)
612 : void rhoinit (int, int);
613 : #define ecmprob __ECM(ecmprob)
614 : double ecmprob (double, double, double, double, int);
615 : double pm1prob (double, double, double, double, int, const mpz_t);
616 :
617 : /* pm1.c */
618 : void print_prob (double, const mpz_t, unsigned long, unsigned long, int,
619 : const mpz_t);
620 :
621 : /* auxlib.c */
622 : #define mpz_add_si __ECM(mpz_add_si)
623 : void mpz_add_si (mpz_t, mpz_t, long);
624 : #define mpz_sub_si __ECM(mpz_sub_si)
625 : void mpz_sub_si (mpz_t, mpz_t, long);
626 : #define mpz_divby3_1op __ECM(mpz_divby3_1op)
627 : void mpz_divby3_1op (mpz_t);
628 : #define double_to_size __ECM(double_to_size)
629 : size_t double_to_size (double d);
630 : #define cputime __ECM(cputime)
631 : long cputime (void);
632 : #define realtime __ECM(realtime)
633 : long realtime (void);
634 : #define elltime __ECM(elltime)
635 : long elltime (long, long);
636 : #define test_verbose __ECM(test_verbose)
637 : int test_verbose (int);
638 : #define set_verbose __ECM(set_verbose)
639 : void set_verbose (int);
640 : #define outputf __ECM(outputf)
641 : int outputf (int, const char *, ...);
642 : #define writechkfile __ECM(writechkfile)
643 : void writechkfile (char *, int, double, mpmod_t, mpres_t, mpres_t, mpres_t, mpres_t);
644 : #define aux_fseek64 __ECM(aux_fseek64)
645 : int aux_fseek64(FILE *, const int64_t, const int);
646 : #define ecm_tstbit __ECM(ecm_tstbit)
647 : int ecm_tstbit (mpz_srcptr, ecm_uint);
648 :
649 : /* Due to GMP (6.x and prior) using long as input to mpz_tstbit, factors would be missed
650 : on computers with 32-bit longs in batch mode when using B1 > 2977044736UL.
651 : So, we need to use our own function when long is not 64-bits wide */
652 : #if ULONG_MAX == 0xffffffffUL
653 : #undef mpz_tstbit
654 : #define mpz_tstbit ecm_tstbit
655 : #endif
656 :
657 : /* auxarith.c */
658 : #define gcd __ECM(gcd)
659 : unsigned long gcd (unsigned long, unsigned long);
660 : #define eulerphi __ECM(eulerphi)
661 : unsigned long eulerphi (unsigned long);
662 : #define ceil_log2 __ECM(ceil_log2)
663 : unsigned int ceil_log2 (unsigned long);
664 : #define find_factor __ECM(find_factor)
665 : unsigned long find_factor (const unsigned long);
666 :
667 : /* random.c */
668 : #define init_randstate __ECM(init_randstate)
669 : void init_randstate (gmp_randstate_t);
670 : #define pp1_random_seed __ECM(pp1_random_seed)
671 : void pp1_random_seed (mpz_t, mpz_t, gmp_randstate_t);
672 : #define pm1_random_seed __ECM(pm1_random_seed)
673 : void pm1_random_seed (mpz_t, mpz_t, gmp_randstate_t);
674 : #define get_random_ul __ECM(get_random_ul)
675 : unsigned long get_random_ul (void);
676 :
677 : /* Fgw.c */
678 : #ifdef HAVE_GWNUM
679 : int gw_ecm_stage1 (mpz_t, curve *, mpmod_t, double, double *, mpz_t,
680 : double, unsigned long, unsigned long, signed long);
681 : #endif
682 :
683 : /* batch.c */
684 : #define compute_s __ECM(compute_s )
685 : void compute_s (mpz_t, ecm_uint, int *);
686 : #define ecm_stage1_batch __ECM(ecm_stage1_batch)
687 : int ecm_stage1_batch (mpz_t, mpres_t, mpres_t, mpmod_t, double, double *,
688 : int, mpz_t);
689 :
690 : /* parametrizations.c */
691 : #define get_curve_from_random_parameter __ECM(get_curve_from_random_parameter)
692 : int get_curve_from_random_parameter (mpz_t, mpres_t, mpres_t, mpz_t, int,
693 : mpmod_t, gmp_randstate_t);
694 : #define get_curve_from_param0 __ECM(get_curve_from_param0)
695 : int get_curve_from_param0 (mpz_t, mpres_t, mpres_t, mpz_t, mpmod_t);
696 : #define get_curve_from_param1 __ECM(get_curve_from_param1)
697 : int get_curve_from_param1 (mpres_t, mpres_t, mpz_t, mpmod_t);
698 : #define get_curve_from_param2 __ECM(get_curve_from_param2)
699 : int get_curve_from_param2 (mpz_t, mpres_t, mpres_t, mpz_t, mpmod_t);
700 : #define get_curve_from_param3 __ECM(get_curve_from_param3)
701 : int get_curve_from_param3 (mpres_t, mpres_t, mpz_t, mpmod_t);
702 : #define get_default_param __ECM(get_default_param)
703 : int get_default_param (int, double, int);
704 :
705 : /* sets_long.c */
706 : /* A set of long ints */
707 : typedef struct {
708 : unsigned long card;
709 : long elem[1];
710 : } set_long_t;
711 :
712 : /* A set of sets of long ints */
713 : typedef struct {
714 : unsigned long nr;
715 : set_long_t sets[1];
716 : } sets_long_t;
717 :
718 : #define quicksort_long __ECM(quicksort_long)
719 : void quicksort_long (long *, unsigned long);
720 : #define sets_print __ECM(sets_print)
721 : void sets_print (const int, sets_long_t *);
722 : #define sets_max __ECM(sets_max)
723 : void sets_max (mpz_t, const unsigned long);
724 : #define sets_sumset __ECM(sets_sumset)
725 : void sets_sumset (set_long_t *, const sets_long_t *);
726 : #define sets_sumset_minmax __ECM(sets_sumset_minmax)
727 : void sets_sumset_minmax (mpz_t, const sets_long_t *, const int);
728 : #define sets_extract __ECM(sets_extract)
729 : void sets_extract (sets_long_t *, size_t *, sets_long_t *,
730 : const unsigned long);
731 : #define sets_get_factored_sorted __ECM(sets_get_factored_sorted)
732 : sets_long_t * sets_get_factored_sorted (const unsigned long);
733 :
734 : /* Return the size in bytes of a set of cardinality c */
735 : #define set_sizeof __ECM(set_sizeof)
736 : ATTRIBUTE_UNUSED
737 : static size_t
738 9423 : set_sizeof (const unsigned long c)
739 : {
740 9423 : return sizeof (long) + (size_t) c * sizeof (unsigned long);
741 : }
742 :
743 :
744 : /* Return pointer to the next set in "*sets" */
745 : ATTRIBUTE_UNUSED
746 : static set_long_t *
747 53081 : sets_nextset (const set_long_t *sets)
748 : {
749 106162 : return (set_long_t *) ((char *)sets + sizeof(unsigned long) +
750 53081 : sets->card * sizeof(long));
751 : }
752 :
753 :
754 : #if defined (__cplusplus)
755 : }
756 : #endif
757 :
758 : /* a <- b * c where a and b are mpz, c is a double, and t an auxiliary mpz */
759 : /* Not sure how the preprocessor handles shifts by more than the integer
760 : width on 32 bit machines, so do the shift by 53 in two pieces */
761 : #if (((ULONG_MAX >> 27) >> 26) >= 1)
762 : #define mpz_mul_d(a, b, c, t) \
763 : mpz_mul_ui (a, b, (unsigned long int) c);
764 : #else
765 : #define mpz_mul_d(a, b, c, t) \
766 : if (c < (double) ULONG_MAX) \
767 : mpz_mul_ui (a, b, (unsigned long int) c); \
768 : else { \
769 : mpz_set_d (t, c); \
770 : mpz_mul (a, b, t); }
771 : #endif
772 :
773 : #endif /* _ECM_IMPL_H */
|
