crypto_bigint/uint/modular/
div_by_2.rs

1use crate::Uint;
2
3pub(crate) fn div_by_2<const LIMBS: usize>(a: &Uint<LIMBS>, modulus: &Uint<LIMBS>) -> Uint<LIMBS> {
4    // We are looking for such `x` that `x * 2 = y mod modulus`,
5    // where the given `a = M(y)` is the Montgomery representation of some `y`.
6    // This means that in Montgomery representation it would still apply:
7    // `M(x) + M(x) = a mod modulus`.
8    // So we can just forget about Montgomery representation, and return whatever is
9    // `a` divided by 2, and this will be the Montgomery representation of `x`.
10    // (Which means that this function works regardless of whether `a`
11    // is in Montgomery representation or not, but the algorithm below
12    // does need `modulus` to be odd)
13
14    // Two possibilities:
15    // - if `a` is even, we can just divide by 2;
16    // - if `a` is odd, we divide `(a + modulus)` by 2.
17    // To stay within the modulus we open the parentheses turning it into `a / 2 + modulus / 2 + 1`
18    // ("+1" because both `a` and `modulus` are odd, we lose 0.5 in each integer division).
19    // This will not overflow, so we can just use wrapping operations.
20
21    let (half, is_odd) = a.shr_1();
22    let half_modulus = modulus.shr_vartime(1);
23
24    let if_even = half;
25    let if_odd = half
26        .wrapping_add(&half_modulus)
27        .wrapping_add(&Uint::<LIMBS>::ONE);
28
29    Uint::<LIMBS>::ct_select(&if_even, &if_odd, is_odd)
30}