diff options
Diffstat (limited to 'coqprime/gencertif/ecm-impl.h')
| -rw-r--r-- | coqprime/gencertif/ecm-impl.h | 554 |
1 files changed, 554 insertions, 0 deletions
diff --git a/coqprime/gencertif/ecm-impl.h b/coqprime/gencertif/ecm-impl.h new file mode 100644 index 000000000..392a42fb1 --- /dev/null +++ b/coqprime/gencertif/ecm-impl.h @@ -0,0 +1,554 @@ +/* ecm-impl.h - header file for libecm + + Copyright 2001, 2002, 2003, 2004, 2005 Paul Zimmermann and Alexander Kruppa. + + This program is free software; you can redistribute it and/or modify it + under the terms of the GNU General Public License as published by the + Free Software Foundation; either version 2 of the License, or (at your + option) any later version. + + This program is distributed in the hope that it will be useful, but WITHOUT + ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for + more details. + + You should have received a copy of the GNU General Public License along + with this program; see the file COPYING. If not, write to the Free + Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA + 02111-1307, USA. +*/ + +#if defined (__STDC__) \ + || defined (__cplusplus) \ + || defined (_AIX) \ + || defined (__DECC) \ + || (defined (__mips) && defined (_SYSTYPE_SVR4)) \ + || defined (_MSC_VER) \ + || defined (_WIN32) +#define __ECM_HAVE_TOKEN_PASTE 1 +#else +#define __ECM_HAVE_TOKEN_PASTE 0 +#endif + +#ifndef __ECM +#if __ECM_HAVE_TOKEN_PASTE +#define __ECM(x) __ecm_##x +#else +#define __ECM(x) __ecm_/**/x +#endif +#endif + +#define ECM_STDOUT __ecm_stdout +#define ECM_STDERR __ecm_stderr +extern FILE *ECM_STDOUT, *ECM_STDERR; + +/* Warnings about unused parameters by gcc can be suppressed by prefixing + parameter with ATTRIBUTE_UNUSED when parameter can't be removed, i.e. + for interface consistency reasons */ +#ifdef __GNUC__ +#define ATTRIBUTE_UNUSED __attribute__ ((unused)) +#define ATTRIBUTE_CONST __attribute__ ((const)) +#else +#define ATTRIBUTE_UNUSED +#define ATTRIBUTE_CONST +#endif + +#ifdef __GNUC__ +#define INLINE inline +#else +#define INLINE +#endif + +/* if POLYEVALTELLEGEN is defined, use polyeval_tellegen(), + otherwise use polyeval() */ +#define POLYEVALTELLEGEN + +/* use Kronecker-Scho"nhage's multiplication */ +#define KS_MULTIPLY + +/* define top-level multiplication */ +#define KARA 2 +#define TOOM3 3 +#define TOOM4 4 +#define KS 5 + +/* compile with -DMULT=2 to override default */ +#ifndef MULT +#ifdef KS_MULTIPLY +#define MULT KS +#else +#define MULT TOOM4 +#endif +#endif + +#ifdef POLYEVALTELLEGEN +#define USE_SHORT_PRODUCT +#endif + +/* Use George Woltman's GWNUM library */ +/* Should be defined via -DHAVE_GWNUM by Makefile +#define HAVE_GWNUM +*/ + +#ifdef HAVE_GWNUM +/* Only Fermat numbers with exponent >= GWTHRESHOLD are multiplied with + Woltman's DWT */ +#define GWTHRESHOLD 1024 +#endif + +#if WANT_ASSERT +#include <assert.h> +#define ASSERT(expr) assert (expr) +#else +#define ASSERT(expr) do {} while (0) +#endif + +/* thresholds */ +#ifndef MUL_KARATSUBA_THRESHOLD +#define MUL_KARATSUBA_THRESHOLD 32 +#endif + +#ifndef DIV_DC_THRESHOLD +#define DIV_DC_THRESHOLD (3 * MUL_KARATSUBA_THRESHOLD) +#endif + +#define MPZMOD_THRESHOLD_DEFAULT (3 * DIV_DC_THRESHOLD / 2) +#define REDC_THRESHOLD_DEFAULT (2 * DIV_DC_THRESHOLD) + +/* base2mod is used when size(2^n+/-1) <= BASE2_THRESHOLD * size(cofactor) */ +#define BASE2_THRESHOLD 1.4 + +/* default number of probable prime tests */ +#define PROBAB_PRIME_TESTS 1 + +/* kronecker_schonhage() is used instead of toomcook4() + when bitsize(poly) >= KS_MUL_THRESHOLD */ +#define KS_MUL_THRESHOLD 1e6 +/* same for median product */ +#define KS_TMUL_THRESHOLD 8e5 + +#define ABS(x) ((x) >= 0 ? (x) : -(x)) + +/* getprime */ +#define WANT_FREE_PRIME_TABLE(p) (p < 0.0) +#define FREE_PRIME_TABLE -1.0 + +#define MOD_PLAIN 0 +#define MOD_BASE2 1 +#define MOD_MODMULN 2 +#define MOD_REDC 3 + +/* Various logging levels */ +/* OUTPUT_ALWAYS means print always, regardless of verbose value */ +#define OUTPUT_ALWAYS 0 +/* OUTPUT_NORMAL means print during normal program execution */ +#define OUTPUT_NORMAL 1 +/* OUTPUT_VERBOSE means print if the user requested more verbosity */ +#define OUTPUT_VERBOSE 2 +/* OUTPUT_RESVERBOSE is for printing residues (after stage 1 etc) */ +#define OUTPUT_RESVERBOSE 3 +/* OUTPUT_DEVVERBOSE is for printing internal parameters (for developers) */ +#define OUTPUT_DEVVERBOSE 4 +/* OUTPUT_TRACE is for printing trace data, produces lots of output */ +#define OUTPUT_TRACE 5 +/* OUTPUT_ERROR is for printing error messages */ +#define OUTPUT_ERROR -1 + +typedef mpz_t mpres_t; + +typedef mpz_t* listz_t; + +typedef struct +{ + mpres_t x; + mpres_t y; +} __point_struct; +typedef __point_struct point; + +typedef struct +{ + mpres_t x; + mpres_t y; + mpres_t A; +} __curve_struct; +typedef __curve_struct curve; + +typedef struct +{ + unsigned int size_fd; /* How many entries .fd has, always nr * (S+1) */ + unsigned int nr; /* How many separate progressions there are */ + unsigned int next; /* From which progression to take the next root */ + unsigned int S; /* Degree of the polynomials */ + unsigned int dsieve; /* Values not coprime to dsieve are skipped */ + unsigned int rsieve; /* Which residue mod dsieve current .next belongs to */ + int dickson_a; /* Parameter for Dickson polynomials */ + point *fd; + mpres_t *T; /* For temp values. FIXME: should go! */ + curve *X; /* The curve the points are on */ +} __ecm_roots_state; +typedef __ecm_roots_state ecm_roots_state; + +/* WARNING: it is important that the order of fields matches that + of ecm_roots_state. See comment in pm1.c:pm1_rootsF. */ +typedef struct +{ + unsigned int size_fd; /* How many entries .fd has, always nr * (S+1) */ + unsigned int nr; /* How many separate progressions there are */ + unsigned int next; /* From which progression to take the next root */ + unsigned int S; /* Degree of the polynomials */ + unsigned int dsieve; /* Values not coprime to dsieve are skipped */ + unsigned int rsieve; /* Which residue mod dsieve current .next belongs to */ + int dickson_a; /* Parameter for Dickson polynomials */ + mpres_t *fd; + int invtrick; +} __pm1_roots_state; +typedef __pm1_roots_state pm1_roots_state; + +typedef struct +{ + unsigned int size_fd; /* How many entries .fd has, always nr * (S+1) */ + unsigned int nr; /* How many separate progressions there are */ + unsigned int next; /* From which progression to take the next root */ + unsigned int S; /* Degree of the polynomials */ + unsigned int dsieve; /* Values not coprime to dsieve are skipped */ + unsigned int rsieve; /* Which residue mod dsieve current .next belongs to */ + point *fd; /* for S != 1 */ + mpres_t tmp[4]; /* for S=1 */ + unsigned int d; /* Step size for computing roots of G */ +} __pp1_roots_state; +typedef __pp1_roots_state pp1_roots_state; + +typedef struct +{ + int alloc; + int degree; + listz_t coeff; +} __polyz_struct; +typedef __polyz_struct polyz_t[1]; + +typedef struct +{ + int repr; /* 0: plain modulus, possibly normalized + 1: base 2 number + 2: MODMULN + 3: REDC representation */ + int bits; /* in case of a base 2 number, 2^k[+-]1, bits = [+-]k + in case of MODMULN or REDC representation, nr. of + bits b so that 2^b > orig_modulus and + mp_bits_per_limb | b */ + int Fermat; /* If repr = 1 (base 2 number): If modulus is 2^(2^m)+1, + i.e. bits = 2^m, then Fermat = 2^m, 0 otherwise. + If repr != 1, undefined */ + mp_limb_t Nprim; /* For MODMULN */ + mpz_t orig_modulus; /* The original modulus */ + mpz_t aux_modulus; /* The auxiliary modulus value (i.e. normalized + modulus, or -1/N (mod 2^bits) for REDC */ + mpz_t multiple; /* The smallest multiple of N that is larger or + equal to 2^bits for REDC/MODMULN */ + mpz_t R2, R3; /* For MODMULN and REDC, R^2 and R^3 (mod orig_modulus), + where R = 2^bits. */ + mpz_t temp1, temp2; /* Temp values used during multiplication etc. */ +} __mpmod_struct; +typedef __mpmod_struct mpmod_t[1]; + +#if defined (__cplusplus) +extern "C" { +#endif + +/* getprime.c */ +#define getprime __ECM(getprime) +double getprime (double); + +/* pm1.c */ +#define pm1_rootsF __ECM(pm1_rootsF) +int pm1_rootsF (mpz_t, listz_t, unsigned int, unsigned int, + unsigned int, mpres_t *, listz_t, int, mpmod_t); +#define pm1_rootsG_init __ECM(pm1_rootsG_init) +pm1_roots_state* pm1_rootsG_init (mpres_t *, mpz_t, unsigned int, + unsigned int, int, mpmod_t); +#define pm1_rootsG __ECM(pm1_rootsG) +int pm1_rootsG (mpz_t, listz_t, unsigned int, pm1_roots_state *, + listz_t, mpmod_t); +#define pm1_rootsG_clear __ECM(pm1_rootsG_clear) +void pm1_rootsG_clear (pm1_roots_state *, mpmod_t); + +/* bestd.c */ +#define phi __ECM(phi) +unsigned long phi (unsigned long); +#define bestD __ECM(bestD) +int bestD (mpz_t, mpz_t, int, unsigned int *, unsigned int *, + unsigned int *, unsigned int *, mpz_t); + +/* ecm.c */ +#define choose_S __ECM(choose_S) +int choose_S (mpz_t); + +/* ecm2.c */ +#define ecm_rootsF __ECM(ecm_rootsF) +int ecm_rootsF (mpz_t, listz_t, unsigned int, unsigned int, + unsigned int, curve *, int, mpmod_t); +#define ecm_rootsG_init __ECM(ecm_rootsG_init) +ecm_roots_state* ecm_rootsG_init (mpz_t, curve *, mpz_t, unsigned int, + unsigned int, unsigned int, unsigned int, int, mpmod_t); +#define ecm_rootsG __ECM(ecm_rootsG) +int ecm_rootsG (mpz_t, listz_t, unsigned int, ecm_roots_state *, + mpmod_t); +#define ecm_rootsG_clear __ECM(ecm_rootsG_clear) +void ecm_rootsG_clear (ecm_roots_state *, int, mpmod_t); +void init_roots_state (ecm_roots_state *, int, unsigned int, unsigned int, + double); + +/* lucas.c */ +#define pp1_mul_prac __ECM(pp1_mul_prac) +void pp1_mul_prac (mpres_t, unsigned long, mpmod_t, mpres_t, mpres_t, + mpres_t, mpres_t, mpres_t); + +/* pp1.c */ +#define pp1_rootsF __ECM(pp1_rootsF) +int pp1_rootsF (listz_t, unsigned int, unsigned int, unsigned int, + mpres_t *, listz_t, int, mpmod_t); +#define pp1_rootsG __ECM(pp1_rootsG) +int pp1_rootsG (listz_t, unsigned int, pp1_roots_state *, mpmod_t, mpres_t*); +#define pp1_rootsG_init __ECM(pp1_rootsG_init) +pp1_roots_state* pp1_rootsG_init (mpres_t*, mpz_t, unsigned int, + unsigned int, int, mpmod_t); +#define pp1_rootsG_clear __ECM(pp1_rootsG_clear) +void pp1_rootsG_clear (pp1_roots_state *, mpmod_t); + +/* stage2.c */ +#define stage2 __ECM(stage2) +int stage2 (mpz_t, void *, mpmod_t, mpz_t, mpz_t, unsigned int, + int, int, int, char *); +#define init_progression_coeffs __ECM(init_progression_coeffs) +listz_t init_progression_coeffs (mpz_t, unsigned int, unsigned int, + unsigned int, unsigned int, unsigned int, int); + +/* listz.c */ +#define list_mul_mem __ECM(list_mul_mem) +int list_mul_mem (unsigned int); +#define init_list __ECM(init_list) +listz_t init_list (unsigned int); +#define clear_list __ECM(clear_list) +void clear_list (listz_t, unsigned int); +#define list_inp_raw __ECM(list_inp_raw) +int list_inp_raw (listz_t, FILE *, unsigned int); +#define list_out_raw __ECM(list_out_raw) +int list_out_raw (FILE *, listz_t, unsigned int); +#define print_list __ECM(print_list) +void print_list (listz_t, unsigned int); +#define list_set __ECM(list_set) +void list_set (listz_t, listz_t, unsigned int); +#define list_revert __ECM(list_revert) +void list_revert (listz_t, unsigned int); +#define list_swap __ECM(list_swap) +void list_swap (listz_t, listz_t, unsigned int); +#define list_mod __ECM(list_mod) +void list_mod (listz_t, listz_t, unsigned int, mpz_t); +#define list_add __ECM(list_add) +void list_add (listz_t, listz_t, listz_t, unsigned int); +#define list_sub __ECM(list_sub) +void list_sub (listz_t, listz_t, listz_t, unsigned int); +#define list_mul_z __ECM(list_mul_z) +void list_mul_z (listz_t, listz_t, mpz_t, unsigned int, mpz_t); +#define list_gcd __ECM(list_gcd) +int list_gcd (mpz_t, listz_t, unsigned int, mpz_t); +#define list_zero __ECM(list_zero) +void list_zero (listz_t, unsigned int); +#define list_mul_high __ECM(list_mul_high) +void list_mul_high (listz_t, listz_t, listz_t, unsigned int, listz_t); +#define karatsuba __ECM(karatsuba) +void karatsuba (listz_t, listz_t, listz_t, unsigned int, listz_t); +#define list_mulmod __ECM(list_mulmod) +void list_mulmod (listz_t, listz_t, listz_t, listz_t, unsigned int, + listz_t, mpz_t); +#define list_invert __ECM(list_invert) +int list_invert (listz_t, listz_t, unsigned int, mpz_t, mpmod_t); +#define PolyFromRoots __ECM(PolyFromRoots) +void PolyFromRoots (listz_t, listz_t, unsigned int, listz_t, mpz_t); +#define PolyFromRoots_Tree __ECM(PolyFromRoots_Tree) +int PolyFromRoots_Tree (listz_t, listz_t, unsigned int, listz_t, int, + mpz_t, listz_t*, FILE*, unsigned int); +#define PrerevertDivision __ECM(PrerevertDivision) +int PrerevertDivision (listz_t, listz_t, listz_t, unsigned int, listz_t, + mpz_t); +#define PolyInvert __ECM(PolyInvert) +void PolyInvert (listz_t, listz_t, unsigned int, listz_t, mpz_t); +#define RecursiveDivision __ECM(RecursiveDivision) +void RecursiveDivision (listz_t, listz_t, listz_t, unsigned int, + listz_t, mpz_t, int); + +/* polyeval.c */ +#define polyeval __ECM(polyeval) +void polyeval (listz_t, unsigned int, listz_t*, listz_t, mpz_t, unsigned int); +#define polyeval_tellegen __ECM(polyeval_tellegen) +int polyeval_tellegen (listz_t, unsigned int, listz_t*, listz_t, + unsigned int, listz_t, mpz_t, char *); + +/* toomcook.c */ +#define toomcook3 __ECM(toomcook3) +void toomcook3 (listz_t, listz_t, listz_t, unsigned int, listz_t); +#define toomcook4 __ECM(toomcook4) +void toomcook4 (listz_t, listz_t, listz_t, unsigned int, listz_t); + +/* ks-multiply.c */ +#define kronecker_schonhage __ECM(kronecker_schonhage) +int kronecker_schonhage (listz_t, listz_t, listz_t, unsigned int, listz_t); +#define TMulKS __ECM(TMulKS) +int TMulKS (listz_t, unsigned int, listz_t, unsigned int, listz_t, + unsigned int, mpz_t, int); +#define ks_wrapmul_m __ECM(ks_wrapmul_m) +unsigned int ks_wrapmul_m (unsigned int, unsigned int, mpz_t); +#define ks_wrapmul __ECM(ks_wrapmul) +unsigned int ks_wrapmul (listz_t, unsigned int, listz_t, unsigned int, + listz_t, unsigned int, mpz_t); + +/* mpmod.c */ +#define isbase2 __ECM(isbase2) +int isbase2 (mpz_t, double); +#define mpmod_init __ECM(mpmod_init) +void mpmod_init (mpmod_t, mpz_t, int); +#define mpmod_init_MPZ __ECM(mpmod_init_MPZ) +void mpmod_init_MPZ (mpmod_t, mpz_t); +#define mpmod_init_BASE2 __ECM(mpmod_init_BASE2) +int mpmod_init_BASE2 (mpmod_t, int, mpz_t); +#define mpmod_init_MODMULN __ECM(mpmod_init_MODMULN) +void mpmod_init_MODMULN (mpmod_t, mpz_t); +#define mpmod_init_REDC __ECM(mpmod_init_REDC) +void mpmod_init_REDC (mpmod_t, mpz_t); +#define mpmod_clear __ECM(mpmod_clear) +void mpmod_clear (mpmod_t); +#define mpres_pow __ECM(mpres_pow) +void mpres_pow (mpres_t, mpres_t, mpres_t, mpmod_t); +#define mpres_ui_pow __ECM(mpres_ui_pow) +void mpres_ui_pow (mpres_t, unsigned int, mpres_t, mpmod_t); +#define mpres_mul __ECM(mpres_mul) +void mpres_mul (mpres_t, mpres_t, mpres_t, mpmod_t); +#define mpres_div_2exp __ECM(mpres_div_2exp) +void mpres_div_2exp (mpres_t, mpres_t, unsigned int, mpmod_t); +#define mpres_add_ui __ECM(mpres_add_ui) +void mpres_add_ui (mpres_t, mpres_t, unsigned int, mpmod_t); +#define mpres_add __ECM(mpres_add) +void mpres_add (mpres_t, mpres_t, mpres_t, mpmod_t); +#define mpres_sub_ui __ECM(mpres_sub_ui) +void mpres_sub_ui (mpres_t, mpres_t, unsigned int, mpmod_t); +#define mpres_sub __ECM(mpres_sub) +void mpres_sub (mpres_t, mpres_t, mpres_t, mpmod_t); +#define mpres_set_z __ECM(mpres_set_z) +void mpres_set_z (mpres_t, mpz_t, mpmod_t); +#define mpres_get_z __ECM(mpres_get_z) +void mpres_get_z (mpz_t, mpres_t, mpmod_t); +#define mpres_set_ui __ECM(mpres_set_ui) +void mpres_set_ui (mpres_t, unsigned int, mpmod_t); +#define mpres_init __ECM(mpres_init) +void mpres_init (mpres_t, mpmod_t); +#define mpres_realloc __ECM(mpres_realloc) +void mpres_realloc (mpres_t, mpmod_t); +#define mpres_mul_ui __ECM(mpres_mul_ui) +void mpres_mul_ui (mpres_t, mpres_t, unsigned int, mpmod_t); +#define mpres_neg __ECM(mpres_neg) +void mpres_neg (mpres_t, mpres_t, mpmod_t); +#define mpres_invert __ECM(mpres_invert) +int mpres_invert (mpres_t, mpres_t, mpmod_t); +#define mpres_gcd __ECM(mpres_gcd) +void mpres_gcd (mpz_t, mpres_t, mpmod_t); +#define mpres_out_str __ECM(mpres_out_str) +void mpres_out_str (FILE *, unsigned int, mpres_t, mpmod_t); +#define mpres_is_zero __ECM(mpres_is_zero) +int mpres_is_zero (mpres_t, mpmod_t); +#define mpres_clear(a,n) mpz_clear (a) +#define mpres_set(a,b,n) mpz_set (a, b) +#define mpres_swap(a,b,n) mpz_swap (a, b) + +/* mul_lo.c */ +#define ecm_mul_lo_n __ECM(ecm_mul_lo_n) +void ecm_mul_lo_n (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t); + +/* median.c */ +#define TMulGen __ECM(TMulGen) +unsigned int +TMulGen (listz_t, unsigned int, listz_t, unsigned int, listz_t, + unsigned int, listz_t, mpz_t); +#define TMulGen_space __ECM(TMulGen_space) +unsigned int TMulGen_space (unsigned int, unsigned int, unsigned int); + +/* schoen_strass.c */ +#define DEFAULT 0 +#define MONIC 1 +#define NOPAD 2 +#define F_mul __ECM(F_mul) +unsigned int F_mul (mpz_t *, mpz_t *, mpz_t *, unsigned int, int, + unsigned int, mpz_t *); +#define F_mul_trans __ECM(F_mul_trans) +unsigned int F_mul_trans (mpz_t *, mpz_t *, mpz_t *, unsigned int, + unsigned int, mpz_t *); + +/* rho.c */ +#define rhoinit __ECM(rhoinit) +void rhoinit (int, int); +#define ecmprob __ECM(ecmprob) +double ecmprob (double, double, double, double, int); + +/* auxlib.c */ +#define gcd __ECM(gcd) +unsigned int gcd (unsigned int, unsigned int); +#define mpz_sub_si __ECM(mpz_sub_si) +void mpz_sub_si (mpz_t, mpz_t, int); +#define mpz_divby3_1op __ECM(mpz_divby3_1op) +void mpz_divby3_1op (mpz_t); +#define ceil_log2 __ECM(ceil_log2) +unsigned int ceil_log2 (unsigned int); +#define cputime __ECM(cputime) +unsigned int cputime (void); +#define elltime __ECM(elltime) +unsigned int elltime (unsigned int, unsigned int); +#define test_verbose __ECM(test_verbose) +int test_verbose (int); +#define get_verbose __ECM(get_verbose) +int get_verbose (void); +#define set_verbose __ECM(set_verbose) +void set_verbose (int); +#define inc_verbose __ECM(inc_verbose) +int inc_verbose (void); +#define outputf __ECM(outputf) +int outputf (int, char *, ...); + +/* random.c */ +#define pp1_random_seed __ECM(pp1_random_seed) +void pp1_random_seed (mpz_t, mpz_t, gmp_randstate_t); +#define pm1_random_seed __ECM(pm1_random_seed) +void pm1_random_seed (mpz_t, mpz_t, gmp_randstate_t); +#define get_random_ui __ECM(get_random_ui) +unsigned int get_random_ui (void); + +/* Fgw.c */ +#ifdef HAVE_GWNUM +void Fgwinit (int); +void Fgwclear (void); +void Fgwmul (mpz_t, mpz_t, mpz_t); +#endif + + +#if defined (__cplusplus) +} +#endif + +#define TWO53 9007199254740992.0 /* 2^53 */ + +/* a <- b * c where a and b are mpz, c is a double, and t an auxiliary mpz */ +#if (BITS_PER_MP_LIMB >= 53) +#define mpz_mul_d(a, b, c, t) \ + mpz_mul_ui (a, b, (unsigned long int) c); +#else +#if (BITS_PER_MP_LIMB >= 32) +#define mpz_mul_d(a, b, c, t) \ + if (c < 4294967296.0) \ + mpz_mul_ui (a, b, (unsigned long int) c); \ + else { \ + mpz_set_d (t, c); \ + mpz_mul (a, b, t); } +#else +#define mpz_mul_d(a, b, c, t) \ + mpz_set_d (t, c); \ + mpz_mul (a, b, t); +#endif +#endif |