1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
///
/// Contains [`convolution::ConvolutionAlgorithm`], an abstraction for algorithms
/// for computing convolutions, together with various implementations.
///
///
/// Contains [`matmul::MatmulAlgorithm`], an abstraction for algorithms
/// for computing matrix multiplication, together with various implementations.
///
///
/// Contains [`sqr_mul::generic_abs_square_and_multiply()`] and other functions
/// for computing a power of an element in a generic monoid.
///
///
/// Contains multiple variants of the Extended Euclidean Algorithm.
///
///
/// Contains algorithms to find roots of unity in finite fields.
///
///
/// Contains [`fft::FFTAlgorithm`], an abstraction for algorithms
/// for computing FFTs over various rings, together with different implementations.
///
///
/// 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.
///
///
/// 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.
///
///
/// Contains an implementation of the Miller-Rabin probabilistic primality test.
///
///
/// Contains an implementation of Lenstra's ECM factoring algorithm.
///
///
/// Contains an implementation of the Sieve of Erathostenes, for enumerating
/// prime number up to a certain bound.
///
///
/// Contains an implementation of the bisection method for computing roots, but
/// working with integers only.
///
///
/// Contains an implementation of integer factoring and related utilities, delegating
/// to [`ec_factor`].
///
///
/// Contains an implementation of the Lenstra-Lenstra-Lovasz algorithm for lattice basis
/// reduction.
///
///
/// Contains [`cyclotomic::cyclotomic_polynomial()`] for computing cyclotomic polynomials.
///
///
/// 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()`].
///
///
/// Contains [`poly_factor::FactorPolyField`] for fields over which we can factor polynomials.
///
/// Additionally contains most of the algorithms for factoring polynomials over various fields
/// and rings.
///
///
/// Contains various algorithms for computing discrete logarithms over generic monoids.
///
///
/// Contains [`linsolve::LinSolveRing`] for rings over which we can solve linear systems.
///
/// Additionally contains most of the algorithms for actually solving linear systems over
/// various rings, including partial smith normal forms.
///
///
/// Contains algorithms for computing resultants.
///
///
/// 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`).
///
///
/// Contains algorithms for polynomial interpolation.
///
///
/// Contains Buchberger's algorithm for computing Groebner basis.
///
///
/// Contains [`poly_gcd::PolyTFracGCDRing`] for rings over which we can compute polynomial gcds and
/// related operations, modulo multiplication by non-zero divisors.
///
///
/// Contains implementations to extend [`crate::rings::extension::number_field::NumberField`]s by adjoining
/// additional roots of polynomials.
///
///
/// Contains algorithms for computing divisions in ring extensions for which standard methods
/// are not sufficient.
///
///
/// Contains algorithms for computing the Galois group and Galois closure of a
/// [`crate::rings::extension::number_field::NumberField`].
///
///
/// Contains an implementation of the Newton-Raphson method for approximating roots of
/// polynomials (and more generally, "well-behaved" functions).
///
///
/// Contains an implementation of the Fincke-Pohst lattice point enumeration algorithm.
///