halo2_ecc/bigint/
mul_no_carry.rs

1use super::{CRTInteger, OverflowInteger};
2use halo2_base::{gates::GateInstructions, utils::ScalarField, Context, QuantumCell::Existing};
3
4/// # Assumptions
5/// * `a` and `b` have the same number of limbs `k`
6/// * `k` is nonzero
7/// * `num_limbs_log2_ceil = log2_ceil(k)`
8/// * `log2_ceil(k) + a.max_limb_bits + b.max_limb_bits <= F::NUM_BITS as usize - 2`
9pub fn truncate<F: ScalarField>(
10    gate: &impl GateInstructions<F>,
11    ctx: &mut Context<F>,
12    a: OverflowInteger<F>,
13    b: OverflowInteger<F>,
14    num_limbs_log2_ceil: usize,
15) -> OverflowInteger<F> {
16    let k = a.limbs.len();
17    assert_eq!(k, b.limbs.len());
18    debug_assert!(k > 0);
19
20    debug_assert!(
21        num_limbs_log2_ceil + a.max_limb_bits + b.max_limb_bits <= F::NUM_BITS as usize - 2
22    );
23
24    let out_limbs = (0..k)
25        .map(|i| {
26            gate.inner_product(
27                ctx,
28                a.limbs[..=i].iter().copied(),
29                b.limbs[..=i].iter().rev().map(|x| Existing(*x)),
30            )
31        })
32        .collect();
33
34    OverflowInteger::new(out_limbs, num_limbs_log2_ceil + a.max_limb_bits + b.max_limb_bits)
35}
36
37pub fn crt<F: ScalarField>(
38    gate: &impl GateInstructions<F>,
39    ctx: &mut Context<F>,
40    a: CRTInteger<F>,
41    b: CRTInteger<F>,
42    num_limbs_log2_ceil: usize,
43) -> CRTInteger<F> {
44    let out_trunc = truncate::<F>(gate, ctx, a.truncation, b.truncation, num_limbs_log2_ceil);
45    let out_native = gate.mul(ctx, a.native, b.native);
46    let out_val = a.value * b.value;
47
48    CRTInteger::new(out_trunc, out_native, out_val)
49}