include/flint/ulong_extras.h

0001 /*
0002     Copyright (C) 2006, 2007, 2008, 2009, 2016 William Hart
0003     Copyright (C) 2008 Peter Shrimpton
0004     Copyright (C) 2009 Tom Boothby
0005     Copyright (C) 2010 Fredrik Johansson
0006     Copyright (C) 2023 Albin Ahlbäck
0007
0008     This file is part of FLINT.
0009
0010     FLINT is free software: you can redistribute it and/or modify it under
0011     the terms of the GNU Lesser General Public License (LGPL) as published
0012     by the Free Software Foundation; either version 3 of the License, or
0013     (at your option) any later version.  See <https://www.gnu.org/licenses/>.
0014 */
0015
0016 #ifndef ULONG_EXTRAS_H
0017 #define ULONG_EXTRAS_H
0018
0019 #ifdef ULONG_EXTRAS_INLINES_C
0020 #define ULONG_EXTRAS_INLINE
0021 #else
0022 #define ULONG_EXTRAS_INLINE static inline
0023 #endif
0024
0025 #include "limb_types.h"
0026 #include "longlong.h"
0027
0028 #ifdef __cplusplus
0029 extern "C" {
0030 #endif
0031
0032 /* Randomisation *************************************************************/
0033
0034 ulong n_randlimb(flint_rand_t state);
0035 ulong n_urandint(flint_rand_t state, ulong limit);
0036 ulong n_randbits(flint_rand_t state, unsigned int bits);
0037 ulong n_randprime(flint_rand_t state, ulong bits, int proved);
0038
0039 ulong n_randtest_bits(flint_rand_t state, int bits);
0040 ulong n_randtest(flint_rand_t state);
0041 ulong n_randtest_not_zero(flint_rand_t state);
0042 ulong n_randtest_prime(flint_rand_t state, int proved);
0043
0044 ULONG_EXTRAS_INLINE ulong n_mulhi(ulong a, ulong b)
0045 {
0046 /* Experimental: see if the compiler generates better code than inline assembly */
0047 #if FLINT_BITS == 64 && defined(__GNUC__)
0048     return ((__uint128_t) a * (__uint128_t) b) >> 64;
0049 #else
0050     ulong hi, lo;
0051     umul_ppmm(hi, lo, a, b);
0052     return hi;
0053 #endif
0054 }
0055
0056 #if FLINT64
0057 ULONG_EXTRAS_INLINE ulong _n_randlimb(flint_rand_t state)
0058 {
0059     state->__randval = (state->__randval*UWORD(13282407956253574709) + UWORD(286824421));
0060     state->__randval2 = (state->__randval2*UWORD(7557322358563246341) + UWORD(286824421));
0061
0062     return (state->__randval>>32) + ((state->__randval2>>32) << 32);
0063 }
0064 #else
0065 ULONG_EXTRAS_INLINE ulong _n_randlimb(flint_rand_t state)
0066 {
0067     state->__randval = (state->__randval*UWORD(1543932465) +  UWORD(1626832771));
0068     state->__randval2 = (state->__randval2*UWORD(2495927737) +  UWORD(1626832771));
0069
0070     return (state->__randval>>16) + ((state->__randval2>>16) << 16);
0071 }
0072 #endif
0073
0074 ULONG_EXTRAS_INLINE ulong _n_randint(flint_rand_t state, ulong limit)
0075 {
0076     if ((limit & (limit - 1)) == 0)
0077         return _n_randlimb(state) & (limit - 1);
0078     else
0079         return n_mulhi(_n_randlimb(state), limit);
0080 }
0081
0082 /* Basic arithmetic **********************************************************/
0083
0084 ulong n_revbin(ulong in, ulong bits);
0085
0086 int n_divides(ulong * q, ulong n, ulong p);
0087
0088 /* Check d | n for odd d using Granlund-Montgomery, given
0089    inv1 = 1/d mod 2^FLINT_BITS, inv2 = floor(UWORD_MAX / d) */
0090 ULONG_EXTRAS_INLINE int n_divisible_odd_gm(ulong n, ulong inv1, ulong inv2)
0091 {
0092     return n * inv1 <= inv2;
0093 }
0094
0095 ulong n_divrem2_precomp(ulong * q, ulong a, ulong n, double npre);
0096 ulong n_divrem2_preinv(ulong * q, ulong a, ulong n, ulong ninv);
0097 ulong n_div2_preinv(ulong a, ulong n, ulong ninv);
0098
0099 /*
0100    Method of Niels Moller and Torbjorn Granlund see paper:
0101    Improved Division by Invariant Integers: (algorithm 4)
0102    https://gmplib.org/~tege/division-paper.pdf
0103 */
0104 ULONG_EXTRAS_INLINE ulong
0105 n_divrem_preinv(ulong * q, ulong a, ulong n, ulong ninv, unsigned int norm)
0106 {
0107     ulong q1, q0, r;
0108     n <<= norm;
0109     const ulong u1 = (norm == 0) ? 0 : a >> (FLINT_BITS - norm);
0110     const ulong u0 = (a << norm);
0111     umul_ppmm(q1, q0, ninv, u1);
0112     add_ssaaaa(q1, q0, q1, q0, u1, u0);
0113     (*q) = q1 + 1;
0114     r = u0 - (*q) * n;
0115     if (r > q0)
0116     {
0117         r += n;
0118         (*q)--;
0119     }
0120     if (r >= n)
0121     {
0122         (*q)++;
0123         r -= n;
0124     }
0125     return r >> norm;
0126 }
0127
0128 ULONG_EXTRAS_INLINE ulong
0129 n_divrem_preinv_unnorm(ulong * q, ulong a, ulong n, ulong ninv, unsigned int norm)
0130 {
0131     ulong q1, q0, r;
0132     FLINT_ASSERT(norm >= 1);
0133     n <<= norm;
0134     const ulong u1 = a >> (FLINT_BITS - norm);
0135     const ulong u0 = (a << norm);
0136     umul_ppmm(q1, q0, ninv, u1);
0137     add_ssaaaa(q1, q0, q1, q0, u1, u0);
0138     (*q) = q1 + 1;
0139     r = u0 - (*q) * n;
0140     if (r > q0)
0141     {
0142         r += n;
0143         (*q)--;
0144     }
0145     if (r >= n)
0146     {
0147         (*q)++;
0148         r -= n;
0149     }
0150     return r >> norm;
0151 }
0152
0153 ULONG_EXTRAS_INLINE ulong
0154 n_divrem_norm(ulong * q, ulong a, ulong n)
0155 {
0156     ulong q0 = (a >= n);
0157     *q = q0;
0158     return a - (n & (-q0));
0159 }
0160
0161 ulong n_factorial_mod2_preinv(ulong n, ulong p, ulong pinv);
0162 ulong n_factorial_fast_mod2_preinv(ulong n, ulong p, ulong pinv);
0163
0164 ulong n_sqrt(ulong a);
0165 ulong n_sqrtrem(ulong * r, ulong a);
0166 int n_is_square(ulong x);
0167 int n_is_squarefree(ulong n);
0168
0169 double n_cbrt_estimate(double a);
0170 ulong n_cbrt(ulong a);
0171 ulong n_cbrt_binary_search(ulong x);
0172 ulong n_cbrt_chebyshev_approx(ulong n);
0173 ulong n_cbrtrem(ulong* remainder, ulong n);
0174
0175 ulong n_pow(ulong n, ulong exp);
0176 ulong _n_pow_check(ulong n, ulong exp);
0177 ulong n_root(ulong n, ulong root);
0178 ulong n_rootrem(ulong* remainder, ulong n, ulong root);
0179 int n_is_perfect_power235(ulong n);
0180 int n_is_perfect_power(ulong * root, ulong n);
0181
0182 int n_sizeinbase(ulong n, int base);
0183 slong n_nonzero_sizeinbase10(ulong n);
0184
0185 ulong n_flog(ulong n, ulong b);
0186 ulong n_clog(ulong n, ulong b);
0187 ulong n_clog_2exp(ulong n, ulong b);
0188
0189 #ifndef __GMP_H__
0190 #ifdef _MSC_VER
0191 # define DECLSPEC_IMPORT __declspec(dllimport)
0192 #else
0193 # define DECLSPEC_IMPORT
0194 #endif
0195 DECLSPEC_IMPORT ulong __gmpn_gcd_11(ulong, ulong);
0196 DECLSPEC_IMPORT ulong __gmpn_gcd_1(nn_srcptr, long int, ulong);
0197 #undef DECLSPEC_IMPORT
0198 #endif
0199
0200 ULONG_EXTRAS_INLINE
0201 ulong n_gcd(ulong x, ulong y)
0202 {
0203     if (x != 0 && y != 0)
0204     {
0205 #ifdef FLINT_WANT_GMP_INTERNALS
0206         ulong mx, my, res;
0207         mx = flint_ctz(x);
0208         my = flint_ctz(y);
0209         x >>= mx;
0210         y >>= my;
0211         res = (x != 1 && y != 1) ? __gmpn_gcd_11(x, y) : 1;
0212         res <<= FLINT_MIN(mx, my);
0213         return res;
0214 #else
0215         return __gmpn_gcd_1(&x, 1, y);
0216 #endif
0217     }
0218     else
0219         return x + y;
0220 }
0221
0222 ulong n_xgcd(ulong * a, ulong * b, ulong x, ulong y);
0223 ulong n_gcdinv(ulong * a, ulong x, ulong y);
0224 ulong n_CRT(ulong r1, ulong m1, ulong r2, ulong m2);
0225
0226 /* Checked arithmetic ********************************************************/
0227
0228 ULONG_EXTRAS_INLINE int n_mul_checked(ulong * a, ulong b, ulong c)
0229 {
0230 #if defined(__GNUC__)
0231     return __builtin_mul_overflow(b, c, a);
0232 #else
0233     ulong ahi, alo;
0234     umul_ppmm(ahi, alo, b, c);
0235     *a = alo;
0236     return 0 != ahi;
0237 #endif
0238 }
0239
0240 ULONG_EXTRAS_INLINE int n_add_checked(ulong * a, ulong b, ulong c)
0241 {
0242 #if defined(__GNUC__)
0243     return __builtin_add_overflow(b, c, a);
0244 #else
0245     int of = b + c < b;
0246     *a = b + c;
0247     return of;
0248 #endif
0249 }
0250
0251 ULONG_EXTRAS_INLINE int n_sub_checked(ulong * a, ulong b, ulong c)
0252 {
0253 #if defined(__GNUC__)
0254     return __builtin_sub_overflow(b, c, a);
0255 #else
0256     int of = b < c;
0257     *a = b - c;
0258     return of;
0259 #endif
0260 }
0261
0262 /* Modular arithmetic ********************************************************/
0263
0264 ULONG_EXTRAS_INLINE double n_precompute_inverse(ulong n) { return (double) 1 / (double) n; }
0265
0266 ulong n_preinvert_limb(ulong n);
0267 ulong n_preinvert_limb_prenorm(ulong n);
0268
0269 /* deprecated -- originally defined in longlong.h */
0270 #define invert_limb(dinv, d) do { (dinv) = n_preinvert_limb_prenorm(d); } while (0)
0271
0272 ulong n_mod_precomp(ulong a, ulong n, double ninv);
0273 ulong n_mod2_precomp(ulong a, ulong n, double ninv);
0274 ulong n_mod2_preinv(ulong a, ulong n, ulong ninv);
0275
0276 ulong n_ll_mod_preinv(ulong a_hi, ulong a_lo, ulong n, ulong ninv);
0277 ulong n_lll_mod_preinv(ulong a_hi, ulong a_mi, ulong a_lo, ulong n, ulong ninv);
0278
0279 ulong n_mulmod_precomp(ulong a, ulong b, ulong n, double ninv);
0280 ulong n_mulmod_preinv(ulong a, ulong b, ulong n, ulong ninv, ulong norm);
0281
0282 ULONG_EXTRAS_INLINE
0283 ulong n_mulmod2_preinv(ulong a, ulong b, ulong n, ulong ninv)
0284 {
0285     ulong p1, p2;
0286
0287     FLINT_ASSERT(n != 0);
0288
0289     umul_ppmm(p1, p2, a, b);
0290     return n_ll_mod_preinv(p1, p2, n, ninv);
0291 }
0292
0293 ULONG_EXTRAS_INLINE
0294 ulong n_mulmod2(ulong a, ulong b, ulong n)
0295 {
0296     ulong p1, p2, ninv;
0297
0298     FLINT_ASSERT(n != 0);
0299
0300     ninv = n_preinvert_limb(n);
0301     umul_ppmm(p1, p2, a, b);
0302     return n_ll_mod_preinv(p1, p2, n, ninv);
0303 }
0304
0305 ulong n_powmod_ui_precomp(ulong a, ulong exp, ulong n, double npre);
0306 ulong n_powmod_ui_preinv(ulong a, ulong exp, ulong n, ulong ninv, ulong norm);
0307 ulong n_powmod_precomp(ulong a, slong exp, ulong n, double npre);
0308
0309 ULONG_EXTRAS_INLINE
0310 ulong n_powmod(ulong a, slong exp, ulong n)
0311 {
0312    double npre = n_precompute_inverse(n);
0313
0314    return n_powmod_precomp(a, exp, n, npre);
0315 }
0316
0317 ulong n_powmod2_fmpz_preinv(ulong a, const fmpz_t exp, ulong n, ulong ninv);
0318 ulong n_powmod2_preinv(ulong a, slong exp, ulong n, ulong ninv);
0319 ulong n_powmod2_ui_preinv(ulong a, ulong exp, ulong n, ulong ninv);
0320
0321 ULONG_EXTRAS_INLINE
0322 ulong n_powmod2(ulong a, slong exp, ulong n)
0323 {
0324    ulong ninv;
0325
0326    FLINT_ASSERT(n != 0);
0327
0328    ninv = n_preinvert_limb(n);
0329
0330    return n_powmod2_preinv(a, exp, n, ninv);
0331 }
0332
0333 ULONG_EXTRAS_INLINE
0334 ulong n_addmod(ulong x, ulong y, ulong n)
0335 {
0336     FLINT_ASSERT(x < n);
0337     FLINT_ASSERT(y < n);
0338     FLINT_ASSERT(n != 0);
0339
0340     return (n - y > x ? x + y : x + y - n);
0341 }
0342
0343 ULONG_EXTRAS_INLINE
0344 ulong n_submod(ulong x, ulong y, ulong n)
0345 {
0346     FLINT_ASSERT(x < n);
0347     FLINT_ASSERT(y < n);
0348     FLINT_ASSERT(n != 0);
0349
0350     return (y > x ? x - y + n : x - y);
0351 }
0352
0353 ULONG_EXTRAS_INLINE
0354 ulong n_negmod(ulong x, ulong n)
0355 {
0356     FLINT_ASSERT(x < n);
0357     FLINT_ASSERT(n != 0);
0358
0359     return n_submod(0, x, n);
0360 }
0361
0362 ulong n_sqrtmod(ulong a, ulong p);
0363 slong n_sqrtmod_2pow(ulong ** sqrt, ulong a, slong exp);
0364 slong n_sqrtmod_primepow(ulong ** sqrt, ulong a, ulong p, slong exp);
0365 slong n_sqrtmodn(ulong ** sqrt, ulong a, n_factor_t * fac);
0366
0367 ULONG_EXTRAS_INLINE
0368 ulong n_invmod(ulong x, ulong y)
0369 {
0370    ulong r, g;
0371
0372    g = n_gcdinv(&r, x, y);
0373    if (g != 1)
0374       flint_throw(FLINT_IMPINV, "Cannot invert modulo %wd*%wd\n", g, y/g);
0375
0376    return r;
0377 }
0378
0379 ulong n_binvert(ulong a);
0380
0381 ULONG_EXTRAS_INLINE
0382 ulong n_barrett_precomp(ulong n)
0383 {
0384     ulong q, r;
0385     FLINT_ASSERT(n >= 2);
0386     udiv_qrnnd(q, r, UWORD(1), UWORD(0), n);
0387     return q;
0388 }
0389
0390 ULONG_EXTRAS_INLINE
0391 ulong n_mod_barrett_lazy(ulong x, ulong n, ulong npre)
0392 {
0393     return x - n_mulhi(x, npre) * n;
0394 }
0395
0396 ULONG_EXTRAS_INLINE
0397 ulong n_mod_barrett(ulong x, ulong n, ulong npre)
0398 {
0399     ulong y = n_mod_barrett_lazy(x, n, npre);
0400     if (y >= n)
0401         y -= n;
0402     return y;
0403 }
0404
0405 ULONG_EXTRAS_INLINE
0406 ulong n_lemire_precomp(ulong n)
0407 {
0408     return UWORD_MAX / n + 1;
0409 }
0410
0411 ULONG_EXTRAS_INLINE
0412 ulong n_mod_lemire(ulong x, ulong n, ulong npre)
0413 {
0414     return n_mulhi(n, x * npre);
0415 }
0416
0417 /* Double-limb arithmetic. */
0418
0419 void n_ll_small_preinv(nn_ptr minv, nn_srcptr m);
0420 void n_ll_small_powmod_triple(nn_ptr res1, nn_ptr res2, nn_ptr res3, ulong b1,
0421     ulong b2, ulong b3, nn_srcptr exp, nn_srcptr m, nn_srcptr minv);
0422 void n_ll_small_2_powmod(nn_ptr res, nn_srcptr exp, nn_srcptr m, nn_srcptr minv);
0423
0424 /* Modular multiplication with fixed operand **********************************/
0425
0426 ULONG_EXTRAS_INLINE
0427 ulong n_mulmod_precomp_shoup(ulong a, ulong n)
0428 {
0429     ulong a_precomp, r;
0430     udiv_qrnnd(a_precomp, r, a, UWORD(0), n);
0431     return a_precomp;
0432 }
0433
0434 ULONG_EXTRAS_INLINE
0435 ulong n_mulmod_shoup(ulong a, ulong b, ulong a_precomp, ulong n)
0436 {
0437     ulong res, p_hi = n_mulhi(a_precomp, b);
0438
0439     res = a * b - p_hi * n;
0440
0441     if (res >= n)
0442         res -= n;
0443
0444     return res;
0445 }
0446
0447 ULONG_EXTRAS_INLINE
0448 void n_mulmod_precomp_shoup_quo_rem(ulong * a_pr_quo, ulong * a_pr_rem, ulong a, ulong n)
0449 {
0450     udiv_qrnnd(*a_pr_quo, *a_pr_rem, a, UWORD(0), n);
0451 }
0452
0453 ULONG_EXTRAS_INLINE
0454 ulong n_mulmod_precomp_shoup_rem_from_quo(ulong a_pr_quo, ulong n)
0455 {
0456     return - a_pr_quo * n;
0457 }
0458
0459 ULONG_EXTRAS_INLINE
0460 void n_mulmod_and_precomp_shoup(ulong * ab, ulong * ab_precomp,
0461                                 ulong a, ulong b,
0462                                 ulong a_pr_quo, ulong a_pr_rem, ulong b_precomp,
0463                                 ulong n)
0464 {
0465     ulong p_hi, p_lo;
0466
0467     umul_ppmm(p_hi, *ab_precomp, a_pr_quo, b);
0468     *ab = a * b - p_hi * n;
0469     if (*ab >= n)
0470         *ab -= n;
0471
0472     umul_ppmm(p_hi, p_lo, b_precomp, a_pr_rem);
0473     p_lo = b * a_pr_rem - p_hi * n;
0474     *ab_precomp += p_hi;
0475     if (p_lo >= n)
0476         *ab_precomp += 1;
0477 }
0478
0479
0480 /* Primitive roots and discrete logarithms ***********************************/
0481
0482 ulong n_quadratic_nonresidue(ulong n);
0483 ulong n_primitive_root_prime_prefactor(ulong p, n_factor_t * factors);
0484 ulong n_primitive_root_prime(ulong p);
0485
0486 ulong n_discrete_log_bsgs(ulong b, ulong a, ulong n);
0487
0488 /* Special functions *********************************************************/
0489
0490 int n_jacobi(slong x, ulong y);
0491 int n_jacobi_unsigned(ulong x, ulong y);
0492 int _n_jacobi_unsigned(ulong x, ulong y, unsigned int r);
0493
0494 int n_moebius_mu(ulong n);
0495 void n_moebius_mu_vec(int * mu, ulong len);
0496
0497 ulong n_euler_phi(ulong n);
0498
0499 /* Primality *****************************************************************/
0500
0501 #define FLINT_NUM_PRIMES_SMALL 172
0502 #define FLINT_PRIMES_SMALL_CUTOFF 1030
0503 #define FLINT_PSEUDOSQUARES_CUTOFF 1000
0504 #define FLINT_PRIMES_TAB_DEFAULT_CUTOFF 1000000
0505 #define FLINT_PRIME_PI_ODD_LOOKUP_CUTOFF 311
0506 #define FLINT_SIEVE_SIZE 65536
0507
0508 #if FLINT64
0509 # define UWORD_MAX_PRIME UWORD(18446744073709551557)
0510 #else
0511 # define UWORD_MAX_PRIME UWORD(4294967291)
0512 #endif
0513
0514 FLINT_DLL extern const unsigned int flint_primes_small[];
0515
0516 extern FLINT_TLS_PREFIX ulong * _flint_primes[FLINT_BITS];
0517 extern FLINT_TLS_PREFIX double * _flint_prime_inverses[FLINT_BITS];
0518 extern FLINT_TLS_PREFIX slong _flint_primes_used;
0519
0520 void n_primes_init(n_primes_t iter);
0521 void n_primes_clear(n_primes_t iter);
0522
0523 void n_primes_extend_small(n_primes_t iter, ulong bound);
0524 void n_primes_sieve_range(n_primes_t iter, ulong a, ulong b);
0525 void n_primes_jump_after(n_primes_t iter, ulong n);
0526
0527 ulong n_primes_next(n_primes_t iter);
0528
0529 void n_compute_primes(ulong num_primes);
0530 void n_cleanup_primes(void);
0531
0532 const ulong * n_primes_arr_readonly(ulong n);
0533 const double * n_prime_inverses_arr_readonly(ulong n);
0534
0535 int n_is_probabprime(ulong n);
0536 int n_is_probabprime_fermat(ulong n, ulong i);
0537 int n_is_probabprime_fibonacci(ulong n);
0538 int n_is_probabprime_lucas(ulong n);
0539 int n_is_probabprime_BPSW(ulong n);
0540
0541 int n_is_strong_probabprime_precomp(ulong n, double npre, ulong a, ulong d);
0542 int n_is_strong_probabprime2_preinv(ulong n, ulong ninv, ulong a, ulong d);
0543
0544 int n_is_prime(ulong n);
0545 int n_is_prime_odd_no_trial(ulong n);
0546 int n_is_prime_pseudosquare(ulong n);
0547 int n_is_prime_pocklington(ulong n, ulong iterations);
0548
0549 ulong n_nth_prime(ulong n);
0550 void n_nth_prime_bounds(ulong *lo, ulong *hi, ulong n);
0551
0552 ulong n_prime_pi(ulong n);
0553 void n_prime_pi_bounds(ulong *lo, ulong *hi, ulong n);
0554
0555 ulong n_nextprime(ulong n, int FLINT_UNUSED(proved));
0556
0557 int n_ll_is_prime(ulong nhi, ulong nlo);
0558
0559 /* Factorisation *************************************************************/
0560
0561 #define FLINT_FACTOR_TRIAL_PRIMES_BEFORE_PRIMALITY_TEST 64
0562
0563 /* This happens to be exactly the 16-bit primes. */
0564 #define FLINT_FACTOR_TRIAL_PRIMES 6542
0565 /* First omitted prime p. Factors < p^2 after trial division are guaranteed
0566    to be prime. */
0567 #define FLINT_FACTOR_TRIAL_PRIMES_PRIME UWORD(65537)
0568 #if FLINT_BITS == 64
0569 #define FLINT_FACTOR_TRIAL_CUTOFF (FLINT_FACTOR_TRIAL_PRIMES_PRIME * FLINT_FACTOR_TRIAL_PRIMES_PRIME)
0570 #else
0571 #define FLINT_FACTOR_TRIAL_CUTOFF UWORD_MAX
0572 #endif
0573
0574 #define FLINT_FACTOR_SQUFOF_ITERS 50000
0575 #define FLINT_FACTOR_ONE_LINE_MAX (UWORD(1)<<50)
0576 #define FLINT_FACTOR_ONE_LINE_ITERS 40000
0577 #define FLINT_FACTOR_POLLARD_BRENT_MIN (UWORD(1)<<38)
0578 #define FLINT_FACTOR_POLLARD_BRENT_ITERS 32768
0579
0580 ULONG_EXTRAS_INLINE void n_factor_init(n_factor_t * factors) { factors->num = 0; }
0581
0582 ulong n_factor_evaluate(const n_factor_t * fac);
0583
0584 void n_factor(n_factor_t * factors, ulong n, int FLINT_UNUSED(proved));
0585
0586 void n_factor_insert(n_factor_t * factors, ulong p, ulong exp);
0587
0588 ulong n_factor_trial_range(n_factor_t * factors, ulong n, ulong start, ulong num_primes);
0589 ulong n_factor_trial_partial(n_factor_t * factors, ulong n, ulong * prod, ulong num_primes, ulong limit);
0590 ulong n_factor_trial(n_factor_t * factors, ulong n, ulong num_primes);
0591 ulong n_factor_partial(n_factor_t * factors, ulong n, ulong limit, int proved);
0592
0593 ulong n_factor_power235(ulong *exp, ulong n);
0594 ulong n_factor_one_line(ulong n, ulong iters);
0595 ulong n_factor_lehman(ulong n);
0596
0597 ulong n_ll_factor_SQUFOF(ulong nhi, ulong nlo, ulong iters);
0598 ulong n_factor_SQUFOF(ulong n, ulong iters);
0599
0600 ulong n_factor_pp1(ulong n, ulong B1, ulong c);
0601 ulong n_factor_pp1_wrapper(ulong n);
0602
0603 int n_factor_pollard_brent_single(ulong *factor, ulong n, ulong ai, ulong xi, ulong max_iters);
0604 int n_factor_pollard_brent(ulong *factor, flint_rand_t state, ulong n_in, ulong max_tries, ulong max_iters);
0605
0606 int n_remove(ulong * n, ulong p);
0607 int n_remove2_precomp(ulong * n, ulong p, double ppre);
0608
0609 /* ECM functions *************************************************************/
0610
0611 typedef struct
0612 {
0613     ulong x, z;        /* the coordinates */
0614     ulong a24;         /* value (a + 2)/4 */
0615     ulong ninv;
0616     ulong normbits;
0617     ulong one;
0618
0619     unsigned char *GCD_table; /* checks whether baby step int is
0620                                  coprime to Primorial or not */
0621     unsigned char **prime_table;
0622 }
0623 n_ecm_s;
0624
0625 typedef n_ecm_s n_ecm_t[1];
0626
0627 void n_factor_ecm_double(ulong *x, ulong *z, ulong x0, ulong z0, ulong n, n_ecm_t n_ecm_inf);
0628 void n_factor_ecm_add(ulong *x, ulong *z, ulong x1, ulong z1, ulong x2, ulong z2, ulong x0, ulong z0, ulong n, n_ecm_t n_ecm_inf);
0629 void n_factor_ecm_mul_montgomery_ladder(ulong *x, ulong *z, ulong x0, ulong z0, ulong k, ulong n, n_ecm_t n_ecm_inf);
0630 int n_factor_ecm_select_curve(ulong *f, ulong sig, ulong n, n_ecm_t n_ecm_inf);
0631
0632 int n_factor_ecm(ulong *f, ulong curves, ulong B1, ulong B2, flint_rand_t state, ulong n);
0633 int n_factor_ecm_stage_I(ulong *f, const ulong *prime_array, ulong num, ulong B1, ulong n, n_ecm_t n_ecm_inf);
0634 int n_factor_ecm_stage_II(ulong *f, ulong B1, ulong B2, ulong P, ulong n, n_ecm_t n_ecm_inf);
0635
0636 #ifdef __cplusplus
0637 }
0638 #endif
0639
0640 #endif