Struct NTTBasisPolynomialRingZq 

pub struct NTTBasisPolynomialRingZq {
    pub n: i64,
    pub n_inv: Z,
    pub powers_of_omega: Vec<Z>,
    pub powers_of_omega_inv: Vec<Z>,
    pub powers_of_psi: Vec<Z>,
    pub powers_of_psi_inv: Vec<Z>,
    pub modulus: Modulus,
    pub convolution_type: ConvolutionType,
}

NTTBasisPolynomialRingZq is an object, that given a polynomial X^n - 1 mod q or X^n + 1 mod q computes two transformation functions. With these functions, one can utilize efficient matrix multiplication O(n log n) instead of O(n^2) in the trivial polynomial multiplication for PolynomialRingZq objects.

Currently this implementation only supports n that are a power of two.

Attributes:

• n: the degree of the modulus polynomials
• n_inv: the inverse of n when viewed modulo q
• powers_of_omega: contains a list of n elements, corresponding to the n powers of of the nth root of unity
• powers_of_omega: contains a list of n elements, corresponding to the n powers of of the inverse of the nth root of unity
• powers_of_psi: contains a list of n elements, corresponding to the n powers of of the 2nth root of unity (empty for positively wrapped convolutions)
• powers_of_psi: contains a list of n elements, corresponding to the n powers of of the inverse of the 2nth root of unity (empty for positively wrapped convolutions)
• modulus: a clone of the modulus object the transform is connected to
• convolution_type: tells subsequent algorithms if the convolution is positively or negatively wrapped

Examples

This example is taken from: https://eprint.iacr.org/2024/585.pdf Example 3.8

use qfall_math::integer_mod_q::*;
use std::str::FromStr;

let modulus = Modulus::from(7681);
let poly_mod = ModulusPolynomialRingZq::from_str("5  -1 0 0 0 1 mod 7681").unwrap();
let g_poly = PolyOverZq::from_str("4  1 2 3 4 mod 7681").unwrap();
let h_poly = PolyOverZq::from_str("4  5 6 7 8 mod 7681").unwrap();

let ntt_basis = NTTBasisPolynomialRingZq::init(4, 3383, &modulus, ConvolutionType::Cyclic);

let ghat = ntt_basis.ntt(&g_poly);
let hhat = ntt_basis.ntt(&h_poly);

// simulate entrywise multiplication
let mut ghat_hhat = Vec::new();
for i in 0..4 {
    ghat_hhat.push(&ghat[i] * &hhat[i]);
}

let g_h_poly = ntt_basis.inv_ntt(ghat_hhat);

let g_h_poly_ring = PolynomialRingZq::from((
    g_h_poly.get_representative_least_nonnegative_residue(),
    &poly_mod,
));

// Ensure that multiplication using the NTT and multiplication using
// FLINTs multiplication algorithms yield the same result.
let g_poly_ring = PolynomialRingZq::from((
    g_poly.get_representative_least_nonnegative_residue(),
    &poly_mod,
));
let h_poly_ring = PolynomialRingZq::from((
    h_poly.get_representative_least_nonnegative_residue(),
    &poly_mod,
));

assert_eq!(g_poly_ring * h_poly_ring, g_h_poly_ring)

This example is taken from: https://eprint.iacr.org/2024/585.pdf Example 3.12

use qfall_math::integer_mod_q::*;
use std::str::FromStr;

let modulus = Modulus::from(7681);
let poly_mod = ModulusPolynomialRingZq::from_str("5  1 0 0 0 1 mod 7681").unwrap();
let g_poly = PolyOverZq::from_str("4  1 2 3 4 mod 7681").unwrap();
let h_poly = PolyOverZq::from_str("4  5 6 7 8 mod 7681").unwrap();

let ntt_basis =
    NTTBasisPolynomialRingZq::init(4, 1925, &modulus, ConvolutionType::Negacyclic);

let ghat = ntt_basis.ntt(&g_poly);
let hhat = ntt_basis.ntt(&h_poly);

// simulate entrywise mutliplication
let mut ghat_hhat = Vec::new();
for i in 0..4 {
    ghat_hhat.push(&ghat[i] * &hhat[i])
}

let g_h_poly = ntt_basis.inv_ntt(ghat_hhat);

let g_h_poly_ring = PolynomialRingZq::from((
    g_h_poly.get_representative_least_nonnegative_residue(),
    &poly_mod,
));

// Ensure that multiplication using the NTT and multiplication using
// FLINTs multiplication algorithms yield the same result.
let g_poly_ring = PolynomialRingZq::from((
    g_poly.get_representative_least_nonnegative_residue(),
    &poly_mod,
));
let h_poly_ring = PolynomialRingZq::from((
    h_poly.get_representative_least_nonnegative_residue(),
    &poly_mod,
));

assert_eq!(g_poly_ring * h_poly_ring, g_h_poly_ring)

Fields

n: i64

n_inv: Z

powers_of_omega: Vec<Z>

powers_of_omega_inv: Vec<Z>

powers_of_psi: Vec<Z>

powers_of_psi_inv: Vec<Z>

modulus: Modulus

convolution_type: ConvolutionType

Implementations

impl NTTBasisPolynomialRingZq

pub fn init( n: usize, root_of_unity: impl Into<Z>, modulus: impl Into<Modulus>, convolution_type: ConvolutionType, ) -> Self

This function allows to initialize a NTTBasisPolynomialRingZq object. We currently only allow for two kinds of moduli to accompany the construction: It must be either cyclic (X^n - 1) or negacyclic (X^n + 1) convoluted wrapping (also submitted in the algorithm) and the degree of the polynomial must be a power of two. Only then can we compute a full-split of the polynomial ring. Accordingly, the root_of_unity must be a nth root of unity or respectively a 2nth root of unity.

This function does not check if the provided root of unity is actually a root of unity!

Parameters:

• n: the degree of the polynomial
• root_of_unity: the n-th or 2n-th root of unity
• q: the modulus of the polynomial
• convolution_type: defines whether convolution is cyclic or negacyclic

Examples

use qfall_math::integer_mod_q::Modulus;
use qfall_math::integer_mod_q::NTTBasisPolynomialRingZq;
use qfall_math::integer_mod_q::ConvolutionType;

let modulus = Modulus::from(7681);

// Initializes the NTT for `X^4 - 1 mod 7681`
let ntt_basis =
    NTTBasisPolynomialRingZq::init(4, 3383, &modulus, ConvolutionType::Cyclic);

// Initializes the NTT for `X^4 + 1 mod 7681`
let ntt_basis =
    NTTBasisPolynomialRingZq::init(4, 1925, &modulus, ConvolutionType::Negacyclic);

Panics…

• if n is not a power of two.

impl NTTBasisPolynomialRingZq

pub fn inv_ntt(&self, vector: Vec<Z>) -> PolyOverZq

For a given polynomial viewed in the polynomial ring defined by the self, it computes the inverse NTT.

It computes the iterative Gentleman-Sande transformation algorithm to compute the transform.

Parameters:

• vector: The coefficients of the polynomial when viewed in NTT.

Returns the inverse of the NTT from a vector and returns it as a polynomial.

Examples

use qfall_math::integer::Z;
use qfall_math::integer_mod_q::{Modulus, PolyOverZq, NTTBasisPolynomialRingZq, ConvolutionType};
use std::str::FromStr;

let g_poly = PolyOverZq::from_str("4  1 2 3 4 mod 7681").unwrap();
let modulus = Modulus::from(7681);

let ntt_basis =
    NTTBasisPolynomialRingZq::init(4, 3383, &modulus, ConvolutionType::Cyclic);

let ghat_ntt = vec![
    Z::from(10),
    Z::from(913),
    Z::from(7679),
    Z::from(6764),
];

let ghat_inv_ntt = ntt_basis.inv_ntt(ghat_ntt);

assert_eq!(g_poly, ghat_inv_ntt);

use qfall_math::integer::Z;
use qfall_math::integer_mod_q::{Modulus, PolyOverZq, NTTBasisPolynomialRingZq, ConvolutionType};
use std::str::FromStr;

let g_poly = PolyOverZq::from_str("4  1 2 3 4 mod 7681").unwrap();
let modulus = Modulus::from(7681);

let ntt_basis =
    NTTBasisPolynomialRingZq::init(4, 1925, &modulus, ConvolutionType::Negacyclic);

let ghat_ntt = vec![
    Z::from(1467),
    Z::from(2807),
    Z::from(3471),
    Z::from(7621),
];

let ghat_inv_ntt = ntt_basis.inv_ntt(ghat_ntt);

assert_eq!(g_poly, ghat_inv_ntt);

Panics …

• if it is not reduced, i.e. has a coefficient of degree > n.
• if the modulus differs from the modulus over which we view the polynomial.

The algorithm is based on the Gentleman-Sande algorithm: -[1] Gentleman, W. Morven, and Gordon Sande. “Fast fourier transforms: for fun and profit.” Proceedings of the November 7-10, 1966, fall joint computer conference. 1966.

impl NTTBasisPolynomialRingZq

pub fn ntt(&self, poly: &PolyOverZq) -> Vec<Z>

For a given polynomial viewed in the polynomial ring defined by the self, it computes the NTT.

It computes the iterative Cooley-Tukey transformation algorithm to compute the transform. Polynomials of degree smaller than n-1 are with 0 coefficients.

Parameters:

• poly: The polynomial for which it is desired to compute the NTT

Returns the NTT of a polynomial in the context of the polynomial ring.

Examples

use qfall_math::integer::Z;
use qfall_math::integer_mod_q::{Modulus, PolyOverZq, NTTBasisPolynomialRingZq, ConvolutionType};
use std::str::FromStr;

let g_poly = PolyOverZq::from_str("4  1 2 3 4 mod 7681").unwrap();
let modulus = Modulus::from(7681);

let ntt_basis =
    NTTBasisPolynomialRingZq::init(4, 3383, &modulus, ConvolutionType::Cyclic);

let ghat = ntt_basis.ntt(&g_poly);

let cmp_ghat = vec![
    Z::from(10),
    Z::from(913),
    Z::from(7679),
    Z::from(6764),
];
assert_eq!(cmp_ghat, ghat);

use qfall_math::integer::Z;
use qfall_math::integer_mod_q::{Modulus, PolyOverZq, NTTBasisPolynomialRingZq, ConvolutionType};
use std::str::FromStr;

let g_poly = PolyOverZq::from_str("4  1 2 3 4 mod 7681").unwrap();
let modulus = Modulus::from(7681);

let ntt_basis =
    NTTBasisPolynomialRingZq::init(4, 1925, &modulus, ConvolutionType::Negacyclic);

let ghat = ntt_basis.ntt(&g_poly);

let cmp_ghat = vec![
    Z::from(1467),
    Z::from(2807),
    Z::from(3471),
    Z::from(7621),
];
assert_eq!(cmp_ghat, ghat);

Panics if …

• it is not reduced, i.e. has a coefficient of degree > n
• the modulus differs from the modulus over which we view the polynomial

The algorithm is based on the Cooley-Tukey algorithm: -[1] Cooley, James W., and John W. Tukey. “An algorithm for the machine calculation of complex Fourier series.” Mathematics of computation 19.90 (1965): 297-301.

Trait Implementations

impl Debug for NTTBasisPolynomialRingZq

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.