qfall_math/integer_mod_q/
ntt_basis_polynomial_ring_zq.rs

1// Copyright © 2025 Marvin Beckmann
2//
3// This file is part of qFALL-math.
4//
5// qFALL-math is free software: you can redistribute it and/or modify it under
6// the terms of the Mozilla Public License Version 2.0 as published by the
7// Mozilla Foundation. See <https://mozilla.org/en-US/MPL/2.0/>.
8
9//! [`NTTBasisPolynomialRingZq`] serves as an optional context object for
10//! [`PolynomialRingZq`](super::PolynomialRingZq). If it is set for the matrix, then the multiplication of polynomials
11//! is performed using the NTT, and otherwise the multiplication is kept as it is.
12
13use super::Modulus;
14use crate::integer::Z;
15pub use from::ConvolutionType;
16
17mod from;
18mod inv_ntt;
19mod ntt;
20
21/// [`NTTBasisPolynomialRingZq`] is an object, that given a polynomial
22/// `X^n - 1 mod q` or `X^n + 1 mod q` computes two transformation functions.
23/// With these functions, one can utilize efficient matrix multiplication O(n log n) instead of
24/// O(n^2) in the trivial polynomial multiplication for [`PolynomialRingZq`](super::PolynomialRingZq) objects.
25///
26/// Currently this implementation *only* supports `n` that are a power of two.
27///
28/// Attributes:
29/// - `n`: the degree of the modulus polynomials
30/// - `n_inv`: the inverse of `n` when viewed `modulo q`
31/// - `powers_of_omega`: contains a list of `n` elements, corresponding to the `n` powers of
32///   of the `n`th root of unity
33/// - `powers_of_omega`: contains a list of `n` elements, corresponding to the `n` powers of
34///   of the inverse of the `n`th root of unity
35/// - `powers_of_psi`: contains a list of `n` elements, corresponding to the `n` powers of
36///   of the `2n`th root of unity (empty for positively wrapped convolutions)
37/// - `powers_of_psi`: contains a list of `n` elements, corresponding to the `n` powers of
38///   of the inverse of the `2n`th root of unity (empty for positively wrapped convolutions)
39/// - `modulus`: a clone of the modulus object the transform is connected to
40/// - `convolution_type`: tells subsequent algorithms if the convolution is positively or negatively wrapped
41///
42/// # Examples
43/// This example is taken from: <https://eprint.iacr.org/2024/585.pdf> Example 3.8
44/// ```
45/// use qfall_math::integer_mod_q::*;
46/// use std::str::FromStr;
47///
48/// let modulus = Modulus::from(7681);
49/// let poly_mod = ModulusPolynomialRingZq::from_str("5  -1 0 0 0 1 mod 7681").unwrap();
50/// let g_poly = PolyOverZq::from_str("4  1 2 3 4 mod 7681").unwrap();
51/// let h_poly = PolyOverZq::from_str("4  5 6 7 8 mod 7681").unwrap();
52///
53/// let ntt_basis = NTTBasisPolynomialRingZq::init(4, 3383, &modulus, ConvolutionType::Cyclic);
54///
55/// let ghat = ntt_basis.ntt(&g_poly);
56/// let hhat = ntt_basis.ntt(&h_poly);
57///
58/// // simulate entrywise multiplication
59/// let mut ghat_hhat = Vec::new();
60/// for i in 0..4 {
61///     ghat_hhat.push(&ghat[i] * &hhat[i]);
62/// }
63///
64/// let g_h_poly = ntt_basis.inv_ntt(ghat_hhat);
65///
66/// let g_h_poly_ring = PolynomialRingZq::from((
67///     g_h_poly.get_representative_least_nonnegative_residue(),
68///     &poly_mod,
69/// ));
70///
71/// // Ensure that multiplication using the NTT and multiplication using
72/// // FLINTs multiplication algorithms yield the same result.
73/// let g_poly_ring = PolynomialRingZq::from((
74///     g_poly.get_representative_least_nonnegative_residue(),
75///     &poly_mod,
76/// ));
77/// let h_poly_ring = PolynomialRingZq::from((
78///     h_poly.get_representative_least_nonnegative_residue(),
79///     &poly_mod,
80/// ));
81///
82/// assert_eq!(g_poly_ring * h_poly_ring, g_h_poly_ring)
83/// ```
84///
85/// This example is taken from: <https://eprint.iacr.org/2024/585.pdf> Example 3.12
86/// ```
87/// use qfall_math::integer_mod_q::*;
88/// use std::str::FromStr;
89///
90/// let modulus = Modulus::from(7681);
91/// let poly_mod = ModulusPolynomialRingZq::from_str("5  1 0 0 0 1 mod 7681").unwrap();
92/// let g_poly = PolyOverZq::from_str("4  1 2 3 4 mod 7681").unwrap();
93/// let h_poly = PolyOverZq::from_str("4  5 6 7 8 mod 7681").unwrap();
94///
95/// let ntt_basis =
96///     NTTBasisPolynomialRingZq::init(4, 1925, &modulus, ConvolutionType::Negacyclic);
97///
98/// let ghat = ntt_basis.ntt(&g_poly);
99/// let hhat = ntt_basis.ntt(&h_poly);
100///
101/// // simulate entrywise mutliplication
102/// let mut ghat_hhat = Vec::new();
103/// for i in 0..4 {
104///     ghat_hhat.push(&ghat[i] * &hhat[i])
105/// }
106///
107/// let g_h_poly = ntt_basis.inv_ntt(ghat_hhat);
108///
109/// let g_h_poly_ring = PolynomialRingZq::from((
110///     g_h_poly.get_representative_least_nonnegative_residue(),
111///     &poly_mod,
112/// ));
113///
114/// // Ensure that multiplication using the NTT and multiplication using
115/// // FLINTs multiplication algorithms yield the same result.
116/// let g_poly_ring = PolynomialRingZq::from((
117///     g_poly.get_representative_least_nonnegative_residue(),
118///     &poly_mod,
119/// ));
120/// let h_poly_ring = PolynomialRingZq::from((
121///     h_poly.get_representative_least_nonnegative_residue(),
122///     &poly_mod,
123/// ));
124///
125/// assert_eq!(g_poly_ring * h_poly_ring, g_h_poly_ring)
126/// ```
127#[derive(Debug)]
128pub struct NTTBasisPolynomialRingZq {
129    pub n: i64,
130    pub n_inv: Z,
131    pub powers_of_omega: Vec<Z>,
132    pub powers_of_omega_inv: Vec<Z>,
133    pub powers_of_psi: Vec<Z>,
134    pub powers_of_psi_inv: Vec<Z>,
135    pub modulus: Modulus,
136    pub convolution_type: ConvolutionType,
137}
qfall_math/integer_mod_q/ntt_basis_polynomial_ring_zq.rs

qfall_math/integer_mod_q/
ntt_basis_polynomial_ring_zq.rs
