crypto_bigint/modular/
div_by_2.rs

1#[cfg(feature = "alloc")]
2use crate::{BoxedUint, ConstantTimeSelect};
3use crate::{Odd, Uint};
4
5pub(crate) const fn div_by_2<const LIMBS: usize>(
6    a: &Uint<LIMBS>,
7    modulus: &Odd<Uint<LIMBS>>,
8) -> Uint<LIMBS> {
9    // We are looking for such `b` that `b + b = a mod modulus`.
10    // Two possibilities:
11    // - if `a` is even, we can just divide by 2;
12    // - if `a` is odd, we divide `(a + modulus)` by 2.
13    // To stay within the modulus we open the parentheses turning it into `a / 2 + modulus / 2 + 1`
14    // ("+1" because both `a` and `modulus` are odd, we lose 0.5 in each integer division).
15    // This will not overflow, so we can just use wrapping operations.
16
17    // Note that this also works if `a` is a Montgomery representation modulo `modulus`
18    // of some integer `x`.
19    // If `b + b = a mod modulus` it means that `y + y = x mod modulus` where `y` is the integer
20    // whose Montgomery representation is `b`.
21
22    let (half, is_odd) = a.shr1_with_carry();
23    let half_modulus = modulus.0.shr1();
24
25    let if_even = half;
26    let if_odd = half
27        .wrapping_add(&half_modulus)
28        .wrapping_add(&Uint::<LIMBS>::ONE);
29
30    Uint::<LIMBS>::select(&if_even, &if_odd, is_odd)
31}
32
33#[cfg(feature = "alloc")]
34pub(crate) fn div_by_2_boxed(a: &BoxedUint, modulus: &Odd<BoxedUint>) -> BoxedUint {
35    debug_assert_eq!(a.bits_precision(), modulus.bits_precision());
36
37    let (mut half, is_odd) = a.shr1_with_carry();
38    let half_modulus = modulus.shr1();
39
40    let if_odd = half
41        .wrapping_add(&half_modulus)
42        .wrapping_add(&BoxedUint::one_with_precision(a.bits_precision()));
43
44    half.ct_assign(&if_odd, is_odd);
45
46    half
47}
crypto_bigint/modular/div_by_2.rs

crypto_bigint/modular/
div_by_2.rs
