crypto_bigint/modular/
div_by_2.rs

1#[cfg(feature = "alloc")]
2use crate::{BoxedUint, Integer};
3use crate::{Limb, 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
14    // Note that this also works if `a` is a Montgomery representation modulo `modulus`
15    // of some integer `x`.
16    // If `b + b = a mod modulus` it means that `y + y = x mod modulus` where `y` is the integer
17    // whose Montgomery representation is `b`.
18
19    let is_odd = a.is_odd();
20    let (if_odd, carry) = a.carrying_add(modulus.as_ref(), Limb::ZERO);
21    let carry = Limb::select(Limb::ZERO, carry, is_odd);
22    Uint::<LIMBS>::select(a, &if_odd, is_odd)
23        .shr1()
24        .set_bit(Uint::<LIMBS>::BITS - 1, carry.is_nonzero())
25}
26
27#[cfg(feature = "alloc")]
28pub(crate) fn div_by_2_boxed(a: &BoxedUint, modulus: &Odd<BoxedUint>) -> BoxedUint {
29    let mut result = a.clone();
30    div_by_2_boxed_assign(&mut result, modulus);
31    result
32}
33
34#[cfg(feature = "alloc")]
35pub(crate) fn div_by_2_boxed_assign(a: &mut BoxedUint, modulus: &Odd<BoxedUint>) {
36    debug_assert_eq!(a.bits_precision(), modulus.bits_precision());
37
38    let is_odd = a.is_odd();
39    let carry = a.conditional_carrying_add_assign(modulus, is_odd);
40    a.shr1_assign();
41    a.set_bit(a.bits_precision() - 1, carry);
42}
crypto_bigint/modular/div_by_2.rs

crypto_bigint/modular/
div_by_2.rs
