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
• 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
• RatFunc<F>: univariate rational functions
• Echelon<F>, dense: sparse and dense linear algebra
• modp_echelon: sparse elimination/null spaces on bare u64 residues, one modulus per matrix
• crt: Chinese remaindering and rational reconstruction
• lehmer: Lehmer gcd for big integers
• Newton<F>, Thiele<F>: polynomial and rational interpolation
• Massey<F>: incremental Berlekamp–Massey recurrence recovery
• 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

MIT Licensed. Copyright 2024-2026 Stephen Diehl. See LICENSE for details.