polycore

polycore

A shared polynomial trait foundation for fields, word-sized prime fields, Chinese remaindering, sparse multivariate and dense univariate polynomials, and a sparse incremental echelon form.

• Field: blanket trait over the field operators
• Modular: prime fields with access to bare residues
• Fp, Gf<P>: prime fields below $2^{64}$
• Poly<F>, Monomial, Order: sparse multivariate polynomials
• Uni<F>: dense univariate polynomials
• PrimeField: NTT multiplication, Newton division and half-GCD
• PowerTable<F>: cached monomial powers
• GeometricEvaluator<F>: successive geometric evaluations
• modp: word-sized modular arithmetic
• MulBy: Shoup multiplication by a fixed residue
• Primes: descending word-sized primes
• SmoothPrimes: primes with a prescribed power of two in p − 1
• PowerOfTwoSubgroup: subgroup generators and discrete logarithms
• RatFunc<F>: univariate rational functions
• Echelon<F>, dense: sparse and dense linear algebra
• crt: Chinese remaindering and rational reconstruction
• CrtAccumulator: incremental CRT over coefficient vectors
• MixedRadixAccumulator: CRT with coefficient support remapping
• WangContext: rational reconstruction with a shared bound
• lehmer: Lehmer gcd for big integers
• Newton<F>: incremental polynomial interpolation
• Thiele<F>: rational interpolation by continued fractions
• Massey<F>: incremental Berlekamp–Massey recurrence recovery
• Rng: deterministic sampling from keyed seeds
• BlackBox: evaluation of unknown functions over prime fields
• Ring: parsing and printing

Field is operator-based rather than method-based (add, multiply, ...) so that BigRational, Fp, and extensions can be fields without wrappers or impls, generic code reads as the mathematics does, and nothing new is needed from num-traits. The cost is some clone() calls on big coefficients but whatever.

Fp::zero() and Fp::one() carry no modulus and adopt the one they meet, so nullary constructors still work at a runtime modulus.

This library is for scientific computing uses not cryptography or anything timing attack sensitive.

polyfactor

Factoring in one variable, on top of polycore.

• factor_mod: Berlekamp over $\mathrm{GF}(p)$
• factor: Hensel lifting and Zassenhaus over $\mathbb{Q}$
• Alg, NumberField: number field arithmetic
• factor_over: Trager over number fields

License

Released under the MIT License. See LICENSE for details.