crypto_bigint/modular/
lincomb.rs

1use crate::{Limb, Odd, Uint, modular::FixedMontyForm, primitives::u32_min};
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) = ai.as_montgomery().limbs[j].carrying_mul_add(
43                        bi.as_montgomery().limbs[k],
44                        $u[k],
45                        carry,
46                    );
47                    k += 1;
48                }
49                (hi, carry) = hi.carrying_add(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) = q.carrying_mul_add($modulus[0], $u[0], Limb::ZERO);
58
59            i = 1;
60            while i < $nlimbs {
61                ($u[i - 1], carry) = q.carrying_mul_add($modulus[i], $u[i], carry);
62                i += 1;
63            }
64            ($u[$nlimbs - 1], carry) = hi.carrying_add(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 << u32_min(MOD::PARAMS.mod_leading_zeros, usize::BITS - 1);
80    let mut ret = Uint::ZERO;
81    let mut remain = products.len();
82    if remain <= max_accum {
83        let carry = impl_longa_monty_lincomb!(
84            products,
85            ret.limbs,
86            modulus.as_ref().limbs,
87            mod_neg_inv,
88            LIMBS
89        );
90        ret.try_sub_with_carry(carry, modulus.as_ref()).0
91    } else {
92        let mut window;
93        while remain > 0 {
94            let mut buf = Uint::ZERO;
95            let mut count = remain;
96            if count > max_accum {
97                count = max_accum;
98            }
99            (window, products) = products.split_at(count);
100            let carry = impl_longa_monty_lincomb!(
101                window,
102                buf.limbs,
103                modulus.as_ref().limbs,
104                mod_neg_inv,
105                LIMBS
106            );
107            buf = buf.try_sub_with_carry(carry, modulus.as_ref()).0;
108            ret = ret.add_mod(&buf, modulus.as_nz_ref());
109            remain -= count;
110        }
111        ret
112    }
113}
114
115pub const fn lincomb_monty_form<const LIMBS: usize>(
116    mut products: &[(&FixedMontyForm<LIMBS>, &FixedMontyForm<LIMBS>)],
117    modulus: &Odd<Uint<LIMBS>>,
118    mod_neg_inv: Limb,
119    mod_leading_zeros: u32,
120) -> Uint<LIMBS> {
121    let max_accum = 1 << u32_min(mod_leading_zeros, usize::BITS - 1);
122    let mut ret = Uint::ZERO;
123    let mut remain = products.len();
124    if remain <= max_accum {
125        let carry = impl_longa_monty_lincomb!(
126            products,
127            ret.limbs,
128            modulus.as_ref().limbs,
129            mod_neg_inv,
130            LIMBS
131        );
132        ret.try_sub_with_carry(carry, modulus.as_ref()).0
133    } else {
134        let mut window;
135        while remain > 0 {
136            let mut count = remain;
137            if count > max_accum {
138                count = max_accum;
139            }
140            (window, products) = products.split_at(count);
141            let mut buf = Uint::ZERO;
142            let carry = impl_longa_monty_lincomb!(
143                window,
144                buf.limbs,
145                modulus.as_ref().limbs,
146                mod_neg_inv,
147                LIMBS
148            );
149            buf = buf.try_sub_with_carry(carry, modulus.as_ref()).0;
150            ret = ret.add_mod(&buf, modulus.as_nz_ref());
151            remain -= count;
152        }
153        ret
154    }
155}
156
157#[cfg(feature = "alloc")]
158pub fn lincomb_boxed_monty_form(
159    mut products: &[(&BoxedMontyForm, &BoxedMontyForm)],
160    modulus: &Odd<BoxedUint>,
161    mod_neg_inv: Limb,
162    mod_leading_zeros: u32,
163) -> BoxedUint {
164    let max_accum = 1 << u32_min(mod_leading_zeros, usize::BITS - 1);
165    let nlimbs = modulus.as_ref().nlimbs();
166    let mut ret = BoxedUint::zero_with_precision(modulus.as_ref().bits_precision());
167    let mut remain = products.len();
168    if remain <= max_accum {
169        let carry = impl_longa_monty_lincomb!(
170            products,
171            ret.limbs,
172            modulus.as_ref().limbs,
173            mod_neg_inv,
174            nlimbs
175        );
176        ret.sub_assign_mod_with_carry(carry, modulus.as_ref(), modulus.as_ref());
177    } else {
178        let mut window;
179        let mut buf = BoxedUint::zero_with_precision(modulus.as_ref().bits_precision());
180        while remain > 0 {
181            buf.limbs.fill(Limb::ZERO);
182            let mut count = remain;
183            if count > max_accum {
184                count = max_accum;
185            }
186            (window, products) = products.split_at(count);
187            let carry = impl_longa_monty_lincomb!(
188                window,
189                buf.limbs,
190                modulus.as_ref().limbs,
191                mod_neg_inv,
192                nlimbs
193            );
194            buf.sub_assign_mod_with_carry(carry, modulus.as_ref(), modulus.as_ref());
195            ret.add_mod_assign(&buf, modulus.as_nz_ref());
196            remain -= count;
197        }
198    }
199    ret
200}
crypto_bigint/modular/lincomb.rs

crypto_bigint/modular/
lincomb.rs
