crypto_bigint/uint/boxed/
sqrt.rs

1//! [`BoxedUint`] square root operations.
2
3use crate::{BoxedUint, CheckedSquareRoot, Choice, CtOption, FloorSquareRoot, NonZero};
4
5impl BoxedUint {
6    /// Computes `floor(√(self))` in constant time.
7    ///
8    /// Callers can check if `self` is a square by squaring the result.
9    #[deprecated(since = "0.7.0", note = "please use `floor_sqrt` instead")]
10    #[must_use]
11    pub fn sqrt(&self) -> Self {
12        self.floor_sqrt()
13    }
14
15    /// Computes √(`self`) in constant time.
16    ///
17    /// Callers can check if `self` is a square by squaring the result, or use
18    /// `checked_sqrt`.
19    #[must_use]
20    pub fn floor_sqrt(&self) -> Self {
21        let mut root = self.clone();
22        root.floor_sqrt_assign();
23        root
24    }
25
26    /// Computes `floor(√(self))`.
27    ///
28    /// Callers can check if `self` is a square by squaring the result.
29    ///
30    /// Variable time with respect to `self`.
31    #[deprecated(since = "0.7.0", note = "please use `floor_sqrt_vartime` instead")]
32    #[must_use]
33    pub fn sqrt_vartime(&self) -> Self {
34        self.floor_sqrt_vartime()
35    }
36
37    /// Computes √(`self`).
38    ///
39    /// Callers can check if `self` is a square by squaring the result, or use
40    /// `checked_sqrt_vartime`.
41    ///
42    /// Variable time with respect to `self`.
43    #[must_use]
44    pub fn floor_sqrt_vartime(&self) -> Self {
45        let mut root = self.clone();
46        root.floor_sqrt_assign_vartime();
47        root
48    }
49
50    /// Wrapped sqrt is just `floor(√(self))`.
51    /// There’s no way wrapping could ever happen.
52    /// This function exists so that all operations are accounted for in the wrapping operations.
53    #[must_use]
54    pub fn wrapping_sqrt(&self) -> Self {
55        self.floor_sqrt()
56    }
57
58    /// Wrapped sqrt is just `floor(√(self))`.
59    /// There’s no way wrapping could ever happen.
60    /// This function exists so that all operations are accounted for in the wrapping operations.
61    ///
62    /// Variable time with respect to `self`.
63    #[must_use]
64    pub fn wrapping_sqrt_vartime(&self) -> Self {
65        self.floor_sqrt_vartime()
66    }
67
68    /// Perform checked sqrt, returning a [`CtOption`] which `is_some`
69    /// only if the square root is exact.
70    #[must_use]
71    pub fn checked_sqrt(&self) -> CtOption<Self> {
72        let mut root = self.clone();
73        let exact = root.floor_sqrt_assign();
74        CtOption::new(root, exact)
75    }
76
77    /// Perform checked sqrt, returning an [`Option`] which `is_some`
78    /// only if the square root is exact.
79    ///
80    /// Variable time with respect to `self`.
81    #[must_use]
82    pub fn checked_sqrt_vartime(&self) -> Option<Self> {
83        let mut root = self.clone();
84        if root.floor_sqrt_assign_vartime() {
85            Some(root)
86        } else {
87            None
88        }
89    }
90
91    /// Assigns `floor(√(self))` to `self` in constant time, and returns a [`Choice`]
92    /// indicating whether the square root is exact.
93    fn floor_sqrt_assign(&mut self) -> Choice {
94        let size = self.nlimbs();
95        let mut buf = Self::zero_with_precision(self.bits_precision() * 2);
96        self.as_mut_uint_ref()
97            .sqrt_assign(buf.as_mut_uint_ref().split_at_mut(size))
98    }
99
100    /// Assigns `floor(√(self))` to `self`, and returns a [`bool`]
101    /// indicating whether the square root is exact.
102    ///
103    /// Variable time with respect to `self`.
104    pub fn floor_sqrt_assign_vartime(&mut self) -> bool {
105        let size = self.nlimbs();
106        let mut buf = Self::zero_with_precision(self.bits_precision() * 2);
107        self.as_mut_uint_ref()
108            .sqrt_assign_vartime(buf.as_mut_uint_ref().split_at_mut(size))
109    }
110}
111
112impl CheckedSquareRoot for BoxedUint {
113    type Output = Self;
114
115    fn checked_sqrt(&self) -> CtOption<Self::Output> {
116        self.checked_sqrt()
117    }
118
119    fn checked_sqrt_vartime(&self) -> Option<Self::Output> {
120        self.checked_sqrt_vartime()
121    }
122}
123
124impl FloorSquareRoot for BoxedUint {
125    fn floor_sqrt(&self) -> Self {
126        self.floor_sqrt()
127    }
128
129    fn floor_sqrt_vartime(&self) -> Self {
130        self.floor_sqrt_vartime()
131    }
132}
133
134impl CheckedSquareRoot for NonZero<BoxedUint> {
135    type Output = Self;
136
137    fn checked_sqrt(&self) -> CtOption<Self> {
138        self.as_ref().checked_sqrt().map(NonZero::new_unchecked)
139    }
140
141    fn checked_sqrt_vartime(&self) -> Option<Self> {
142        self.as_ref()
143            .checked_sqrt_vartime()
144            .map(NonZero::new_unchecked)
145    }
146}
147
148impl FloorSquareRoot for NonZero<BoxedUint> {
149    fn floor_sqrt(&self) -> Self {
150        NonZero::new_unchecked(self.as_ref().floor_sqrt())
151    }
152
153    fn floor_sqrt_vartime(&self) -> Self {
154        NonZero::new_unchecked(self.as_ref().floor_sqrt_vartime())
155    }
156}
157
158#[cfg(test)]
159#[allow(clippy::integer_division_remainder_used, reason = "test")]
160mod tests {
161    use crate::{BoxedUint, CheckedSquareRoot, FloorSquareRoot, Limb};
162
163    #[cfg(feature = "rand_core")]
164    use {
165        crate::RandomBits,
166        chacha20::ChaCha8Rng,
167        rand_core::{Rng, SeedableRng},
168    };
169
170    #[test]
171    fn edge() {
172        assert_eq!(
173            BoxedUint::zero_with_precision(256).floor_sqrt(),
174            BoxedUint::zero_with_precision(256)
175        );
176        assert_eq!(
177            BoxedUint::one_with_precision(256).floor_sqrt(),
178            BoxedUint::one_with_precision(256)
179        );
180        let mut half = BoxedUint::zero_with_precision(256);
181        for i in 0..half.limbs.len() / 2 {
182            half.limbs[i] = Limb::MAX;
183        }
184        let u256_max = BoxedUint::max(256);
185        assert_eq!(u256_max.floor_sqrt(), half);
186
187        // Test edge cases that use up the maximum number of iterations.
188
189        // `x = (r + 1)^2 - 583`, where `r` is the expected square root.
190        assert_eq!(
191            BoxedUint::from_be_hex("055fa39422bd9f281762946e056535badbf8a6864d45fa3d", 192)
192                .unwrap()
193                .floor_sqrt(),
194            BoxedUint::from_be_hex("0000000000000000000000002516f0832a538b2d98869e21", 192)
195                .unwrap(),
196        );
197        assert_eq!(
198            BoxedUint::from_be_hex("055fa39422bd9f281762946e056535badbf8a6864d45fa3d", 192)
199                .unwrap()
200                .floor_sqrt_vartime(),
201            BoxedUint::from_be_hex("0000000000000000000000002516f0832a538b2d98869e21", 192)
202                .unwrap()
203        );
204
205        // `x = (r + 1)^2 - 205`, where `r` is the expected square root.
206        assert_eq!(
207            BoxedUint::from_be_hex(
208                "4bb750738e25a8f82940737d94a48a91f8cd918a3679ff90c1a631f2bd6c3597",
209                256
210            )
211            .unwrap()
212            .floor_sqrt(),
213            BoxedUint::from_be_hex(
214                "000000000000000000000000000000008b3956339e8315cff66eb6107b610075",
215                256
216            )
217            .unwrap()
218        );
219        assert_eq!(
220            BoxedUint::from_be_hex(
221                "4bb750738e25a8f82940737d94a48a91f8cd918a3679ff90c1a631f2bd6c3597",
222                256
223            )
224            .unwrap()
225            .floor_sqrt_vartime(),
226            BoxedUint::from_be_hex(
227                "000000000000000000000000000000008b3956339e8315cff66eb6107b610075",
228                256
229            )
230            .unwrap()
231        );
232    }
233
234    #[test]
235    fn edge_vartime() {
236        assert_eq!(
237            BoxedUint::zero_with_precision(256).floor_sqrt_vartime(),
238            BoxedUint::zero_with_precision(256)
239        );
240        assert_eq!(
241            BoxedUint::one_with_precision(256).floor_sqrt_vartime(),
242            BoxedUint::one_with_precision(256)
243        );
244        let mut half = BoxedUint::zero_with_precision(256);
245        for i in 0..half.limbs.len() / 2 {
246            half.limbs[i] = Limb::MAX;
247        }
248        let u256_max = !BoxedUint::zero_with_precision(256);
249        assert_eq!(u256_max.floor_sqrt_vartime(), half);
250    }
251
252    #[test]
253    fn simple() {
254        let tests = [
255            (4u8, 2u8),
256            (9, 3),
257            (16, 4),
258            (25, 5),
259            (36, 6),
260            (49, 7),
261            (64, 8),
262            (81, 9),
263            (100, 10),
264            (121, 11),
265            (144, 12),
266            (169, 13),
267        ];
268        for (a, e) in &tests {
269            let l = BoxedUint::from(*a);
270            let r = BoxedUint::from(*e);
271            assert_eq!(l.floor_sqrt(), r);
272            assert_eq!(l.floor_sqrt_vartime(), r);
273            assert_eq!(
274                CheckedSquareRoot::checked_sqrt(&l).into_option().as_ref(),
275                Some(&r)
276            );
277            assert_eq!(
278                CheckedSquareRoot::checked_sqrt_vartime(&l).as_ref(),
279                Some(&r)
280            );
281            let nz_l = l.as_nz_vartime().unwrap();
282            let nz_r = r.to_nz().unwrap();
283            assert_eq!(FloorSquareRoot::floor_sqrt(nz_l), nz_r);
284            assert_eq!(FloorSquareRoot::floor_sqrt_vartime(nz_l), nz_r);
285            assert_eq!(
286                CheckedSquareRoot::checked_sqrt(nz_l).into_option().as_ref(),
287                Some(&nz_r)
288            );
289            assert_eq!(
290                CheckedSquareRoot::checked_sqrt_vartime(nz_l).as_ref(),
291                Some(&nz_r)
292            );
293        }
294    }
295
296    #[test]
297    fn nonsquares() {
298        assert_eq!(BoxedUint::from(2u8).floor_sqrt(), BoxedUint::from(1u8));
299        assert!(!BoxedUint::from(2u8).checked_sqrt().is_some().to_bool());
300        assert_eq!(BoxedUint::from(3u8).floor_sqrt(), BoxedUint::from(1u8));
301        assert!(!BoxedUint::from(3u8).checked_sqrt().is_some().to_bool());
302        assert_eq!(BoxedUint::from(5u8).floor_sqrt(), BoxedUint::from(2u8));
303        assert_eq!(BoxedUint::from(6u8).floor_sqrt(), BoxedUint::from(2u8));
304        assert_eq!(BoxedUint::from(7u8).floor_sqrt(), BoxedUint::from(2u8));
305        assert_eq!(BoxedUint::from(8u8).floor_sqrt(), BoxedUint::from(2u8));
306        assert_eq!(BoxedUint::from(10u8).floor_sqrt(), BoxedUint::from(3u8));
307    }
308
309    #[test]
310    fn nonsquares_vartime() {
311        assert_eq!(
312            BoxedUint::from(2u8).floor_sqrt_vartime(),
313            BoxedUint::from(1u8)
314        );
315        assert!(BoxedUint::from(2u8).checked_sqrt_vartime().is_none());
316        assert_eq!(
317            BoxedUint::from(3u8).floor_sqrt_vartime(),
318            BoxedUint::from(1u8)
319        );
320        assert!(BoxedUint::from(3u8).checked_sqrt_vartime().is_none());
321        assert_eq!(
322            BoxedUint::from(5u8).floor_sqrt_vartime(),
323            BoxedUint::from(2u8)
324        );
325        assert_eq!(
326            BoxedUint::from(6u8).floor_sqrt_vartime(),
327            BoxedUint::from(2u8)
328        );
329        assert_eq!(
330            BoxedUint::from(7u8).floor_sqrt_vartime(),
331            BoxedUint::from(2u8)
332        );
333        assert_eq!(
334            BoxedUint::from(8u8).floor_sqrt_vartime(),
335            BoxedUint::from(2u8)
336        );
337        assert_eq!(
338            BoxedUint::from(10u8).floor_sqrt_vartime(),
339            BoxedUint::from(3u8)
340        );
341    }
342
343    #[cfg(feature = "rand_core")]
344    #[test]
345    fn fuzz() {
346        use crate::ConcatenatingSquare;
347
348        let mut rng = ChaCha8Rng::from_seed([7u8; 32]);
349        let rounds = if cfg!(miri) { 10 } else { 50 };
350        for _ in 0..rounds {
351            let t = u64::from(rng.next_u32());
352            let s = BoxedUint::from(t);
353            let s2 = s.checked_mul(&s).unwrap();
354            assert_eq!(s2.floor_sqrt(), s);
355            assert_eq!(s2.floor_sqrt_vartime(), s);
356            assert!(CheckedSquareRoot::checked_sqrt(&s2).is_some().to_bool());
357            assert!(CheckedSquareRoot::checked_sqrt_vartime(&s2).is_some());
358        }
359
360        for _ in 0..rounds {
361            let s = BoxedUint::random_bits(&mut rng, 512);
362            let mut s2 = BoxedUint::zero_with_precision(512);
363            s2.limbs[..s.limbs.len()].copy_from_slice(&s.limbs);
364            assert_eq!(s.concatenating_square().floor_sqrt(), s2);
365            assert_eq!(s.concatenating_square().floor_sqrt_vartime(), s2);
366        }
367    }
368}
crypto_bigint/uint/boxed/sqrt.rs

crypto_bigint/uint/boxed/
sqrt.rs
