crypto_bigint/modular/
lincomb.rs

1use crate::{modular::MontyForm, Limb, Odd, Uint};
2
3use super::{ConstMontyForm, ConstMontyParams};
4
5#[cfg(feature = "alloc")]
6use super::BoxedMontyForm;
7#[cfg(feature = "alloc")]
8use crate::BoxedUint;
9
10/// Implement the coarse interleaved sum of products (Algorithm 2 for B=1) from
11/// Efficient Algorithms for Large Prime Characteristic Fields and Their Application
12/// to Bilinear Pairings by Patrick Longa. https://eprint.iacr.org/2022/367
13///
14/// For correct results, the un-reduced sum of products must not exceed `p•R`  where `p`
15/// is the modulus. Given a list of pairs `(a_1, b_1)..(a_k, b_k)` in Montgomery form,
16/// where each `a_i < p` and `b_i < p`, we have `sum(a_i•b_i) < k•p^2` and so up to
17/// `k = floor(R/p)` pairs may be safely accumulated per call.
18///
19/// This is implemented as a macro to abstract over `const fn` and boxed use cases, since the latter
20/// needs mutable references and thus the unstable `const_mut_refs` feature (rust-lang/rust#57349).
21///
22// TODO: change this into a `const fn` when `const_mut_refs` is stable
23macro_rules! impl_longa_monty_lincomb {
24    ($a_b:expr, $u:expr, $modulus:expr, $mod_neg_inv:expr, $nlimbs:expr) => {{
25        let len = $a_b.len();
26        let mut hi_carry = Limb::ZERO;
27        let mut hi;
28        let mut carry;
29
30        let mut j = 0;
31        while j < $nlimbs {
32            hi = hi_carry;
33            hi_carry = Limb::ZERO;
34
35            let mut i = 0;
36            while i < len {
37                let (ai, bi) = &$a_b[i];
38                carry = Limb::ZERO;
39
40                let mut k = 0;
41                while k < $nlimbs {
42                    ($u[k], carry) = $u[k].mac(
43                        ai.as_montgomery().limbs[j],
44                        bi.as_montgomery().limbs[k],
45                        carry,
46                    );
47                    k += 1;
48                }
49                (hi, carry) = hi.adc(carry, Limb::ZERO);
50                hi_carry = hi_carry.wrapping_add(carry);
51
52                i += 1;
53            }
54
55            let q = $u[0].wrapping_mul($mod_neg_inv);
56
57            (_, carry) = $u[0].mac(q, $modulus[0], Limb::ZERO);
58
59            i = 1;
60            while i < $nlimbs {
61                ($u[i - 1], carry) = $u[i].mac(q, $modulus[i], carry);
62                i += 1;
63            }
64            ($u[$nlimbs - 1], carry) = hi.adc(carry, Limb::ZERO);
65            hi_carry = hi_carry.wrapping_add(carry);
66
67            j += 1;
68        }
69
70        hi_carry
71    }};
72}
73
74pub const fn lincomb_const_monty_form<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize>(
75    mut products: &[(ConstMontyForm<MOD, LIMBS>, ConstMontyForm<MOD, LIMBS>)],
76    modulus: &Odd<Uint<LIMBS>>,
77    mod_neg_inv: Limb,
78) -> Uint<LIMBS> {
79    let max_accum = 1 << (MOD::MOD_LEADING_ZEROS as usize);
80    let mut ret = Uint::ZERO;
81    let mut remain = products.len();
82    if remain <= max_accum {
83        let carry =
84            impl_longa_monty_lincomb!(products, ret.limbs, modulus.0.limbs, mod_neg_inv, LIMBS);
85        ret.sub_mod_with_carry(carry, &modulus.0, &modulus.0)
86    } else {
87        let mut window;
88        while remain > 0 {
89            let mut buf = Uint::ZERO;
90            let mut count = remain;
91            if count > max_accum {
92                count = max_accum;
93            }
94            (window, products) = products.split_at(count);
95            let carry =
96                impl_longa_monty_lincomb!(window, buf.limbs, modulus.0.limbs, mod_neg_inv, LIMBS);
97            buf = buf.sub_mod_with_carry(carry, &modulus.0, &modulus.0);
98            ret = ret.add_mod(&buf, &modulus.0);
99            remain -= count;
100        }
101        ret
102    }
103}
104
105pub const fn lincomb_monty_form<const LIMBS: usize>(
106    mut products: &[(&MontyForm<LIMBS>, &MontyForm<LIMBS>)],
107    modulus: &Odd<Uint<LIMBS>>,
108    mod_neg_inv: Limb,
109    mod_leading_zeros: u32,
110) -> Uint<LIMBS> {
111    let max_accum = 1 << (mod_leading_zeros as usize);
112    let mut ret = Uint::ZERO;
113    let mut remain = products.len();
114    if remain <= max_accum {
115        let carry =
116            impl_longa_monty_lincomb!(products, ret.limbs, modulus.0.limbs, mod_neg_inv, LIMBS);
117        ret.sub_mod_with_carry(carry, &modulus.0, &modulus.0)
118    } else {
119        let mut window;
120        while remain > 0 {
121            let mut count = remain;
122            if count > max_accum {
123                count = max_accum;
124            }
125            (window, products) = products.split_at(count);
126            let mut buf = Uint::ZERO;
127            let carry =
128                impl_longa_monty_lincomb!(window, buf.limbs, modulus.0.limbs, mod_neg_inv, LIMBS);
129            buf = buf.sub_mod_with_carry(carry, &modulus.0, &modulus.0);
130            ret = ret.add_mod(&buf, &modulus.0);
131            remain -= count;
132        }
133        ret
134    }
135}
136
137#[cfg(feature = "alloc")]
138pub fn lincomb_boxed_monty_form(
139    mut products: &[(&BoxedMontyForm, &BoxedMontyForm)],
140    modulus: &Odd<BoxedUint>,
141    mod_neg_inv: Limb,
142    mod_leading_zeros: u32,
143) -> BoxedUint {
144    let max_accum = 1 << (mod_leading_zeros as usize);
145    let nlimbs = modulus.0.nlimbs();
146    let mut ret = BoxedUint::zero_with_precision(modulus.0.bits_precision());
147    let mut remain = products.len();
148    if remain <= max_accum {
149        let carry =
150            impl_longa_monty_lincomb!(products, ret.limbs, modulus.0.limbs, mod_neg_inv, nlimbs);
151        ret.sub_assign_mod_with_carry(carry, &modulus.0, &modulus.0);
152    } else {
153        let mut window;
154        let mut buf = BoxedUint::zero_with_precision(modulus.0.bits_precision());
155        while remain > 0 {
156            buf.limbs.fill(Limb::ZERO);
157            let mut count = remain;
158            if count > max_accum {
159                count = max_accum;
160            }
161            (window, products) = products.split_at(count);
162            let carry =
163                impl_longa_monty_lincomb!(window, buf.limbs, modulus.0.limbs, mod_neg_inv, nlimbs);
164            buf.sub_assign_mod_with_carry(carry, &modulus.0, &modulus.0);
165            let carry = ret.adc_assign(&buf, Limb::ZERO);
166            ret.sub_assign_mod_with_carry(carry, &modulus.0, &modulus.0);
167            remain -= count;
168        }
169    }
170    ret
171}
crypto_bigint/modular/lincomb.rs

crypto_bigint/modular/
lincomb.rs
