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
• RatFunc<F>: univariate rational functions
• Echelon<F>, dense: sparse and dense linear algebra
• crt: Chinese remaindering and rational reconstruction
• lehmer: Lehmer gcd for big integers
• interp: Newton, Thiele, Berlekamp-Massey
• 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.