labrador/core/
inner_product.rs

1use std::{
2    borrow::Borrow,
3    ops::{Add, Mul},
4};
5
6/// Computes the **linear combination** of two equally-sized slices, returning the
7/// sum of pair-wise products.
8///
9/// Conceptually, given two slices  
10/// `elements = [A1, A2, … , An]` and `challenges = [c1, c2, … , cn]`,  
11/// the function evaluates  
12///
13/// ```text
14/// Σ (Ai · ci)  for i = 1 .. n
15/// ```
16///
17/// where `·` is multiplication for the underlying types and `+` is the
18/// corresponding addition. The result’s type (`B`) is the same as the borrowed
19/// type of each element in `elements`.
20///
21/// # Arguments
22///
23/// * `elements`   – Slice of items whose borrowed values will be multiplied by
24///   the corresponding entries in `challenges`.
25/// * `challenges` – Slice of multipliers—**must** be the same length as
26///   `elements`.
27///
28/// # Returns
29///
30/// The accumulated sum **Σ `(elements[i] * challenges[i])`** as a value of type
31/// `B`.
32///
33///
34/// # Examples
35///
36/// Basic usage with primitive integers:
37///
38/// ```rust
39/// use std::borrow::Borrow;
40/// use rand::rng;
41/// use labrador::ring::rq::Rq;
42/// use labrador::core::inner_product::compute_linear_combination;
43///
44/// // The function is generic; we can call it directly.
45/// let elems = [Rq::random(&mut rng()), Rq::random(&mut rng()), Rq::random(&mut rng()), Rq::random(&mut rng()), Rq::random(&mut rng())];
46/// let challenges = [Rq::random(&mut rng()), Rq::random(&mut rng()), Rq::random(&mut rng()), Rq::random(&mut rng()), Rq::random(&mut rng())];
47/// let sum = compute_linear_combination(&elems, &challenges);
48/// ```
49///
50pub fn compute_linear_combination<E, B, C>(elements: &[E], challenges: &[C]) -> B
51where
52    E: Borrow<B>,
53    for<'a> &'a B: Mul<&'a C, Output = B>,
54    for<'a> &'a B: Add<&'a B, Output = B>,
55{
56    debug_assert_eq!(
57        elements.len(),
58        challenges.len(),
59        "vectors must be the same length"
60    );
61    debug_assert!(!elements.is_empty(), "`elements` must not be empty");
62
63    let mut zipped_iter = elements.iter().zip(challenges.iter());
64    // Must do the following as the init value in fold requires size of B
65    let (e0, c0) = zipped_iter.next().unwrap();
66    let init = e0.borrow() * c0;
67
68    zipped_iter.fold(init, |acc, (elem, c)| &acc + &(elem.borrow() * c))
69}
70
71#[cfg(test)]
72mod tests {
73    use rand::rng;
74
75    use crate::ring::{rq::Rq, rq_matrix::RqMatrix, rq_vector::RqVector, zq::Zq};
76
77    use super::*;
78
79    #[test]
80    #[should_panic]
81    fn test_inputs_with_different_lengths_panic() {
82        let vector_a = RqVector::random(&mut rng(), 100);
83        let vector_b = RqVector::random(&mut rng(), 90);
84        let _ = compute_linear_combination(vector_a.elements(), vector_b.elements());
85    }
86
87    #[test]
88    fn test_zq_type_inputs() {
89        let poly_a = Rq::random(&mut rng());
90        let poly_b = Rq::random(&mut rng());
91
92        let result = compute_linear_combination(poly_a.coeffs(), poly_b.coeffs());
93
94        let mut expected = Zq::ZERO;
95        for i in 0..poly_a.coeffs().len() {
96            expected += poly_a.coeffs()[i] * poly_b.coeffs()[i];
97        }
98        assert_eq!(result, expected);
99    }
100
101    #[test]
102    fn test_rq_type_inputs() {
103        let poly_vec_a = RqVector::random(&mut rng(), 100);
104        let poly_vec_b = RqVector::random(&mut rng(), 100);
105
106        let result = compute_linear_combination(poly_vec_a.elements(), poly_vec_b.elements());
107
108        let mut expected = Rq::zero();
109        for i in 0..poly_vec_a.elements().len() {
110            expected = &expected + &(&poly_vec_a.elements()[i] * &poly_vec_b.elements()[i]);
111        }
112        assert_eq!(result, expected);
113    }
114
115    #[test]
116    fn test_zq_rq_type_inputs() {
117        let poly_a = Rq::random(&mut rng());
118        let poly_vec_b = RqVector::random(&mut rng(), 64);
119
120        let result = compute_linear_combination(poly_vec_b.elements(), poly_a.coeffs());
121
122        let mut expected = Rq::zero();
123        for i in 0..poly_a.coeffs().len() {
124            expected = &expected + &(&poly_vec_b.elements()[i] * &poly_a.coeffs()[i]);
125        }
126        assert_eq!(result, expected);
127    }
128
129    #[test]
130    fn test_zq_rqvector_type_inputs() {
131        let poly_a = Rq::random(&mut rng());
132        let poly_vec_b = RqMatrix::random(&mut rng(), 64, 100);
133
134        let result = compute_linear_combination(poly_vec_b.elements(), poly_a.coeffs());
135
136        let mut expected = RqVector::zero(100);
137        for i in 0..poly_a.coeffs().len() {
138            expected = &expected + &(&poly_vec_b.elements()[i] * poly_a.coeffs()[i]);
139        }
140        assert_eq!(result, expected);
141    }
142
143    #[test]
144    fn test_rq_rqvector_type_inputs() {
145        let poly_vec_a = RqVector::random(&mut rng(), 80);
146        let poly_vec_b = RqMatrix::random(&mut rng(), 80, 100);
147
148        let result = compute_linear_combination(poly_vec_b.elements(), poly_vec_a.elements());
149
150        let mut expected = RqVector::zero(100);
151        for i in 0..poly_vec_a.elements().len() {
152            expected = &expected + &(&poly_vec_b.elements()[i] * &poly_vec_a.elements()[i]);
153        }
154        assert_eq!(result, expected);
155    }
156}
labrador/core/inner_product.rs

labrador/core/
inner_product.rs
