Module algorithms 

A collection of all number-theoretic algorithms that are currently implemented in this crate.

Modules

bigint_ops

Contains basic algorithms for implementing operations on arbitrary-precision integers. Unless you are implementing your own big integer type, you should use crate::integer::BigIntRing instead.

buchberger

Contains Buchberger’s algorithm for computing Groebner basis.

convolution

Contains convolution::ConvolutionAlgorithm, an abstraction for algorithms for computing convolutions, together with various implementations.

cyclotomic

Contains cyclotomic::cyclotomic_polynomial() for computing cyclotomic polynomials.

discrete_log

Contains various algorithms for computing discrete logarithms over generic monoids.

ec_factor

Contains an implementation of Lenstra’s ECM factoring algorithm.

eea

Contains multiple variants of the Extended Euclidean Algorithm.

erathostenes

Contains an implementation of the Sieve of Erathostenes, for enumerating prime number up to a certain bound.

extension_ops

Contains basic algorithms for implementing operations on ring extensions. Unless you are implementing your own extension ring type, you should use the operations through crate::rings::extension::FreeAlgebra instead.

fft

Contains fft::FFTAlgorithm, an abstraction for algorithms for computing FFTs over various rings, together with different implementations.

fincke_pohst

Contains an implementation of the Fincke-Pohst lattice point enumeration algorithm.

galois

Contains algorithms for computing the Galois group and Galois closure of a crate::rings::extension::number_field::NumberField.

int_bisect

Contains an implementation of the bisection method for computing roots, but working with integers only.

int_factor

Contains an implementation of integer factoring and related utilities, delegating to ec_factor.

interpolate

Contains algorithms for polynomial interpolation.

linsolve

Contains linsolve::LinSolveRing for rings over which we can solve linear systems.

lll

Contains an implementation of the Lenstra-Lenstra-Lovasz algorithm for lattice basis reduction.

matmul

Contains matmul::MatmulAlgorithm, an abstraction for algorithms for computing matrix multiplication, together with various implementations.

miller_rabin

Contains an implementation of the Miller-Rabin probabilistic primality test.

newton

Contains an implementation of the Newton-Raphson method for approximating roots of polynomials (and more generally, “well-behaved” functions).

poly_div

Contains poly_div::poly_div_rem() for computing polynomial division. In most cases, you will instead use this functionality through crate::pid::EuclideanRing::euclidean_div_rem().

poly_factor

Contains poly_factor::FactorPolyField for fields over which we can factor polynomials.

poly_gcd

Contains poly_gcd::PolyTFracGCDRing for rings over which we can compute polynomial gcds and related operations, modulo multiplication by non-zero divisors.

qr

rational_reconstruction

Contains algorithms for rational reconstruction, i.e. find a small rational number x from its reduction modulo some n (coprime to the denominator of x).

resultant

Contains algorithms for computing resultants.

splitting_field

Contains implementations to extend crate::rings::extension::number_field::NumberFields by adjoining additional roots of polynomials.

sqr_mul

Contains sqr_mul::generic_abs_square_and_multiply() and other functions for computing a power of an element in a generic monoid.

unity_root

Contains algorithms to find roots of unity in finite fields.

zpe_extension

Contains algorithms for computing divisions in ring extensions for which standard methods are not sufficient.