malachite_nz/natural/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::natural::Natural;
10use malachite_base::num::arithmetic::traits::{ModPow, ModPowAssign, ModSquare, ModSquareAssign};
11use malachite_base::num::basic::traits::Two;
12
13impl ModSquare<Self> for Natural {
14    type Output = Self;
15
16    /// Squares a [`Natural`] modulo another [`Natural`] $m$. The input must be already reduced
17    /// modulo $m$. Both [`Natural`]s are taken by value.
18    ///
19    /// $f(x, m) = y$, where $x, y < m$ and $x^2 \equiv y \mod m$.
20    ///
21    /// # Worst-case complexity
22    /// $T(n) = O(n \log n \log\log n)$
23    ///
24    /// $M(n) = O(n \log n)$
25    ///
26    /// where $T$ is time, $M$ is additional memory, and $n$ is `m.significant_bits()`.
27    ///
28    /// # Panics
29    /// Panics if `self` is greater than or equal to `m`.
30    ///
31    /// # Examples
32    /// ```
33    /// use malachite_base::num::arithmetic::traits::ModSquare;
34    /// use malachite_nz::natural::Natural;
35    ///
36    /// assert_eq!(Natural::from(2u32).mod_square(Natural::from(10u32)), 4);
37    /// assert_eq!(Natural::from(100u32).mod_square(Natural::from(497u32)), 60);
38    /// ```
39    fn mod_square(self, m: Self) -> Self {
40        (&self).mod_pow(&Self::TWO, &m)
41    }
42}
43
44impl ModSquare<&Self> for Natural {
45    type Output = Self;
46
47    /// Squares a [`Natural`] modulo another [`Natural`] $m$. The input must be already reduced
48    /// modulo $m$. The first [`Natural`] is taken by value and the second by reference.
49    ///
50    /// $f(x, m) = y$, where $x, y < m$ and $x^2 \equiv y \mod m$.
51    ///
52    /// # Worst-case complexity
53    /// $T(n) = O(n \log n \log\log n)$
54    ///
55    /// $M(n) = O(n \log n)$
56    ///
57    /// where $T$ is time, $M$ is additional memory, and $n$ is `m.significant_bits()`.
58    ///
59    /// # Panics
60    /// Panics if `self` is greater than or equal to `m`.
61    ///
62    /// # Examples
63    /// ```
64    /// use malachite_base::num::arithmetic::traits::ModSquare;
65    /// use malachite_nz::natural::Natural;
66    ///
67    /// assert_eq!(Natural::from(2u32).mod_square(&Natural::from(10u32)), 4);
68    /// assert_eq!(Natural::from(100u32).mod_square(&Natural::from(497u32)), 60);
69    /// ```
70    fn mod_square(self, m: &Self) -> Self {
71        (&self).mod_pow(&Self::TWO, m)
72    }
73}
74
75impl ModSquare<Natural> for &Natural {
76    type Output = Natural;
77
78    /// Squares a [`Natural`] modulo another [`Natural`] $m$. The input must be already reduced
79    /// modulo $m$. The first [`Natural`] is taken by reference and the second by value.
80    ///
81    /// $f(x, m) = y$, where $x, y < m$ and $x^2 \equiv y \mod m$.
82    ///
83    /// # Worst-case complexity
84    /// $T(n) = O(n \log n \log\log n)$
85    ///
86    /// $M(n) = O(n \log n)$
87    ///
88    /// where $T$ is time, $M$ is additional memory, and $n$ is `m.significant_bits()`.
89    ///
90    /// # Panics
91    /// Panics if `self` is greater than or equal to `m`.
92    ///
93    /// # Examples
94    /// ```
95    /// use malachite_base::num::arithmetic::traits::ModSquare;
96    /// use malachite_nz::natural::Natural;
97    ///
98    /// assert_eq!((&Natural::from(2u32)).mod_square(Natural::from(10u32)), 4);
99    /// assert_eq!(
100    ///     (&Natural::from(100u32)).mod_square(Natural::from(497u32)),
101    ///     60
102    /// );
103    /// ```
104    fn mod_square(self, m: Natural) -> Natural {
105        self.mod_pow(&Natural::TWO, &m)
106    }
107}
108
109impl ModSquare<&Natural> for &Natural {
110    type Output = Natural;
111
112    /// Squares a [`Natural`] modulo another [`Natural`] $m$. The input must be already reduced
113    /// modulo $m$. Both [`Natural`]s are taken by reference.
114    ///
115    /// $f(x, m) = y$, where $x, y < m$ and $x^2 \equiv y \mod m$.
116    ///
117    /// # Worst-case complexity
118    /// $T(n) = O(n \log n \log\log n)$
119    ///
120    /// $M(n) = O(n \log n)$
121    ///
122    /// where $T$ is time, $M$ is additional memory, and $n$ is `m.significant_bits()`.
123    ///
124    /// # Panics
125    /// Panics if `self` is greater than or equal to `m`.
126    ///
127    /// # Examples
128    /// ```
129    /// use malachite_base::num::arithmetic::traits::ModSquare;
130    /// use malachite_nz::natural::Natural;
131    ///
132    /// assert_eq!((&Natural::from(2u32)).mod_square(&Natural::from(10u32)), 4);
133    /// assert_eq!(
134    ///     (&Natural::from(100u32)).mod_square(&Natural::from(497u32)),
135    ///     60
136    /// );
137    /// ```
138    fn mod_square(self, m: &Natural) -> Natural {
139        self.mod_pow(&Natural::TWO, m)
140    }
141}
142
143impl ModSquareAssign<Self> for Natural {
144    /// Squares a [`Natural`] modulo another [`Natural`] $m$, in place. The input must be already
145    /// reduced modulo $m$. The [`Natural`] on the right-hand side is taken by value.
146    ///
147    /// $x \gets y$, where $x, y < m$ and $x^2 \equiv y \mod m$.
148    ///
149    /// # Worst-case complexity
150    /// $T(n) = O(n \log n \log\log n)$
151    ///
152    /// $M(n) = O(n \log n)$
153    ///
154    /// where $T$ is time, $M$ is additional memory, and $n$ is `m.significant_bits()`.
155    ///
156    /// # Panics
157    /// Panics if `self` is greater than or equal to `m`.
158    ///
159    /// # Examples
160    /// ```
161    /// use malachite_base::num::arithmetic::traits::ModSquareAssign;
162    /// use malachite_nz::natural::Natural;
163    ///
164    /// let mut x = Natural::from(2u32);
165    /// x.mod_square_assign(Natural::from(10u32));
166    /// assert_eq!(x, 4);
167    ///
168    /// let mut x = Natural::from(100u32);
169    /// x.mod_square_assign(Natural::from(497u32));
170    /// assert_eq!(x, 60);
171    /// ```
172    #[inline]
173    fn mod_square_assign(&mut self, m: Self) {
174        self.mod_pow_assign(&Self::TWO, &m);
175    }
176}
177
178impl ModSquareAssign<&Self> for Natural {
179    /// Squares a [`Natural`] modulo another [`Natural`] $m$, in place. The input must be already
180    /// reduced modulo $m$. The [`Natural`] on the right-hand side is taken by reference.
181    ///
182    /// $x \gets y$, where $x, y < m$ and $x^2 \equiv y \mod m$.
183    ///
184    /// # Worst-case complexity
185    /// $T(n) = O(n \log n \log\log n)$
186    ///
187    /// $M(n) = O(n \log n)$
188    ///
189    /// where $T$ is time, $M$ is additional memory, and $n$ is `m.significant_bits()`.
190    ///
191    /// # Panics
192    /// Panics if `self` is greater than or equal to `m`.
193    ///
194    /// # Examples
195    /// ```
196    /// use malachite_base::num::arithmetic::traits::ModSquareAssign;
197    /// use malachite_nz::natural::Natural;
198    ///
199    /// let mut x = Natural::from(2u32);
200    /// x.mod_square_assign(&Natural::from(10u32));
201    /// assert_eq!(x, 4);
202    ///
203    /// let mut x = Natural::from(100u32);
204    /// x.mod_square_assign(&Natural::from(497u32));
205    /// assert_eq!(x, 60);
206    /// ```
207    #[inline]
208    fn mod_square_assign(&mut self, m: &Self) {
209        self.mod_pow_assign(&Self::TWO, m);
210    }
211}
malachite_nz/natural/arithmetic/mod_square.rs

malachite_nz/natural/arithmetic/
mod_square.rs
