labrador/ring/
rq.rs

1// This file is part of the polynomial ring operations module.
2//
3//
4// Currently implemented functions include:
5// - Polynomial addition:          +
6// - Polynomial multiplication:    *
7// - inner_product/ Dot product:   inner_product()
8// - Polynomial subtraction:       -
9// - Polynomial negation:          neg()
10// - Scalar multiplication:        scalar_mul()
11// - Polynomial evaluation:        eval()
12// - Zero check:                   is_zero()
13// - Polynomial equality check:    is_equal()
14// - Get the Coefficients:         get_coefficients()
15// - Random small norm vector:     random_small_vector()
16// - Squared norm of coefficients: compute_norm_squared()
17//
18// Further operations and optimizations will be added in future versions.
19
20// We use the Zq ring
21use crate::ring::zq::Zq;
22use core::ops::{Add, Mul, Sub};
23use rand::distr::{Distribution, Uniform};
24use rand::{CryptoRng, Rng};
25use rustfft::num_complex::Complex;
26use rustfft::FftPlanner;
27
28/// This module provides implementations for various operations
29/// in the polynomial ring R = Z_q\[X\] / (X^d + 1).
30#[derive(Debug, Clone, PartialEq, Eq)]
31pub struct Rq {
32    coeffs: [Zq; Self::DEGREE],
33}
34
35impl Rq {
36    pub const DEGREE: usize = 64;
37    /// Constructor for the polynomial ring
38    pub const fn new(coeffs: [Zq; Self::DEGREE]) -> Self {
39        Rq { coeffs }
40    }
41
42    /// Generate zero polynomial
43    pub const fn zero() -> Self {
44        Self {
45            coeffs: [Zq::ZERO; Self::DEGREE],
46        }
47    }
48
49    pub fn into_coeffs(self) -> [Zq; Self::DEGREE] {
50        self.coeffs
51    }
52
53    /// Get the coefficients as a vector
54    pub fn get_coefficients(&self) -> &[Zq; Self::DEGREE] {
55        &self.coeffs
56    }
57
58    /// Generate random polynomial with a provided cryptographically secure RNG
59    pub fn random<R: Rng + CryptoRng>(rng: &mut R) -> Self {
60        let uniform = Uniform::new_inclusive(Zq::ZERO, Zq::NEG_ONE).unwrap();
61        let mut coeffs = [Zq::ZERO; Self::DEGREE];
62        coeffs.iter_mut().for_each(|c| *c = uniform.sample(rng));
63        Self { coeffs }
64    }
65
66    /// Generate random polynomial with a provided cryptographically secure RNG and given bound
67    pub fn random_with_bound<R: Rng + CryptoRng>(rng: &mut R, bound: u32) -> Self {
68        let uniform = Uniform::new_inclusive(Zq::ZERO, Zq::new(bound)).unwrap();
69        let mut coeffs = [Zq::ZERO; Self::DEGREE];
70        coeffs.iter_mut().for_each(|c| {
71            *c = if rng.random_bool(0.5) {
72                -uniform.sample(rng)
73            } else {
74                uniform.sample(rng)
75            }
76        });
77        Self { coeffs }
78    }
79
80    #[allow(clippy::as_conversions)]
81    pub fn l2_norm_squared(&self) -> Zq {
82        self.coeffs
83            .iter()
84            .map(|coeff| {
85                coeff.centered_mod(Zq::new(Zq::Q as u32))
86                    * coeff.centered_mod(Zq::new(Zq::Q as u32))
87            })
88            .sum()
89    }
90
91    /// Decomposes a polynomial into base-B representation:
92    /// p = p⁽⁰⁾ + p⁽¹⁾·B + p⁽²⁾·B² + ... + p⁽ᵗ⁻¹⁾·B^(t-1)
93    /// Where each p⁽ⁱ⁾ has small coefficients, using centered representatives
94    pub fn decompose(&self, base: Zq, num_parts: usize) -> Vec<Rq> {
95        debug_assert!(num_parts > 0, "num_parts must be positive");
96        let mut parts = Vec::with_capacity(num_parts);
97        let mut initial_coeffs = *self.get_coefficients();
98
99        for _ in 0..num_parts - 1 {
100            // Extract low part (mod base, centered around 0)
101            let mut low_coeffs = [Zq::ZERO; Self::DEGREE];
102
103            for (low_c, coeff) in low_coeffs.iter_mut().zip(initial_coeffs.iter_mut()) {
104                let centered = coeff.centered_mod(base);
105                *low_c = centered;
106                *coeff = (*coeff - centered).scale_by(base);
107            }
108            parts.push(Self::new(low_coeffs));
109        }
110        parts.push(Self::new(initial_coeffs));
111        parts
112    }
113
114    /// Compute the conjugate automorphism \sigma_{-1} of vector based on B) Constraints..., Page 21.
115    pub fn conjugate_automorphism(&self) -> Self {
116        let q_minus_1 = Zq::NEG_ONE;
117
118        let original_coefficients = self.get_coefficients();
119
120        let mut conjugated_coeffs = [Zq::ZERO; Rq::DEGREE];
121        conjugated_coeffs[0] = original_coefficients[0];
122
123        for (conj_coeff, original_coeff) in conjugated_coeffs
124            .iter_mut()
125            .skip(1)
126            .zip(original_coefficients.iter().rev())
127        {
128            *conj_coeff = original_coeff * q_minus_1;
129        }
130
131        Self::new(conjugated_coeffs)
132    }
133
134    /// Compute the operator norm of a polynomial given its coefficients.
135    /// The operator norm is defined as the maximum magnitude of the DFT (eigenvalues)
136    /// of the coefficient vector.
137    ///
138    /// Note that: The operator norm only affects the coefficients of the random PolyRings generated from the challenge space.
139    /// Prover and Verifier will not do the operator norm check, because random PolyRings are determined after generation.
140    /// Both party will have access to the same PolyRings through transcript,
141    #[allow(clippy::as_conversions)]
142    pub fn operator_norm(&self) -> f64 {
143        let coeffs = self.get_coefficients();
144        let n = coeffs.len();
145        let mut planner = FftPlanner::new();
146        let fft = planner.plan_fft_forward(n);
147
148        // Convert coefficients into complex numbers (with zero imaginary parts)
149        let mut buffer: Vec<Complex<f64>> = coeffs
150            .iter()
151            .map(|&x| {
152                let half = Zq::NEG_ONE.scale_by(Zq::TWO);
153                let converted_value = if x > half {
154                    x.to_u128() as f64 - Zq::NEG_ONE.to_u128() as f64 - 1.0
155                } else {
156                    x.to_u128() as f64
157                };
158                Complex {
159                    re: converted_value,
160                    im: 0.0,
161                }
162            })
163            .collect();
164
165        // Compute the FFT (this gives the eigenvalues of the circulant matrix)
166        fft.process(&mut buffer);
167
168        // Return the maximum absolute value (norm) among the eigenvalues
169        buffer
170            .iter()
171            .map(|c| c.norm())
172            .fold(0.0, |max, x| max.max(x))
173    }
174}
175
176impl Add<&Rq> for &Rq {
177    type Output = Rq;
178    /// Add two polynomials
179    fn add(self, other: &Rq) -> Rq {
180        let mut coeffs = [Zq::ZERO; Rq::DEGREE];
181        for (r, (a, b)) in coeffs
182            .iter_mut()
183            .zip(self.coeffs.iter().zip(other.coeffs.iter()))
184        {
185            *r = *a + *b;
186        }
187        Rq::new(coeffs)
188    }
189}
190
191impl Sub<&Rq> for &Rq {
192    type Output = Rq;
193    /// Add two polynomials
194    fn sub(self, other: &Rq) -> Rq {
195        let mut coeffs = [Zq::ZERO; Rq::DEGREE];
196        for (r, (a, b)) in coeffs
197            .iter_mut()
198            .zip(self.coeffs.iter().zip(other.coeffs.iter()))
199        {
200            *r = *a - *b;
201        }
202        Rq::new(coeffs)
203    }
204}
205
206impl Mul<&Rq> for &Rq {
207    type Output = Rq;
208    /// Polynomial multiplication modulo x^D + 1
209    fn mul(self, other: &Rq) -> Rq {
210        let mut result = [Zq::ZERO; Rq::DEGREE];
211        let mut out_of_field = [Zq::ZERO; Rq::DEGREE];
212        for (i, &self_coeff) in self.coeffs.iter().enumerate() {
213            for (j, &other_coeff) in other.coeffs.iter().enumerate() {
214                if i + j < Rq::DEGREE {
215                    result[i + j] += self_coeff * other_coeff;
216                } else {
217                    out_of_field[(i + j) % Rq::DEGREE] += self_coeff * other_coeff;
218                }
219            }
220        }
221        // Process excess terms with sign adjustment
222        for i in (0..Rq::DEGREE).rev() {
223            result[i] -= out_of_field[i];
224        }
225        Rq::new(result)
226    }
227}
228
229impl Mul<&Zq> for &Rq {
230    type Output = Rq;
231    /// Scalar multiplication of a polynomial
232    fn mul(self, other: &Zq) -> Rq {
233        let mut copied_coeffs = self.coeffs;
234        for elem in copied_coeffs.iter_mut() {
235            *elem *= *other;
236        }
237        Rq::new(copied_coeffs)
238    }
239}
240
241#[cfg(test)]
242pub mod tests {
243    use super::*;
244
245    pub fn generate_rq_from_zq_vector(vec: Vec<Zq>) -> Rq {
246        let mut temp = [Zq::ZERO; Rq::DEGREE];
247        // Process excess terms with sign adjustment
248        for i in (0..vec.len()).rev() {
249            let m = i / Rq::DEGREE;
250            let r = i % Rq::DEGREE;
251            let sign = if m % 2 == 0 { 1 } else { -1 };
252            if sign == 1 {
253                temp[r] += vec[i];
254            } else {
255                temp[r] -= vec[i];
256            }
257        }
258        Rq::new(temp)
259    }
260
261    mod helper {
262        use super::*;
263        pub fn padded(prefix: &[Zq]) -> [Zq; Rq::DEGREE] {
264            assert!(
265                prefix.len() <= Rq::DEGREE,
266                "too many coefficients for degree {}",
267                Rq::DEGREE
268            );
269
270            let mut out = [Zq::ZERO; Rq::DEGREE];
271            out[..prefix.len()].copy_from_slice(prefix);
272            out
273        }
274
275        pub fn rq_from(prefix: &[Zq]) -> Rq {
276            Rq {
277                coeffs: padded(prefix),
278            }
279        }
280    }
281
282    // Test new() and polynomial creation
283    #[test]
284    fn test_new_and_create_poly() {
285        let coeffs = [Zq::ONE, Zq::new(2), Zq::new(3), Zq::new(4)];
286        let poly = helper::rq_from(&coeffs);
287        assert_eq!(poly.coeffs, helper::padded(&coeffs));
288
289        // Direct conversion
290        let coeffs2 = [Zq::ONE, Zq::new(2), Zq::new(3), Zq::new(4)];
291        let poly_from_vec_direct: Rq = generate_rq_from_zq_vector(coeffs.to_vec());
292        assert_eq!(poly_from_vec_direct.coeffs, helper::padded(&coeffs2));
293    }
294
295    #[test]
296    fn test_into_coeffs_returns_correct() {
297        let mut coeffs = [Zq::ZERO; Rq::DEGREE];
298        coeffs[0] = Zq::ONE;
299        coeffs[0] = Zq::new(20);
300        coeffs[0] = Zq::new(3121);
301        coeffs[0] = Zq::new(40);
302        let poly: Rq = generate_rq_from_zq_vector(coeffs.to_vec());
303
304        let result = Rq::into_coeffs(poly); // or whatever constructor you have
305        assert_eq!(result, coeffs);
306    }
307
308    // Test addition of polynomials
309    #[test]
310    fn test_add() {
311        // Within bounds
312        let poly1: Rq =
313            generate_rq_from_zq_vector(vec![Zq::ONE, Zq::new(2), Zq::new(3), Zq::new(4)]);
314        let poly2: Rq =
315            generate_rq_from_zq_vector(vec![Zq::new(4), Zq::new(3), Zq::new(2), Zq::ONE]);
316        let result = &poly1 + &poly2;
317        assert_eq!(
318            result.coeffs,
319            helper::padded(&[Zq::new(5), Zq::new(5), Zq::new(5), Zq::new(5)])
320        );
321
322        // Outside of bounds
323        let poly3: Rq =
324            generate_rq_from_zq_vector(vec![Zq::ONE, Zq::new(2), Zq::new(3), Zq::new(4)]);
325        let poly4: Rq =
326            generate_rq_from_zq_vector(vec![Zq::NEG_ONE, Zq::new(3), Zq::NEG_ONE, Zq::ONE]);
327        let result2 = &poly3 + &poly4;
328        assert_eq!(
329            result2.coeffs,
330            helper::padded(&[Zq::ZERO, Zq::new(5), Zq::new(2), Zq::new(5)])
331        );
332        // Addition with zero polynomial
333        let poly5: Rq =
334            generate_rq_from_zq_vector(vec![Zq::ONE, Zq::new(2), Zq::new(3), Zq::new(4)]);
335        let poly6: Rq = generate_rq_from_zq_vector(vec![Zq::ZERO]);
336        let result3 = &poly5 + &poly6;
337        assert_eq!(
338            result3.coeffs,
339            helper::padded(&[Zq::ONE, Zq::new(2), Zq::new(3), Zq::new(4)])
340        );
341        // Addition with high coefficients
342        let poly7: Rq =
343            generate_rq_from_zq_vector(vec![Zq::ONE, Zq::new(2), Zq::new(3), Zq::NEG_ONE]);
344        let poly8: Rq =
345            generate_rq_from_zq_vector(vec![Zq::NEG_ONE, Zq::NEG_ONE, Zq::NEG_ONE, Zq::NEG_ONE]);
346        let result3 = &poly7 + &poly8;
347        assert_eq!(
348            result3.coeffs,
349            helper::padded(&[Zq::ZERO, Zq::ONE, Zq::new(2), -Zq::new(2)])
350        );
351    }
352
353    // Test multiplication of polynomials
354    #[test]
355    fn test_mul() {
356        // Multiplication with wrapping
357        let poly1: Rq = generate_rq_from_zq_vector(vec![Zq::ONE, Zq::ONE, Zq::new(2)]);
358        let poly2: Rq = generate_rq_from_zq_vector(vec![Zq::ONE, Zq::ONE]);
359        let result = &poly1 * &poly2;
360        assert_eq!(
361            result.coeffs,
362            helper::padded(&[Zq::new(1), Zq::new(2), Zq::new(3), Zq::new(2)])
363        );
364
365        // Multiplication with zero polynomial
366        let poly3: Rq = generate_rq_from_zq_vector(vec![Zq::ONE, Zq::ONE, Zq::new(2)]);
367        let poly4: Rq = generate_rq_from_zq_vector(vec![Zq::ZERO]);
368        let result2 = &poly3 * &poly4;
369        assert_eq!(
370            result2.coeffs,
371            helper::padded(&[Zq::ZERO, Zq::ZERO, Zq::ZERO])
372        );
373
374        // Needs to be revised later
375        // // Multiplication with wrapping higher order
376        // let poly5: Rq = generate_rq_from_zq_vector(vec![Zq::ONE, Zq::ONE, Zq::new(2)]);
377        // let poly6: Rq = vec![Zq::ONE, Zq::ONE, Zq::new(7), Zq::new(5)].into();
378        // let result3 = poly5 * poly6;
379        // assert_eq!(
380        //     result3.coeffs,
381        //     helper::padded(&[Zq::new(u32::MAX - 12), Zq::new(u32::MAX - 16), Zq::ZERO])
382        // );
383    }
384
385    // Test subtraction of polynomials
386    #[test]
387    fn test_sub() {
388        // within bounds
389        let poly1: Rq =
390            generate_rq_from_zq_vector(vec![Zq::new(5), Zq::new(10), Zq::new(15), Zq::new(20)]);
391        let poly2: Rq =
392            generate_rq_from_zq_vector(vec![Zq::new(2), Zq::new(4), Zq::new(6), Zq::new(8)]);
393        let result = &poly1 - &poly2;
394        assert_eq!(
395            result.coeffs,
396            helper::padded(&[Zq::new(3), Zq::new(6), Zq::new(9), Zq::new(12)])
397        );
398
399        // Outside of bounds
400        let poly3: Rq = generate_rq_from_zq_vector(vec![Zq::ONE, Zq::ONE, Zq::new(3), Zq::new(2)]);
401        let poly4: Rq =
402            generate_rq_from_zq_vector(vec![Zq::new(2), Zq::new(4), Zq::new(6), Zq::new(8)]);
403        let result2 = &poly3 - &poly4;
404        assert_eq!(
405            result2.coeffs,
406            helper::padded(&[
407                Zq::ZERO - Zq::new(1),
408                Zq::ZERO - Zq::new(3),
409                Zq::ZERO - Zq::new(3),
410                Zq::ZERO - Zq::new(6),
411            ])
412        );
413        // Subtraction with zero polynomial
414        let poly5: Rq =
415            generate_rq_from_zq_vector(vec![Zq::ONE, Zq::new(2), Zq::new(3), Zq::new(4)]);
416        let poly6: Rq = generate_rq_from_zq_vector(vec![Zq::ZERO]);
417        let result3 = &poly6 - &poly5;
418        let result4 = &poly5 - &poly6;
419        assert_eq!(
420            result3.coeffs,
421            helper::padded(&[
422                Zq::ZERO - Zq::new(1),
423                Zq::ZERO - Zq::new(2),
424                Zq::ZERO - Zq::new(3),
425                Zq::ZERO - Zq::new(4),
426            ])
427        );
428        assert_eq!(
429            result4.coeffs,
430            helper::padded(&[Zq::ONE, Zq::new(2), Zq::new(3), Zq::new(4)])
431        );
432    }
433
434    // Test scalar multiplication
435    #[test]
436    fn test_scalar_mul() {
437        let poly: Rq =
438            generate_rq_from_zq_vector(vec![Zq::ONE, Zq::new(2), Zq::new(3), Zq::new(4)]);
439        let result = &poly * &Zq::new(2);
440        assert_eq!(
441            result.coeffs,
442            helper::padded(&[Zq::new(2), Zq::new(4), Zq::new(6), Zq::new(8)])
443        );
444    }
445
446    // Test coefficient extraction
447    #[test]
448    fn test_get_coefficient() {
449        let poly: Rq = generate_rq_from_zq_vector(vec![Zq::ONE, Zq::ZERO, Zq::new(5), Zq::NEG_ONE]);
450        let vec = helper::padded(&[Zq::ONE, Zq::ZERO, Zq::new(5), Zq::NEG_ONE]).to_vec();
451        assert!(poly.get_coefficients().to_vec() == vec);
452
453        let poly_zero: Rq =
454            generate_rq_from_zq_vector(vec![Zq::ZERO, Zq::ZERO, Zq::ZERO, Zq::ZERO]);
455        let vec_zero = helper::padded(&[Zq::ZERO, Zq::ZERO, Zq::ZERO, Zq::ZERO]).to_vec();
456        assert!(poly_zero.get_coefficients().to_vec() == vec_zero);
457    }
458
459    #[test]
460    fn test_base2_decomposition() {
461        // Test case 1: Base 2 decomposition
462        let poly: Rq =
463            generate_rq_from_zq_vector(vec![Zq::new(5), Zq::new(3), Zq::new(7), Zq::new(1)]);
464        let parts = poly.decompose(Zq::TWO, 2);
465
466        // Part 0: remainders mod 2 (no centering needed for base 2)
467        assert_eq!(
468            parts[0].coeffs,
469            helper::padded(&[
470                Zq::ONE, // 5 mod 2 = 1
471                Zq::ONE, // 3 mod 2 = 1
472                Zq::ONE, // 7 mod 2 = 1
473                Zq::ONE, // 1 mod 2 = 1
474            ])
475        );
476
477        // Part 1: quotients after division by 2
478        assert_eq!(
479            parts[1].coeffs,
480            helper::padded(&[
481                Zq::new(2), // 5 div 2 = 2
482                Zq::ONE,    // 3 div 2 = 1
483                Zq::new(3), // 7 div 2 = 3
484                Zq::ZERO,   // 1 div 2 = 0
485            ])
486        );
487
488        // Verify Base 2 reconstruction coefficient by coefficient
489        for i in 0..4 {
490            let expected = poly.coeffs[i];
491            let actual = parts[0].coeffs[i] + parts[1].coeffs[i] * Zq::TWO;
492            assert_eq!(actual, expected, "Base 2: Coefficient {} mismatch", i);
493        }
494    }
495
496    #[test]
497    fn test_base3_decomposition() {
498        // Test case: Base 3 decomposition with centering
499        let specific_poly: Rq =
500            generate_rq_from_zq_vector(vec![Zq::new(8), Zq::new(11), Zq::new(4), Zq::new(15)]);
501        let parts = specific_poly.decompose(Zq::new(3), 2);
502
503        // Part 0: centered remainders mod 3
504        assert_eq!(
505            parts[0].coeffs,
506            helper::padded(&[
507                Zq::NEG_ONE, // 8 mod 3 = 2 -> -1 (centered)
508                Zq::NEG_ONE, // 11 mod 3 = 2 -> -1 (centered)
509                Zq::ONE,     // 4 mod 3 = 1 -> 1 (centered)
510                Zq::ZERO,    // 15 mod 3 = 0 -> 0 (centered)
511            ])
512        );
513
514        // Part 1: quotients
515        assert_eq!(
516            parts[1].coeffs,
517            helper::padded(&[
518                Zq::new(3), // (8 + 1) div 3 = 3
519                Zq::new(4), // (11 + 1) div 3 = 4
520                Zq::ONE,    // 4 div 3 = 1
521                Zq::new(5), // 15 div 3 = 5
522            ])
523        );
524
525        // Verify Base 3 reconstruction coefficient by coefficient
526        for i in 0..4 {
527            let expected = specific_poly.coeffs[i];
528            let p0 = parts[0].coeffs[i];
529            let p1 = parts[1].coeffs[i];
530            let actual = p0 + p1 * Zq::new(3);
531            assert_eq!(actual, expected, "Base 3: Coefficient {} mismatch", i);
532        }
533    }
534
535    #[test]
536    fn test_decomposition_edge_cases() {
537        // Test zero polynomial
538        let zero_poly: Rq = generate_rq_from_zq_vector(vec![Zq::ZERO; 4]);
539        let parts = zero_poly.decompose(Zq::TWO, 2);
540        assert!(
541            // Check any polynomial is zero
542            parts
543                .iter()
544                .all(|p| p.get_coefficients().iter().all(|&coeff| coeff == Zq::ZERO)),
545            "Zero polynomial decomposition failed"
546        );
547
548        // Test single part decomposition
549        let simple_poly: Rq =
550            generate_rq_from_zq_vector(vec![Zq::ONE, Zq::new(2), Zq::new(3), Zq::new(4)]);
551        let parts = simple_poly.decompose(Zq::TWO, 1);
552        assert_eq!(parts.len(), 1, "Single part decomposition length incorrect");
553        assert_eq!(
554            parts[0], simple_poly,
555            "Single part decomposition value incorrect"
556        );
557    }
558
559    #[test]
560    fn test_large_base_decomposition() {
561        // Test decomposition with larger bases (8 and 16)
562        let poly: Rq =
563            generate_rq_from_zq_vector(vec![Zq::new(120), Zq::new(33), Zq::new(255), Zq::new(19)]);
564
565        // Base 8 decomposition
566        let parts_base8 = poly.decompose(Zq::new(8), 2);
567
568        // Part 0: centered remainders mod 8
569        assert_eq!(
570            parts_base8[0].coeffs,
571            helper::padded(&[
572                Zq::ZERO,    // 120 mod 8 = 0 -> 0 (centered)
573                Zq::ONE,     // 33 mod 8 = 1 -> 1 (centered)
574                Zq::NEG_ONE, // 255 mod 8 = 7 -> -1 (centered)
575                Zq::new(3),  // 19 mod 8 = 3 -> 3 (centered)
576            ])
577        );
578
579        // Part 1: quotients
580        assert_eq!(
581            parts_base8[1].coeffs,
582            helper::padded(&[
583                Zq::new(15), // 120 div 8 = 15
584                Zq::new(4),  // 33 div 8 = 4
585                Zq::new(32), // (255 + 1) div 8 = 32
586                Zq::new(2),  // 19 div 8 = 2
587            ])
588        );
589
590        // Verify reconstruction coefficient by coefficient
591        for i in 0..4 {
592            let expected = poly.coeffs[i];
593            let p0 = parts_base8[0].coeffs[i];
594            let p1 = parts_base8[1].coeffs[i];
595            let actual = p0 + p1 * Zq::new(8);
596            assert_eq!(actual, expected, "Base 8: Coefficient {} mismatch", i);
597        }
598
599        // Base 16 decomposition
600        let parts_base16 = poly.decompose(Zq::new(16), 2);
601
602        // Verify reconstruction for base 16
603        for i in 0..4 {
604            let expected = poly.coeffs[i];
605            let p0 = parts_base16[0].coeffs[i];
606            let p1 = parts_base16[1].coeffs[i];
607            let actual = p0 + p1 * Zq::new(16);
608            assert_eq!(actual, expected, "Base 16: Coefficient {} mismatch", i);
609        }
610    }
611
612    #[test]
613    fn test_multi_part_decomposition() {
614        // Test with more than 2 parts
615        let poly: Rq = generate_rq_from_zq_vector(vec![
616            Zq::new(123),
617            Zq::new(456),
618            Zq::new(789),
619            Zq::new(101112),
620        ]);
621
622        // Decompose into 3 parts with base 4
623        let parts = poly.decompose(Zq::new(4), 3);
624        assert_eq!(parts.len(), 3, "Should have 3 parts");
625
626        // Test reconstruction with all 3 parts
627        let reconstructed =
628            &(&parts[0] + &(&(&parts[1] * &Zq::new(4)) + &(&parts[2] * &Zq::new(16)))); // 4²
629
630        // Verify reconstruction coefficient by coefficient
631        for i in 0..4 {
632            assert_eq!(
633                reconstructed.coeffs[i], poly.coeffs[i],
634                "3-part base 4: Coefficient {} mismatch",
635                i
636            );
637        }
638    }
639
640    #[test]
641    fn test_centering_properties() {
642        // Test that centering works correctly for various values
643        // Using base 5 which has half_base = 2
644        let values = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
645        let poly: Rq =
646            generate_rq_from_zq_vector(values.iter().map(|&v| Zq::new(v)).collect::<Vec<Zq>>());
647
648        let parts = poly.decompose(Zq::new(5), 2);
649
650        // Expected centered values for each coefficient:
651        // 0 mod 5 = 0 -> 0
652        // 1 mod 5 = 1 -> 1
653        // 2 mod 5 = 2 -> 2 (at threshold)
654        // 3 mod 5 = 3 -> -2 (centered)
655        // 4 mod 5 = 4 -> -1 (centered)
656        // 5 mod 5 = 0 -> 0
657        // ... and so on
658        let expected_centered = [
659            Zq::ZERO,    // 0 centered
660            Zq::ONE,     // 1 centered
661            Zq::new(2),  // 2 centered (at threshold)
662            -Zq::new(2), // 3 centered to -2
663            -Zq::ONE,    // 4 centered to -1
664            Zq::ZERO,    // 5 centered
665            Zq::ONE,     // 6 centered
666            Zq::new(2),  // 7 centered
667            -Zq::new(2), // 8 centered to -2
668            -Zq::ONE,    // 9 centered to -1
669            Zq::ZERO,    // 10 centered
670        ];
671
672        for (i, &expected) in expected_centered.iter().enumerate() {
673            assert_eq!(
674                parts[0].coeffs[i], expected,
675                "Base 5 centering: Coefficient {} incorrectly centered",
676                i
677            );
678        }
679    }
680
681    #[test]
682    fn test_extreme_values() {
683        // Test with values near the extremes of the Zq range
684        let poly: Rq = generate_rq_from_zq_vector(vec![Zq::ZERO, Zq::NEG_ONE, -Zq::ONE]);
685
686        // Decompose with base 3
687        let parts = poly.decompose(Zq::new(3), 2);
688
689        // Verify reconstruction
690        let reconstructed = &parts[0] + &(&parts[1] * &Zq::new(3));
691
692        for i in 0..3 {
693            assert_eq!(
694                reconstructed.coeffs[i], poly.coeffs[i],
695                "Extreme values: Coefficient {} mismatch",
696                i
697            );
698        }
699
700        // Corrected test for high value divisibility
701        // u32::MAX = 4294967295, which equals 1431655765 * 3 + 0
702        // So u32::MAX mod 3 = 0, which remains 0 (no centering needed)
703        assert_eq!(parts[0].coeffs[1], -Zq::new(1)); // Remainder after division by 3
704        assert_eq!(parts[1].coeffs[1], Zq::ZERO); // Quotient
705
706        // Check u32::MAX - 1 as well
707        // 4294967294 mod 3 = 1, which remains 1 (no centering needed since 1 <= half_base)
708        assert_eq!(parts[0].coeffs[2], Zq::NEG_ONE); // u32::MAX - 1 is the third coefficient
709        assert_eq!(parts[1].coeffs[2], Zq::ZERO); // Should be same quotient
710    }
711
712    #[test]
713    fn test_decomposition_properties() {
714        // Test the algebraic property that all coefficients in first part should be small
715        let poly: Rq = generate_rq_from_zq_vector(vec![
716            Zq::new(100),
717            Zq::new(200),
718            Zq::new(300),
719            Zq::new(400),
720            Zq::new(500),
721            Zq::new(600),
722            Zq::new(700),
723            Zq::new(800),
724        ]);
725
726        for base in [2, 3, 4, 5, 8, 10, 16].iter() {
727            let parts = poly.decompose(Zq::new(*base), 2);
728            let half_base = Zq::new(*base).scale_by(Zq::TWO);
729
730            // Check that all coefficients in first part are properly "small"
731            for coeff in parts[0].coeffs.iter() {
732                // In centered representation, all coefficients should be <= half_base
733                let abs_coeff = if *coeff > Zq::new(u32::MAX / 2) {
734                    Zq::ZERO - *coeff // Handle negative values (represented as large positive ones)
735                } else {
736                    *coeff
737                };
738
739                assert!(
740                    abs_coeff <= half_base,
741                    "Base {}: First part coefficient {} exceeds half-base {}",
742                    base,
743                    coeff,
744                    half_base
745                );
746            }
747
748            // Verify reconstruction
749            let reconstructed = &parts[0] + &(&parts[1] * &Zq::new(*base));
750            assert_eq!(reconstructed, poly, "Base {}: Reconstruction failed", base);
751        }
752    }
753
754    #[test]
755    fn test_conjugate_automorphism() {
756        use crate::core::inner_product::compute_linear_combination;
757
758        let poly1 = helper::rq_from(&[Zq::ONE, Zq::TWO, Zq::new(3)]);
759        let poly2 = helper::rq_from(&[Zq::new(4), Zq::new(5), Zq::new(6)]);
760        let inner_12 =
761            compute_linear_combination(poly1.get_coefficients(), poly2.get_coefficients());
762        let conjugated_1 = poly1.conjugate_automorphism();
763        let inner_conjugated_12 = &conjugated_1 * &poly2;
764
765        assert_eq!(inner_conjugated_12.coeffs.len(), Rq::DEGREE);
766        assert_eq!(inner_conjugated_12.get_coefficients()[0], Zq::new(32));
767        assert_eq!(inner_conjugated_12.get_coefficients()[1], Zq::new(17));
768        assert_eq!(inner_conjugated_12.get_coefficients()[2], Zq::new(6));
769
770        // ct<\sigma_{-1}(poly1), poly2> ?= <poly1, poly2>
771        let ct_inner_conjugated_12 = inner_conjugated_12.get_coefficients()[0];
772        assert_eq!(ct_inner_conjugated_12, inner_12);
773    }
774
775    // Test the square of the norm
776    #[test]
777    fn test_norm() {
778        let poly1 = generate_rq_from_zq_vector(vec![Zq::ONE, Zq::ZERO, Zq::new(5), Zq::NEG_ONE]);
779        let poly2 = generate_rq_from_zq_vector(vec![Zq::ZERO, Zq::ZERO, Zq::new(5), Zq::ONE]);
780        let poly3 = generate_rq_from_zq_vector(vec![Zq::new(5), Zq::ONE, -Zq::new(6), Zq::ZERO]);
781        let poly4 = Rq::zero();
782
783        assert_eq!(poly1.l2_norm_squared(), Zq::new(27));
784        assert_eq!(poly2.l2_norm_squared(), Zq::new(26));
785        assert_eq!(poly3.l2_norm_squared(), Zq::new(62));
786        assert_eq!(poly4.l2_norm_squared(), Zq::ZERO);
787    }
788}
labrador/ring/rq.rs

labrador/ring/
rq.rs
