malachite_base/unsigned_polynomial/arithmetic/mod.rs
1// Copyright © 2026 Mikhail Hogrefe
2//
3// This file is part of Malachite.
4//
5// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
6// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
7// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.
8
9/// Implementations of [`CanonicalizeUnit`](crate::num::arithmetic::traits::CanonicalizeUnit) and
10/// [`CanonicalizeUnitAssign`](crate::num::arithmetic::traits::CanonicalizeUnitAssign), which bring
11/// a polynomial into canonical unit form.
12pub mod canonicalize_unit;
13/// Implementations of [`ComposePowerOfX`](crate::polynomial::ComposePowerOfX) and
14/// [`ComposePowerOfXAssign`](crate::polynomial::ComposePowerOfXAssign), for substituting a power of
15/// the variable into a polynomial.
16pub mod compose_power_of_x;
17/// Implementations of [`Content`](crate::polynomial::Content),
18/// [`PrimitivePart`](crate::polynomial::PrimitivePart),
19/// [`PrimitivePartAssign`](crate::polynomial::PrimitivePartAssign), and
20/// [`ContentAndPrimitivePart`](crate::polynomial::ContentAndPrimitivePart), which compute the GCD
21/// of a polynomial's coefficients and the polynomial divided by it.
22pub mod content;
23/// Implementations of [`DeflatePowerOfX`](crate::polynomial::DeflatePowerOfX) and
24/// [`DeflatePowerOfXAssign`](crate::polynomial::DeflatePowerOfXAssign), for undoing the
25/// substitution of a power of the variable into a polynomial.
26pub mod deflate_power_of_x;
27/// Implementations of [`DivPowerOfX`](crate::polynomial::DivPowerOfX) and
28/// [`DivPowerOfXAssign`](crate::polynomial::DivPowerOfXAssign), for dividing a polynomial by a
29/// power of its variable and discarding the remainder.
30pub mod div_power_of_x;
31/// Implementations of [`ModEvaluate`](crate::polynomial::ModEvaluate) and
32/// [`ModPowerOf2Evaluate`](crate::polynomial::ModPowerOf2Evaluate), which evaluate a polynomial at
33/// a value modulo a value or a power of 2.
34pub mod evaluate;
35/// An implementation of [`ExponentGcd`](crate::polynomial::ExponentGcd), the greatest common
36/// divisor of the exponents at which a polynomial has nonzero coefficients.
37pub mod exponent_gcd;
38/// An implementation of [`Height`](crate::num::arithmetic::traits::Height), the largest of a
39/// polynomial's coefficients.
40pub mod height;
41/// An implementation of [`IsUnit`](crate::num::arithmetic::traits::IsUnit), a trait for determining
42/// whether a number is a unit of its ring.
43pub mod is_unit;
44/// Implementations of [`ModAdd`](crate::num::arithmetic::traits::ModAdd) and
45/// [`ModAddAssign`](crate::num::arithmetic::traits::ModAddAssign), for adding two polynomials
46/// modulo a value.
47pub mod mod_add;
48/// Implementations of [`ModAddTruncated`](crate::polynomial::ModAddTruncated) and
49/// [`ModAddTruncatedAssign`](crate::polynomial::ModAddTruncatedAssign), for adding two polynomials
50/// modulo a value and keeping only their low coefficients.
51pub mod mod_add_truncated;
52/// Implementations of [`ModDerivative`](crate::polynomial::ModDerivative) and
53/// [`ModDerivativeAssign`](crate::polynomial::ModDerivativeAssign), for differentiating a
54/// polynomial modulo a number.
55pub mod mod_derivative;
56/// Implementations of [`ModIntegral`](crate::polynomial::ModIntegral) and
57/// [`ModIntegralAssign`](crate::polynomial::ModIntegralAssign), for integrating a polynomial modulo
58/// a value.
59pub mod mod_integral;
60/// An implementation of [`ModIsReduced`](crate::num::arithmetic::traits::ModIsReduced), which
61/// checks whether every coefficient of a polynomial is less than a given modulus.
62pub mod mod_is_reduced;
63/// Implementations of [`ModMakeMonic`](crate::polynomial::ModMakeMonic) and
64/// [`ModMakeMonicAssign`](crate::polynomial::ModMakeMonicAssign), which make a polynomial monic
65/// modulo a value.
66pub mod mod_make_monic;
67/// Implementations of [`ModMul`](crate::num::arithmetic::traits::ModMul) and
68/// [`ModMulAssign`](crate::num::arithmetic::traits::ModMulAssign), for multiplying two polynomials
69/// modulo a value.
70pub mod mod_mul;
71#[doc(hidden)]
72pub mod mod_mul_middle;
73/// Implementations of [`ModMulTruncated`](crate::polynomial::ModMulTruncated) and
74/// [`ModMulTruncatedAssign`](crate::polynomial::ModMulTruncatedAssign), for multiplying two
75/// polynomials modulo a value and keeping the low coefficients of the product.
76pub mod mod_mul_truncated;
77/// Implementations of [`ModNeg`](crate::num::arithmetic::traits::ModNeg) and
78/// [`ModNegAssign`](crate::num::arithmetic::traits::ModNegAssign), which negate a polynomial modulo
79/// a number.
80pub mod mod_neg;
81/// Implementations of [`ModNthDerivative`](crate::polynomial::ModNthDerivative) and
82/// [`ModNthDerivativeAssign`](crate::polynomial::ModNthDerivativeAssign), for differentiating a
83/// polynomial any number of times modulo a number.
84pub mod mod_nth_derivative;
85/// Implementations of [`Mod`](crate::num::arithmetic::traits::Mod),
86/// [`ModAssign`](crate::num::arithmetic::traits::ModAssign), [`Rem`](core::ops::Rem) and
87/// [`RemAssign`](core::ops::RemAssign), which reduce every coefficient of a polynomial modulo a
88/// number.
89pub mod mod_op;
90/// Implementations of [`ModPow`](crate::num::arithmetic::traits::ModPow) and
91/// [`ModPowAssign`](crate::num::arithmetic::traits::ModPowAssign), for raising a polynomial to a
92/// power modulo a number.
93pub mod mod_pow;
94/// Implementations of [`ModPowTruncated`](crate::polynomial::ModPowTruncated) and
95/// [`ModPowTruncatedAssign`](crate::polynomial::ModPowTruncatedAssign), for raising a polynomial to
96/// a power modulo a number and keeping only the low coefficients.
97pub mod mod_pow_truncated;
98/// Implementations of [`ModPowerOf2`](crate::num::arithmetic::traits::ModPowerOf2) and
99/// [`ModPowerOf2Assign`](crate::num::arithmetic::traits::ModPowerOf2Assign), which reduce every
100/// coefficient of a polynomial modulo a power of 2.
101pub mod mod_power_of_2;
102/// Implementations of [`ModPowerOf2Add`](crate::num::arithmetic::traits::ModPowerOf2Add) and
103/// [`ModPowerOf2AddAssign`](crate::num::arithmetic::traits::ModPowerOf2AddAssign), for adding two
104/// polynomials modulo $2^k$.
105pub mod mod_power_of_2_add;
106/// Implementations of [`ModPowerOf2AddTruncated`](crate::polynomial::ModPowerOf2AddTruncated) and
107/// [`ModPowerOf2AddTruncatedAssign`](crate::polynomial::ModPowerOf2AddTruncatedAssign), for adding
108/// two polynomials modulo $2^k$ and keeping only their low coefficients.
109pub mod mod_power_of_2_add_truncated;
110/// Implementations of [`ModPowerOf2Derivative`](crate::polynomial::ModPowerOf2Derivative) and
111/// [`ModPowerOf2DerivativeAssign`](crate::polynomial::ModPowerOf2DerivativeAssign), for
112/// differentiating a polynomial modulo a power of 2.
113pub mod mod_power_of_2_derivative;
114/// Implementations of [`ModPowerOf2Integral`](crate::polynomial::ModPowerOf2Integral) and
115/// [`ModPowerOf2IntegralAssign`](crate::polynomial::ModPowerOf2IntegralAssign), for integrating a
116/// polynomial modulo $2^k$.
117pub mod mod_power_of_2_integral;
118/// An implementation of
119/// [`ModPowerOf2IsReduced`](crate::num::arithmetic::traits::ModPowerOf2IsReduced), which checks
120/// whether every coefficient of a polynomial is less than a given power of 2.
121pub mod mod_power_of_2_is_reduced;
122/// Implementations of [`ModPowerOf2Mul`](crate::num::arithmetic::traits::ModPowerOf2Mul) and
123/// [`ModPowerOf2MulAssign`](crate::num::arithmetic::traits::ModPowerOf2MulAssign), for multiplying
124/// two polynomials modulo $2^k$.
125pub mod mod_power_of_2_mul;
126/// Implementations of [`ModPowerOf2MulTruncated`](crate::polynomial::ModPowerOf2MulTruncated) and
127/// [`ModPowerOf2MulTruncatedAssign`](crate::polynomial::ModPowerOf2MulTruncatedAssign), for
128/// multiplying two polynomials modulo $2^k$ and keeping the low coefficients of the product.
129pub mod mod_power_of_2_mul_truncated;
130/// Implementations of [`ModPowerOf2Neg`](crate::num::arithmetic::traits::ModPowerOf2Neg) and
131/// [`ModPowerOf2NegAssign`](crate::num::arithmetic::traits::ModPowerOf2NegAssign), which negate a
132/// polynomial modulo a power of 2.
133pub mod mod_power_of_2_neg;
134/// Implementations of [`ModPowerOf2NthDerivative`](crate::polynomial::ModPowerOf2NthDerivative) and
135/// [`ModPowerOf2NthDerivativeAssign`](crate::polynomial::ModPowerOf2NthDerivativeAssign), for
136/// differentiating a polynomial any number of times modulo a power of 2.
137pub mod mod_power_of_2_nth_derivative;
138/// Implementations of [`ModPowerOf2Pow`](crate::num::arithmetic::traits::ModPowerOf2Pow) and
139/// [`ModPowerOf2PowAssign`](crate::num::arithmetic::traits::ModPowerOf2PowAssign), for raising a
140/// polynomial to a power modulo a power of 2.
141pub mod mod_power_of_2_pow;
142/// Implementations of [`ModPowerOf2PowTruncated`](crate::polynomial::ModPowerOf2PowTruncated) and
143/// [`ModPowerOf2PowTruncatedAssign`](crate::polynomial::ModPowerOf2PowTruncatedAssign), for raising
144/// a polynomial to a power modulo a power of 2 and keeping only the low coefficients.
145pub mod mod_power_of_2_pow_truncated;
146/// Implementations of [`ModPowerOf2Shl`](crate::num::arithmetic::traits::ModPowerOf2Shl) and
147/// [`ModPowerOf2ShlAssign`](crate::num::arithmetic::traits::ModPowerOf2ShlAssign), for
148/// left-shifting a polynomial modulo a power of 2.
149///
150/// # mod_power_of_2_shl
151/// ```
152/// use core::str::FromStr;
153/// use malachite_base::num::arithmetic::traits::ModPowerOf2Shl;
154/// use malachite_base::unsigned_polynomial::UnsignedPolynomial;
155///
156/// let p = UnsignedPolynomial::<u8>::from_str("5*x^2+x+3").unwrap();
157/// assert_eq!(
158/// p.clone().mod_power_of_2_shl(1u8, 3).to_string(),
159/// "2*x^2+2*x+6"
160/// );
161/// assert_eq!(
162/// p.clone().mod_power_of_2_shl(2u16, 3).to_string(),
163/// "4*x^2+4*x+4"
164/// );
165/// assert_eq!(p.mod_power_of_2_shl(3u32, 3).to_string(), "0");
166/// assert_eq!(
167/// UnsignedPolynomial::<u8>::from_str("x^2+128*x+1")
168/// .unwrap()
169/// .mod_power_of_2_shl(1u64, 8)
170/// .to_string(),
171/// "2*x^2+2"
172/// );
173/// assert_eq!(
174/// UnsignedPolynomial::<u64>::from_str("x+1")
175/// .unwrap()
176/// .mod_power_of_2_shl(63u128, 64)
177/// .to_string(),
178/// "9223372036854775808*x+9223372036854775808"
179/// );
180///
181/// let p = UnsignedPolynomial::<u8>::from_str("5*x^2+x+3").unwrap();
182/// assert_eq!((&p).mod_power_of_2_shl(1u8, 3).to_string(), "2*x^2+2*x+6");
183/// assert_eq!((&p).mod_power_of_2_shl(2u16, 3).to_string(), "4*x^2+4*x+4");
184/// assert_eq!((&p).mod_power_of_2_shl(3u32, 3).to_string(), "0");
185/// assert_eq!(
186/// (&UnsignedPolynomial::<u8>::from_str("x^2+128*x+1").unwrap())
187/// .mod_power_of_2_shl(1u64, 8)
188/// .to_string(),
189/// "2*x^2+2"
190/// );
191/// assert_eq!(
192/// (&UnsignedPolynomial::<u64>::from_str("x+1").unwrap())
193/// .mod_power_of_2_shl(63u128, 64)
194/// .to_string(),
195/// "9223372036854775808*x+9223372036854775808"
196/// );
197/// ```
198///
199/// # mod_power_of_2_shl_assign
200/// ```
201/// use core::str::FromStr;
202/// use malachite_base::num::arithmetic::traits::ModPowerOf2ShlAssign;
203/// use malachite_base::unsigned_polynomial::UnsignedPolynomial;
204///
205/// let mut p = UnsignedPolynomial::<u8>::from_str("5*x^2+x+3").unwrap();
206/// p.mod_power_of_2_shl_assign(1u8, 3);
207/// assert_eq!(p.to_string(), "2*x^2+2*x+6");
208///
209/// let mut p = UnsignedPolynomial::<u8>::from_str("5*x^2+x+3").unwrap();
210/// p.mod_power_of_2_shl_assign(3u32, 3);
211/// assert_eq!(p.to_string(), "0");
212///
213/// let mut p = UnsignedPolynomial::<u8>::from_str("x^2+128*x+1").unwrap();
214/// p.mod_power_of_2_shl_assign(1u64, 8);
215/// assert_eq!(p.to_string(), "2*x^2+2");
216///
217/// let mut p = UnsignedPolynomial::<u64>::from_str("x+1").unwrap();
218/// p.mod_power_of_2_shl_assign(63u128, 64);
219/// assert_eq!(p.to_string(), "9223372036854775808*x+9223372036854775808");
220/// ```
221pub mod mod_power_of_2_shl;
222/// Implementations of [`ModPowerOf2Square`](crate::num::arithmetic::traits::ModPowerOf2Square) and
223/// [`ModPowerOf2SquareAssign`](crate::num::arithmetic::traits::ModPowerOf2SquareAssign), for
224/// squaring a polynomial modulo $2^k$.
225pub mod mod_power_of_2_square;
226/// Implementations of [`ModPowerOf2SquareTruncated`](crate::polynomial::ModPowerOf2SquareTruncated)
227/// and [`ModPowerOf2SquareTruncatedAssign`](crate::polynomial::ModPowerOf2SquareTruncatedAssign),
228/// for squaring a polynomial modulo $2^k$ and keeping the low coefficients of the square.
229pub mod mod_power_of_2_square_truncated;
230/// Implementations of [`ModPowerOf2Sub`](crate::num::arithmetic::traits::ModPowerOf2Sub) and
231/// [`ModPowerOf2SubAssign`](crate::num::arithmetic::traits::ModPowerOf2SubAssign), for subtracting
232/// one polynomial from another modulo $2^k$.
233pub mod mod_power_of_2_sub;
234/// Implementations of [`ModPowerOf2SubTruncated`](crate::polynomial::ModPowerOf2SubTruncated) and
235/// [`ModPowerOf2SubTruncatedAssign`](crate::polynomial::ModPowerOf2SubTruncatedAssign), for
236/// subtracting one polynomial from another modulo $2^k$ and keeping only their low coefficients.
237pub mod mod_power_of_2_sub_truncated;
238/// Implementations of [`ModShl`](crate::num::arithmetic::traits::ModShl) and
239/// [`ModShlAssign`](crate::num::arithmetic::traits::ModShlAssign), for left-shifting a polynomial
240/// modulo a number.
241///
242/// # mod_shl
243/// ```
244/// use core::str::FromStr;
245/// use malachite_base::num::arithmetic::traits::ModShl;
246/// use malachite_base::unsigned_polynomial::UnsignedPolynomial;
247///
248/// let p = UnsignedPolynomial::<u8>::from_str("3*x^2+x+7").unwrap();
249/// assert_eq!(p.clone().mod_shl(1u8, 10).to_string(), "6*x^2+2*x+4");
250/// assert_eq!(p.mod_shl(3u16, 10).to_string(), "4*x^2+8*x+6");
251/// assert_eq!(
252/// UnsignedPolynomial::<u8>::from_str("3*x^2+5")
253/// .unwrap()
254/// .mod_shl(2u32, 12)
255/// .to_string(),
256/// "8"
257/// );
258/// assert_eq!(
259/// UnsignedPolynomial::<u64>::from_str("x+1")
260/// .unwrap()
261/// .mod_shl(100u64, 1000000000000000000)
262/// .to_string(),
263/// "229401496703205376*x+229401496703205376"
264/// );
265///
266/// let p = UnsignedPolynomial::<u8>::from_str("3*x^2+x+7").unwrap();
267/// assert_eq!((&p).mod_shl(1u8, 10).to_string(), "6*x^2+2*x+4");
268/// assert_eq!((&p).mod_shl(3u16, 10).to_string(), "4*x^2+8*x+6");
269/// assert_eq!(
270/// (&UnsignedPolynomial::<u8>::from_str("3*x^2+5").unwrap())
271/// .mod_shl(2u32, 12)
272/// .to_string(),
273/// "8"
274/// );
275/// assert_eq!(
276/// (&UnsignedPolynomial::<u64>::from_str("x+1").unwrap())
277/// .mod_shl(100u64, 1000000000000000000)
278/// .to_string(),
279/// "229401496703205376*x+229401496703205376"
280/// );
281/// ```
282///
283/// # mod_shl_assign
284/// ```
285/// use core::str::FromStr;
286/// use malachite_base::num::arithmetic::traits::ModShlAssign;
287/// use malachite_base::unsigned_polynomial::UnsignedPolynomial;
288///
289/// let mut p = UnsignedPolynomial::<u8>::from_str("3*x^2+x+7").unwrap();
290/// p.mod_shl_assign(1u8, 10);
291/// assert_eq!(p.to_string(), "6*x^2+2*x+4");
292///
293/// let mut p = UnsignedPolynomial::<u8>::from_str("3*x^2+x+7").unwrap();
294/// p.mod_shl_assign(3u16, 10);
295/// assert_eq!(p.to_string(), "4*x^2+8*x+6");
296///
297/// let mut p = UnsignedPolynomial::<u8>::from_str("3*x^2+5").unwrap();
298/// p.mod_shl_assign(2u32, 12);
299/// assert_eq!(p.to_string(), "8");
300///
301/// let mut p = UnsignedPolynomial::<u64>::from_str("x+1").unwrap();
302/// p.mod_shl_assign(100u64, 1000000000000000000);
303/// assert_eq!(p.to_string(), "229401496703205376*x+229401496703205376");
304/// ```
305pub mod mod_shl;
306/// Implementations of [`ModSquare`](crate::num::arithmetic::traits::ModSquare) and
307/// [`ModSquareAssign`](crate::num::arithmetic::traits::ModSquareAssign), for squaring a polynomial
308/// modulo a value.
309pub mod mod_square;
310/// Implementations of [`ModSquareTruncated`](crate::polynomial::ModSquareTruncated) and
311/// [`ModSquareTruncatedAssign`](crate::polynomial::ModSquareTruncatedAssign), for squaring a
312/// polynomial modulo a value and keeping the low coefficients of the square.
313pub mod mod_square_truncated;
314/// Implementations of [`ModSub`](crate::num::arithmetic::traits::ModSub) and
315/// [`ModSubAssign`](crate::num::arithmetic::traits::ModSubAssign), for subtracting one polynomial
316/// from another modulo a value.
317pub mod mod_sub;
318/// Implementations of [`ModSubTruncated`](crate::polynomial::ModSubTruncated) and
319/// [`ModSubTruncatedAssign`](crate::polynomial::ModSubTruncatedAssign), for subtracting one
320/// polynomial from another modulo a value and keeping only their low coefficients.
321pub mod mod_sub_truncated;
322/// Implementations of [`MulPowerOfX`](crate::polynomial::MulPowerOfX) and
323/// [`MulPowerOfXAssign`](crate::polynomial::MulPowerOfXAssign), for multiplying a polynomial by a
324/// power of its variable.
325pub mod mul_power_of_x;