malachite_base/num/arithmetic/
mod_square.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
9use crate::num::arithmetic::traits::{
10    ModMulPrecomputed, ModPow, ModPowAssign, ModSquare, ModSquareAssign, ModSquarePrecomputed,
11    ModSquarePrecomputedAssign,
12};
13
14// `$mul_data` projects the modular-exponentiation data onto the modular-multiplication data it
15// contains: the pow data is `(mul_inverse, shift)` for every type except `u128`, whose pow and mul
16// data are both `()`.
17macro_rules! impl_mod_square {
18    ($t:ident, $mul_data:path) => {
19        impl ModSquare for $t {
20            type Output = $t;
21
22            /// Squares a number modulo another number $m$. The input must be already reduced modulo
23            /// $m$.
24            ///
25            /// $f(x, m) = y$, where $x, y < m$ and $x^2 \equiv y \mod m$.
26            ///
27            /// # Worst-case complexity
28            /// Constant time and additional memory.
29            ///
30            /// # Panics
31            /// Panics if `self` is greater than or equal to `m`.
32            ///
33            /// # Examples
34            /// See [here](super::mod_square#mod_square).
35            #[inline]
36            fn mod_square(self, m: $t) -> $t {
37                self.mod_pow(2, m)
38            }
39        }
40
41        impl ModSquareAssign for $t {
42            /// Squares a number modulo another number $m$, in place. The input must be already
43            /// reduced modulo $m$.
44            ///
45            /// $x \gets y$, where $x, y < m$ and $x^2 \equiv y \mod m$.
46            ///
47            /// # Worst-case complexity
48            /// Constant time and additional memory.
49            ///
50            /// # Panics
51            /// Panics if `self` is greater than or equal to `m`.
52            ///
53            /// # Examples
54            /// See [here](super::mod_square#mod_square_assign).
55            #[inline]
56            fn mod_square_assign(&mut self, m: $t) {
57                self.mod_pow_assign(2, m);
58            }
59        }
60
61        impl ModSquarePrecomputed<u64, $t> for $t {
62            /// Squares a number modulo another number $m$. The input must be already reduced modulo
63            /// $m$.
64            ///
65            /// Some precomputed data is provided; this speeds up computations involving several
66            /// modular squarings with the same modulus. The precomputed data should be obtained
67            /// using [`precompute_mod_pow_data`](super::traits::ModPowPrecomputed).
68            ///
69            /// # Worst-case complexity
70            /// Constant time and additional memory.
71            ///
72            /// # Panics
73            /// Panics if `self` is greater than or equal to `m`.
74            ///
75            /// # Examples
76            /// See [here](super::mod_square#mod_square_precomputed).
77            #[inline]
78            fn mod_square_precomputed(self, m: $t, data: &Self::Data) -> Self::Output {
79                self.mod_mul_precomputed(self, m, $mul_data(data))
80            }
81        }
82
83        impl ModSquarePrecomputedAssign<u64, $t> for $t {
84            /// Squares a number modulo another number $m$, in place. The input must be already
85            /// reduced modulo $m$.
86            ///
87            /// Some precomputed data is provided; this speeds up computations involving several
88            /// modular squarings with the same modulus. The precomputed data should be obtained
89            /// using [`precompute_mod_pow_data`](super::traits::ModPowPrecomputed).
90            ///
91            /// # Worst-case complexity
92            /// Constant time and additional memory.
93            ///
94            /// # Panics
95            /// Panics if `self` is greater than or equal to `m`.
96            ///
97            /// # Examples
98            /// See [here](super::mod_square#mod_square_precomputed_assign).
99            #[inline]
100            fn mod_square_precomputed_assign(&mut self, m: $t, data: &Self::Data) {
101                *self = self.mod_mul_precomputed(*self, m, $mul_data(data));
102            }
103        }
104    };
105}
106const fn pair_mul_data<A, B>(data: &(A, B)) -> &A {
107    &data.0
108}
109
110const fn unit_mul_data(data: &()) -> &() {
111    data
112}
113
114impl_mod_square!(u8, pair_mul_data);
115impl_mod_square!(u16, pair_mul_data);
116impl_mod_square!(u32, pair_mul_data);
117impl_mod_square!(u64, pair_mul_data);
118impl_mod_square!(u128, unit_mul_data);
119impl_mod_square!(usize, pair_mul_data);
malachite_base/num/arithmetic/mod_square.rs

malachite_base/num/arithmetic/
mod_square.rs
