qfall_math/integer_mod_q/modulus_polynomial_ring_zq/
ntt_basis.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//! This module contains implementations to instantiate
10//! the ntt basis for a given `[ModulusPolynomialRingZq`] object.
11//!
12//! This includes a collection of fixed NTT-viable rings, and the option to set them
13//! unchecked.
14//!
15//! The explicit functions contain the documentation.
16
17use super::ModulusPolynomialRingZq;
18use crate::{
19    integer::Z,
20    integer_mod_q::{
21        Modulus,
22        ntt_basis_polynomial_ring_zq::{ConvolutionType, NTTBasisPolynomialRingZq},
23    },
24    traits::GetCoefficient,
25};
26use std::rc::Rc;
27
28impl ModulusPolynomialRingZq {
29    /// Initiates the NTT-basis for the [`ModulusPolynomialRingZq`] by providing a
30    /// root of unity.
31    /// It is not checked if it is actually a root of unity.
32    /// Based on the constant coefficient, it will either be instantiated for cyclic or negacyclic convolution.
33    /// If it is 1, then it will be interpreted as negacyclic and as cyclic otherwise.
34    /// The rest of the modulus-polynomial will not be checked, whether it is suited, and it will not be checked
35    /// if the provided root is actually a root of unity in the ring.
36    /// Setting the basis only works if `n` is a power of two.
37    ///
38    /// Parameters:
39    /// - `root_of_unity`: the `n`th or respectivley `2n`th root of unity over the modulus
40    ///
41    /// Defines the NTT-basis for the modulus ring without checking the context.
42    ///
43    /// # Examples
44    /// ```
45    /// use qfall_math::integer_mod_q::ModulusPolynomialRingZq;
46    /// use qfall_math::integer_mod_q::PolyOverZq;
47    /// use crate::qfall_math::traits::SetCoefficient;
48    ///
49    /// let n = 256;
50    /// let modulus = 2_i64.pow(23) - 2_i64.pow(13) + 1;
51    ///
52    /// let mut mod_poly = PolyOverZq::from(modulus);
53    /// mod_poly.set_coeff(0, 1).unwrap();
54    /// mod_poly.set_coeff(n, 1).unwrap();
55    ///
56    /// let mut polynomial_modulus = ModulusPolynomialRingZq::from(&mod_poly);
57    ///
58    /// polynomial_modulus.set_ntt_unchecked(1753);
59    /// ```
60    ///
61    /// # Safety
62    /// The caller is responsible in ensuring that the  given root is actually a proper
63    /// root, under the associated polynomial. For negacyclic polynomials, this means
64    /// that the root must be a 2nth root of unity and for cyclic polynomials this means
65    /// that it must be an nth root.
66    ///
67    /// # Panics
68    /// - if `n` is not a power of two.
69    pub fn set_ntt_unchecked(&mut self, root_of_unity: impl Into<Z>) {
70        let n = self.get_degree();
71        let one_coeff: Z = self.get_coeff(0).unwrap();
72
73        let convolution_type = {
74            if one_coeff == Z::ONE {
75                ConvolutionType::Negacyclic
76            } else {
77                ConvolutionType::Cyclic
78            }
79        };
80
81        let ntt_basis = NTTBasisPolynomialRingZq::init(
82            n as usize,
83            root_of_unity,
84            Modulus::from(self.get_q()),
85            convolution_type,
86        );
87        self.ntt_basis = Rc::new(Some(ntt_basis))
88    }
89}
qfall_math/integer_mod_q/modulus_polynomial_ring_zq/ntt_basis.rs

qfall_math/integer_mod_q/modulus_polynomial_ring_zq/
ntt_basis.rs
