crypto_bigint/modular/
reduction.rs

1//! Modular reduction implementation.
2
3use crate::{Limb, Odd, Uint};
4
5/// Algorithm 14.32 in Handbook of Applied Cryptography <https://cacr.uwaterloo.ca/hac/about/chap14.pdf>
6#[inline(always)]
7const fn montgomery_reduction_inner(
8    upper: &mut [Limb],
9    lower: &mut [Limb],
10    modulus: &[Limb],
11    mod_neg_inv: Limb,
12) -> Limb {
13    let nlimbs = modulus.len();
14    debug_assert!(nlimbs == upper.len());
15    debug_assert!(nlimbs == lower.len());
16
17    let mut meta_carry = Limb::ZERO;
18    let mut new_sum;
19
20    let mut i = 0;
21    while i < nlimbs {
22        let u = lower[i].wrapping_mul(mod_neg_inv);
23
24        let (_, mut carry) = u.carrying_mul_add(modulus[0], lower[i], Limb::ZERO);
25        let mut new_limb;
26
27        let mut j = 1;
28        while j < (nlimbs - i) {
29            (new_limb, carry) = u.carrying_mul_add(modulus[j], lower[i + j], carry);
30            lower[i + j] = new_limb;
31            j += 1;
32        }
33        while j < nlimbs {
34            (new_limb, carry) = u.carrying_mul_add(modulus[j], upper[i + j - nlimbs], carry);
35            upper[i + j - nlimbs] = new_limb;
36            j += 1;
37        }
38
39        (new_sum, meta_carry) = upper[i].carrying_add(carry, meta_carry);
40        upper[i] = new_sum;
41
42        i += 1;
43    }
44
45    meta_carry
46}
47
48/// Algorithm 14.32 in Handbook of Applied Cryptography <https://cacr.uwaterloo.ca/hac/about/chap14.pdf>
49pub(crate) const fn montgomery_reduction<const LIMBS: usize>(
50    lower_upper: &(Uint<LIMBS>, Uint<LIMBS>),
51    modulus: &Odd<Uint<LIMBS>>,
52    mod_neg_inv: Limb,
53) -> Uint<LIMBS> {
54    let (mut lower, mut upper) = *lower_upper;
55    let meta_carry = montgomery_reduction_inner(
56        &mut upper.limbs,
57        &mut lower.limbs,
58        &modulus.as_ref().limbs,
59        mod_neg_inv,
60    );
61
62    // Division is simply taking the upper half of the limbs
63    // Final reduction (at this point, the value is at most 2 * modulus,
64    // so `meta_carry` is either 0 or 1)
65    upper.try_sub_with_carry(meta_carry, modulus.as_ref()).0
66}
67
68/// This algorithm corresponds to a Montgomery reduction of the wide input `(x, 0)`,
69/// Algorithm 14.32 in Handbook of Applied Cryptography <https://cacr.uwaterloo.ca/hac/about/chap14.pdf>
70/// Or to a Montgomery multiplication of `x` by `1` (Algorithm 14.36).
71/// This version does not produce a carry and does not need further correction by
72/// subtracting the modulus as long as `x < modulus`. This is guaranteed because
73/// `x < modulus => u < modulus => ((x + u•modulus) << N) < modulus`.
74#[inline(always)]
75pub const fn montgomery_retrieve_inner(
76    x: &[Limb],
77    out: &mut [Limb],
78    modulus: &[Limb],
79    mod_neg_inv: Limb,
80) {
81    let nlimbs = modulus.len();
82    assert!(nlimbs == x.len() && nlimbs == out.len());
83
84    let mut i = 0;
85    while i < nlimbs {
86        let xi = x[i];
87        let u = out[0].wrapping_add(xi).wrapping_mul(mod_neg_inv);
88
89        out[0] = u.carrying_mul_add(modulus[0], xi, out[0]).1;
90
91        let mut j = 1;
92        while j < nlimbs {
93            (out[j - 1], out[j]) = u.carrying_mul_add(modulus[j], out[j], out[j - 1]);
94            j += 1;
95        }
96
97        i += 1;
98    }
99}
100
101/// For input `x < modulus` in Montgomery form, compute `x•R^-1 mod modulus`.
102pub const fn montgomery_retrieve<const LIMBS: usize>(
103    montgomery_form: &Uint<LIMBS>,
104    modulus: &Odd<Uint<LIMBS>>,
105    mod_neg_inv: Limb,
106) -> Uint<LIMBS> {
107    debug_assert!(Uint::lt(montgomery_form, modulus.as_ref()).to_bool_vartime());
108    let mut res = Uint::ZERO;
109    montgomery_retrieve_inner(
110        montgomery_form.as_limbs(),
111        res.as_mut_limbs(),
112        modulus.as_ref().as_limbs(),
113        mod_neg_inv,
114    );
115    res
116}
crypto_bigint/modular/reduction.rs

crypto_bigint/modular/
reduction.rs
