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 *, 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 /* auxlib.c */
618 #define mpz_add_si __ECM(mpz_add_si)
619 void mpz_add_si (mpz_t, mpz_t, long);
620 #define mpz_sub_si __ECM(mpz_sub_si)
621 void mpz_sub_si (mpz_t, mpz_t, long);
622 #define mpz_divby3_1op __ECM(mpz_divby3_1op)
623 void mpz_divby3_1op (mpz_t);
624 #define double_to_size __ECM(double_to_size)
625 size_t double_to_size (double d);
626 #define cputime __ECM(cputime)
627 long cputime (void);
628 #define realtime __ECM(realtime)
629 long realtime (void);
630 #define elltime __ECM(elltime)
631 long elltime (long, long);
632 #define test_verbose __ECM(test_verbose)
633 int test_verbose (int);
634 #define set_verbose __ECM(set_verbose)
635 void set_verbose (int);
636 #define outputf __ECM(outputf)
637 int outputf (int, const char *, ...);
638 #define writechkfile __ECM(writechkfile)
639 void writechkfile (char *, int, double, mpmod_t, mpres_t, mpres_t, mpres_t, mpres_t);
640 #define aux_fseek64 __ECM(aux_fseek64)
641 int aux_fseek64(FILE *, const int64_t, const int);
642
643 /* auxarith.c */
644 #define gcd __ECM(gcd)
645 unsigned long gcd (unsigned long, unsigned long);
646 #define eulerphi __ECM(eulerphi)
647 unsigned long eulerphi (unsigned long);
648 #define ceil_log2 __ECM(ceil_log2)
649 unsigned int ceil_log2 (unsigned long);
650 #define find_factor __ECM(find_factor)
651 unsigned long find_factor (const unsigned long);
652
653 /* random.c */
654 #define init_randstate __ECM(init_randstate)
655 void init_randstate (gmp_randstate_t);
656 #define pp1_random_seed __ECM(pp1_random_seed)
657 void pp1_random_seed (mpz_t, mpz_t, gmp_randstate_t);
658 #define pm1_random_seed __ECM(pm1_random_seed)
659 void pm1_random_seed (mpz_t, mpz_t, gmp_randstate_t);
660 #define get_random_ul __ECM(get_random_ul)
661 unsigned long get_random_ul (void);
662
663 /* Fgw.c */
664 #ifdef HAVE_GWNUM
665 int gw_ecm_stage1 (mpz_t, curve *, mpmod_t, double, double *, mpz_t,
666 double, unsigned long, unsigned long, signed long);
667 #endif
668
669 /* batch.c */
670 #define compute_s __ECM(compute_s )
671 void compute_s (mpz_t, ecm_uint, int *);
672 #define ecm_stage1_batch __ECM(ecm_stage1_batch)
673 int ecm_stage1_batch (mpz_t, mpres_t, mpres_t, mpmod_t, double, double *,
674 int, mpz_t);
675
676 /* parametrizations.c */
677 #define get_curve_from_random_parameter __ECM(get_curve_from_random_parameter)
678 int get_curve_from_random_parameter (mpz_t, mpres_t, mpres_t, mpz_t, int,
679 mpmod_t, gmp_randstate_t);
680 #define get_curve_from_param0 __ECM(get_curve_from_param0)
681 int get_curve_from_param0 (mpz_t, mpres_t, mpres_t, mpz_t, mpmod_t);
682 #define get_curve_from_param1 __ECM(get_curve_from_param1)
683 int get_curve_from_param1 (mpres_t, mpres_t, mpz_t, mpmod_t);
684 #define get_curve_from_param2 __ECM(get_curve_from_param2)
685 int get_curve_from_param2 (mpz_t, mpres_t, mpres_t, mpz_t, mpmod_t);
686 #define get_curve_from_param3 __ECM(get_curve_from_param3)
687 int get_curve_from_param3 (mpres_t, mpres_t, mpz_t, mpmod_t);
688 #define get_default_param __ECM(get_default_param)
689 int get_default_param (int, double, int);
690
691 /* sets_long.c */
692 /* A set of long ints */
693 typedef struct {
694 unsigned long card;
695 long elem[1];
696 } set_long_t;
697
698 /* A set of sets of long ints */
699 typedef struct {
700 unsigned long nr;
701 set_long_t sets[1];
702 } sets_long_t;
703
704 #define quicksort_long __ECM(quicksort_long)
705 void quicksort_long (long *, unsigned long);
706 #define sets_print __ECM(sets_print)
707 void sets_print (const int, sets_long_t *);
708 #define sets_max __ECM(sets_max)
709 void sets_max (mpz_t, const unsigned long);
710 #define sets_sumset __ECM(sets_sumset)
711 void sets_sumset (set_long_t *, const sets_long_t *);
712 #define sets_sumset_minmax __ECM(sets_sumset_minmax)
713 void sets_sumset_minmax (mpz_t, const sets_long_t *, const int);
714 #define sets_extract __ECM(sets_extract)
715 void sets_extract (sets_long_t *, size_t *, sets_long_t *,
716 const unsigned long);
717 #define sets_get_factored_sorted __ECM(sets_get_factored_sorted)
718 sets_long_t * sets_get_factored_sorted (const unsigned long);
719
720 /* Return the size in bytes of a set of cardinality c */
721 #define set_sizeof __ECM(set_sizeof)
722 ATTRIBUTE_UNUSED
723 static size_t
set_sizeof(const unsigned long c)724 set_sizeof (const unsigned long c)
725 {
726 return sizeof (long) + (size_t) c * sizeof (unsigned long);
727 }
728
729
730 /* Return pointer to the next set in "*sets" */
731 ATTRIBUTE_UNUSED
732 static set_long_t *
sets_nextset(const set_long_t * sets)733 sets_nextset (const set_long_t *sets)
734 {
735 return (set_long_t *) ((char *)sets + sizeof(unsigned long) +
736 sets->card * sizeof(long));
737 }
738
739
740 #if defined (__cplusplus)
741 }
742 #endif
743
744 /* a <- b * c where a and b are mpz, c is a double, and t an auxiliary mpz */
745 /* Not sure how the preprocessor handles shifts by more than the integer
746 width on 32 bit machines, so do the shift by 53 in two pieces */
747 #if (((ULONG_MAX >> 27) >> 26) >= 1)
748 #define mpz_mul_d(a, b, c, t) \
749 mpz_mul_ui (a, b, (unsigned long int) c);
750 #else
751 #define mpz_mul_d(a, b, c, t) \
752 if (c < (double) ULONG_MAX) \
753 mpz_mul_ui (a, b, (unsigned long int) c); \
754 else { \
755 mpz_set_d (t, c); \
756 mpz_mul (a, b, t); }
757 #endif
758
759 #endif /* _ECM_IMPL_H */
760