// -*- C++ -*- // automatically generated by autodoc // ========== HEADER FILE src/mod/chebyshev.h: ========== // ----- SRCFILE=src/mod/chebyshev1.cc: ----- void chebyT(umod_t n, umod_t x, umod_t &t1, umod_t &t0, umod_t m); // Compute t1=T(n-1,x), t0=T(n,x) modulo m // where T(n,x) is the n-th Chebyshev polynomial of the first kind. umod_t chebyT(umod_t n, umod_t x, umod_t m); // Return t=T(n,x) modulo m // where T(n,x) is the n-th Chebyshev polynomial of the first kind. void chebyT2(umod_t n, umod_t &t1, umod_t &t0, umod_t m); // Compute t1=T(n-1,x), t0=T(n,x) modulo m where x=2 // and T(n,x) is the n-th Chebyshev polynomial of the first kind. // Must have m>4 umod_t chebyT2(umod_t n, umod_t m); // Return t=T(n,x) modulo m where x=2 // and T(n,x) is the n-th Chebyshev polynomial of the first kind. // Must have m>4 // ----- SRCFILE=src/mod/chebyshev2.cc: ----- void chebyU(umod_t n, umod_t x, umod_t &u1, umod_t &u0, umod_t m); // Compute u1=U(n-1, x), u0=U(n, x) modulo m // where U(n, x) is the n-th Chebyshev polynomial of the second kind. umod_t chebyU(umod_t n, umod_t x, umod_t m); // Return t=U(n, x) modulo m // where U(n, x) is the n-th Chebyshev polynomial of the second kind. void chebyU2(umod_t n, umod_t &u1, umod_t &u0, umod_t m); // Compute u1=U(n-1, x), u0=U(n, x) modulo m where x=2 // and U(n, x) is the n-th Chebyshev polynomial of the second kind. // Must have m>4 umod_t chebyU2(umod_t n, umod_t m); // Return u=U(n, x) modulo m where x=2 // and U(n, x) is the n-th Chebyshev polynomial of the second kind. // Must have m>4 // ========== HEADER FILE src/mod/divisors.h: ========== class divisors; // Generate all divisors of a number n. // Method: generate subsets of the multiset of exponents // via mixed radix counting. // ========== HEADER FILE src/mod/factor.h: ========== class factorization; // Factorization of a numbers into prime powers. // Factors can be supplied for constructor, // otherwise trial division is used. // ----- SRCFILE=src/mod/factor.cc: ----- umod_t get_factor_q(umod_t n, umod_t f); // if f divides n return n/f // else return 0 ulong divide_out_factor(umod_t &n, umod_t v); // while v divides n // divide n by v // return how often divided // ========== HEADER FILE src/mod/isqrt.h: ========== Type isqrt(Type d); // Return x (the integer square root of d) so that // x*x <= d and (x+1)*(x+1) > d //. // see Cohen p.38 // ========== HEADER FILE src/mod/mersenne.h: ========== inline bool is_mersenne_x(ulong x); // Return true if x is the exponent of a known Mersenne prime. inline umod_t mersenne(ulong e); inline umod_t mersenne_factorization(ulong e, factorization *F); // ========== HEADER FILE src/mod/mod.h: ========== // ----- SRCFILE=src/mod/modinit.cc: ----- void mod_reset(); bool mod_initialize(umod_t m, umod_t *primes/*=nullptr*/); class mod; // Modular type and arithmetic operations on it // ========== HEADER FILE src/mod/modarith.h: ========== inline umod_t incr_mod(umod_t a, umod_t m); inline umod_t decr_mod(umod_t a, umod_t m); inline umod_t neg_mod(umod_t b, umod_t m); inline umod_t sub_mod(umod_t a, umod_t b, umod_t m); inline umod_t add_mod(umod_t a, umod_t b, umod_t m); inline umod_t mul_mod(umod_t a, umod_t b, umod_t m); inline umod_t sqr_mod(umod_t a, umod_t m); inline umod_t mul_mod_m1dd(umod_t a, umod_t b, umod_t m, long double m1dd); // NOTE: fails for some moduli >62bit, e.g. 0x7ffedc0000000001 inline umod_t pow_mod(umod_t a, umod_t e, umod_t m); // Left-to-right scan inline umod_t pow_mod(umod_t a, umod_t e, umod_t m); // Right-to-left scan inline umod_t inv_modp(umod_t a, umod_t p); // compute inverse of a modulo p where p is prime inline umod_t inv_modpp(umod_t a, umod_t p, ulong e); // compute inverse of a modulo p^e where p is prime inline umod_t inv_mod_egcd(umod_t x, umod_t m); // NOTE: computation of mod inverse by egcd() // does not work for moduli >=2**63 because // signed types are used. // ========== HEADER FILE src/mod/mtypes.h: ========== // ========== HEADER FILE src/mod/numtheory.h: ========== // ----- SRCFILE=src/mod/kronecker.cc: ----- int kronecker(umod_t a, umod_t b); // Return Kronecker symbol (a/b). // Equal to Legendre symbol (a/b) if b is an odd prime. // ----- SRCFILE=src/mod/euler-phi.cc: ----- umod_t euler_phi(umod_t n); umod_t euler_phi(umod_t pr, ulong ex); umod_t euler_phi(const factorization &ff); // let f = \prod_i{p_i^{e_i}} // then euler_phi(f) = // == \prod_i{ euler_phi(p_i^{e_i}) } // == \prod_i{ p_i^{e_i}-p_i^{e_i-1} } // == \prod_i{ (p_i-1) * p_i^{e_i-1} } // ----- SRCFILE=src/mod/chinese.cc: ----- umod_t chinese(const umod_t *x, const factorization &f); // Return R modulo M where: // f[] is the factorization of M, // x[] := R modulo the prime powers of f[]. // ----- SRCFILE=src/mod/cyclic.cc: ----- bool is_cyclic(const factorization &f); // Let f be the factorization of m. // Return whether the units modulo m, i.e. (Z/mZ)* // are a cyclic group. // ----- SRCFILE=src/mod/order.cc: ----- umod_t order_mod(umod_t x, umod_t m, const factorization &phifact); // Return the order of x (mod m). // See Cohen, p.25 // ----- SRCFILE=src/mod/maxorder.cc: ----- umod_t maxorder_mod(const factorization &modfact); // Return the maximal order in the group of units (Z/mZ)* // modfact must be the factorization of m. // If m = 2^e0 * \prod_i{p_i^{e_i}} i=1...k // Then maxorder = lcm(f0,f1,f2,...,fk) // where f0 = 2^e0 if e0 \in {0,1,2}, else (2^e0)/2 // and fi = euler_phi(p_i^{e_i}) = (p_i-1) * p_i^{e_i-1} umod_t maxorder_element_mod(const factorization &modfact, const factorization &phifact); // Return element of maximal order modulo m. // modfact must be the factorization of m, // phifact must be the factorization of euler_phi(m) // ----- SRCFILE=src/mod/quadresidue.cc: ----- bool is_quadratic_residue_2ex(umod_t a, ulong x); // Return whether a is quadratic residue mod 2**x bool is_quadratic_residue(umod_t a, const factorization &mf); // Return whether a is quadratic residue mod mf // ----- SRCFILE=src/mod/sqrtmod.cc: ----- umod_t sqrt_modp(umod_t a, umod_t p); // Return x such that x*x==a (mod p) // p must be an odd prime. // If a is not a square mod p then return 0. umod_t sqrt_modpp(umod_t a, umod_t p, ulong ex); // Return r so that r^2 == a (mod p^ex) // return 0 if there is no such r umod_t sqrt_modf(umod_t a, const factorization &mf); // Return sqrt(a) mod m, given the factorization mf of m // ========== HEADER FILE src/mod/primes.h: ========== // ----- SRCFILE=src/mod/primes.cc: ----- bool is_small_prime(ulong n, const bitarray *B/*=nullptr*/); // Return true if n is a small prime. // Return false if table of primes is not big enough. ulong next_small_prime(ulong n, const bitarray *B/*=nullptr*/); // Return next prime >= n. // Return zero if table of primes is not big enough. // ----- SRCFILE=src/mod/eratosthenes.cc: ----- bitarray * make_prime_bitarray(ulong n, bitarray *B/*=nullptr*/); bitarray * make_oddprime_bitarray(ulong n, bitarray *B/*=nullptr*/); // Sieve of Eratosthenes. // ----- SRCFILE=src/mod/rabinmiller.cc: ----- void n2qt(const umod_t n, umod_t &q, uint &t); // Set q,t so that n == q * 2^t + 1 // n must not equal 1, else routine loops. bool is_strong_pseudo_prime(const umod_t n, const umod_t a, const umod_t q, const uint t); // Return whether n is a strong pseudoprime to base a. // q and t must be set so that n == q * 2^t + 1 bool rabin_miller(umod_t n, uint cm/*=0*/); // Miller-Rabin compositeness test. // Return true of none of the bases <=cm prove compositeness. // If false is returned, then n is proven composite (also for n=1 or n=0). // If true is returned the probability // that n is composite is less than (1/4)^cm // ----- SRCFILE=src/mod/perfpow.cc: ----- static bitarray * make_perfpow_bitarray(ulong n); bool is_small_perfpow(ulong n); // Return whether n is a small perfect power in perfpow_bitarray