crypto_bigint/modular/
reduction.rs

1//! Modular reduction implementation.
2
3use crate::{Limb, Odd, Uint};
4
5#[cfg(feature = "alloc")]
6use {crate::BoxedUint, subtle::Choice};
7
8/// Algorithm 14.32 in Handbook of Applied Cryptography <https://cacr.uwaterloo.ca/hac/about/chap14.pdf>
9const fn montgomery_reduction_inner(
10    upper: &mut [Limb],
11    lower: &mut [Limb],
12    modulus: &[Limb],
13    mod_neg_inv: Limb,
14) -> Limb {
15    let nlimbs = modulus.len();
16    debug_assert!(nlimbs == upper.len());
17    debug_assert!(nlimbs == lower.len());
18
19    let mut meta_carry = Limb::ZERO;
20    let mut new_sum;
21
22    let mut i = 0;
23    while i < nlimbs {
24        let u = lower[i].wrapping_mul(mod_neg_inv);
25
26        let (_, mut carry) = lower[i].mac(u, modulus[0], Limb::ZERO);
27        let mut new_limb;
28
29        let mut j = 1;
30        while j < (nlimbs - i) {
31            (new_limb, carry) = lower[i + j].mac(u, modulus[j], carry);
32            lower[i + j] = new_limb;
33            j += 1;
34        }
35        while j < nlimbs {
36            (new_limb, carry) = upper[i + j - nlimbs].mac(u, modulus[j], carry);
37            upper[i + j - nlimbs] = new_limb;
38            j += 1;
39        }
40
41        (new_sum, meta_carry) = upper[i].adc(carry, meta_carry);
42        upper[i] = new_sum;
43
44        i += 1;
45    }
46
47    meta_carry
48}
49
50/// Algorithm 14.32 in Handbook of Applied Cryptography <https://cacr.uwaterloo.ca/hac/about/chap14.pdf>
51pub const fn montgomery_reduction<const LIMBS: usize>(
52    lower_upper: &(Uint<LIMBS>, Uint<LIMBS>),
53    modulus: &Odd<Uint<LIMBS>>,
54    mod_neg_inv: Limb,
55) -> Uint<LIMBS> {
56    let (mut lower, mut upper) = *lower_upper;
57    let meta_carry = montgomery_reduction_inner(
58        &mut upper.limbs,
59        &mut lower.limbs,
60        &modulus.0.limbs,
61        mod_neg_inv,
62    );
63
64    // Division is simply taking the upper half of the limbs
65    // Final reduction (at this point, the value is at most 2 * modulus,
66    // so `meta_carry` is either 0 or 1)
67    upper.sub_mod_with_carry(meta_carry, &modulus.0, &modulus.0)
68}
69
70/// Algorithm 14.32 in Handbook of Applied Cryptography <https://cacr.uwaterloo.ca/hac/about/chap14.pdf>
71///
72/// This version writes the result into the provided [`BoxedUint`].
73#[cfg(feature = "alloc")]
74pub(crate) fn montgomery_reduction_boxed_mut(
75    x: &mut BoxedUint,
76    modulus: &BoxedUint,
77    mod_neg_inv: Limb,
78    out: &mut BoxedUint,
79) {
80    debug_assert_eq!(x.nlimbs(), modulus.nlimbs() * 2);
81    debug_assert_eq!(out.nlimbs(), modulus.nlimbs());
82
83    let (lower, upper) = x.limbs.split_at_mut(modulus.nlimbs());
84    let meta_carry = montgomery_reduction_inner(upper, lower, &modulus.limbs, mod_neg_inv);
85
86    out.limbs.copy_from_slice(upper);
87    let borrow = out.sbb_assign(modulus, Limb::ZERO);
88
89    // The new `borrow = Word::MAX` iff `carry == 0` and `borrow == Word::MAX`.
90    let borrow = Limb((!meta_carry.0.wrapping_neg()) & borrow.0);
91
92    // If underflow occurred on the final limb, borrow = 0xfff...fff, otherwise
93    // borrow = 0x000...000. Thus, we use it as a mask to conditionally add the modulus.
94    out.conditional_adc_assign(modulus, Choice::from((borrow.0 & 1) as u8));
95}
96
97/// Algorithm 14.32 in Handbook of Applied Cryptography <https://cacr.uwaterloo.ca/hac/about/chap14.pdf>
98///
99/// This version allocates and returns a [`BoxedUint`].
100#[cfg(feature = "alloc")]
101#[inline]
102pub(crate) fn montgomery_reduction_boxed(
103    x: &mut BoxedUint,
104    modulus: &BoxedUint,
105    mod_neg_inv: Limb,
106) -> BoxedUint {
107    let mut ret = BoxedUint::zero_with_precision(modulus.bits_precision());
108    montgomery_reduction_boxed_mut(x, modulus, mod_neg_inv, &mut ret);
109    ret
110}
crypto_bigint/modular/reduction.rs

crypto_bigint/modular/
reduction.rs
