qfall-math 0.1.1

Mathematical foundations for rapid prototyping of lattice-based cryptography
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

// Copyright © 2023 Marvin Beckmann
//
// This file is part of qFALL-math.
//
// qFALL-math is free software: you can redistribute it and/or modify it under
// the terms of the Mozilla Public License Version 2.0 as published by the
// Mozilla Foundation. See <https://mozilla.org/en-US/MPL/2.0/>.

//! Implementations to reduce a [`PolynomialRingZq`] with the
//! [`ModulusPolynomialRingZq`](crate::integer_mod_q::ModulusPolynomialRingZq).

// **For Developers** note: The [`ModulusPolynomialRingZq`](crate::integer_mod_q::ModulusPolynomialRingZq)
// is not applied automatically, and has to be called in the functions individually.
// Additionally the comparisons assume that the entries are reduced,
// hence no reduction is performed in the check.

use super::PolynomialRingZq;
use crate::integer::fmpz_poly_helpers::reduce_fmpz_poly_by_fmpz_mod_poly_sparse;

impl PolynomialRingZq {
    /// This function manually applies the modulus
    /// [`ModulusPolynomialRingZq`](crate::integer_mod_q::ModulusPolynomialRingZq)
    /// to the given polynomial [`PolyOverZ`](crate::integer::PolyOverZ)
    /// in the [`PolynomialRingZq`].
    ///
    /// # Examples
    /// ```compile_fail
    /// use qfall_math::integer_mod_q::PolynomialRingZq;
    /// use qfall_math::integer_mod_q::ModulusPolynomialRingZq;
    /// use qfall_math::integer::PolyOverZ;
    /// use std::str::FromStr;
    ///
    /// let modulus = ModulusPolynomialRingZq::from_str("4  1 0 0 1 mod 17").unwrap();
    /// let poly = PolyOverZ::from_str("4  -1 0 1 1").unwrap();
    /// let mut poly_ring = PolynomialRingZq::from((&poly, &modulus));
    ///
    /// poly_ring.reduce()
    /// ```
    pub(crate) fn reduce(&mut self) {
        let degree = self.get_degree();
        if degree >= 0 {
            unsafe {
                reduce_fmpz_poly_by_fmpz_mod_poly_sparse(
                    &mut self.poly.poly,
                    &self.modulus.modulus.poly,
                    &self.modulus.non_zero,
                    self.modulus.get_q_as_modulus().get_fmpz_mod_ctx_struct(),
                )
            };
        }
    }
}

#[cfg(test)]
mod test_reduced {
    use crate::{
        integer::PolyOverZ,
        integer_mod_q::{ModulusPolynomialRingZq, PolynomialRingZq},
    };
    use std::str::FromStr;

    const LARGE_PRIME: u64 = u64::MAX - 58;

    /// Ensure that the entries are reduced
    #[test]
    fn reduces() {
        let modulus =
            ModulusPolynomialRingZq::from_str(&format!("4  1 0 0 1 mod {LARGE_PRIME}")).unwrap();
        let poly =
            PolyOverZ::from_str(&format!("4  {} {} 1 1", LARGE_PRIME + 2, u64::MAX)).unwrap();
        let mut poly_ring = PolynomialRingZq { poly, modulus };

        let cmp_modulus =
            ModulusPolynomialRingZq::from_str(&format!("4  1 0 0 1 mod {LARGE_PRIME}")).unwrap();
        let cmp_poly = PolyOverZ::from_str("3  1 58 1").unwrap();
        let cmp_poly_ring = PolynomialRingZq {
            poly: cmp_poly.clone(),
            modulus: cmp_modulus,
        };

        // we only compare the parts individually, not under the modulus, hence they should not be the same
        // unless they have been reduced
        assert_ne!(poly_ring.poly, cmp_poly);
        assert_ne!(poly_ring, cmp_poly_ring);

        poly_ring.reduce();
        assert_eq!(poly_ring.poly, cmp_poly);
        assert_eq!(poly_ring, cmp_poly_ring);
    }
}