Complex Structures

Rather than saving Vec<Zq> or Vec<Vec<Zq>> to represent vectors/polynomials and matrices, qFALL-math provides explicit structs with dedicated functionalities that simplify prototyping.

Note that none of the following examples provides an extensive list of possibilities to instantiate structures. Please refer to Random Sampling to create random instances and browse the documentation of qFALL-math to find further options.

Matrices

Each base type (Z, Q, Zq) has a matrix version (MatZ, MatQ, MatZq) that can be instantiated from strings as well as a zero-matrix.

use qfall_math::{integer::MatZ, integer_mod_q::MatZq, rational::MatQ};
use std::str::FromStr;

fn matrix_instantiations() {
    // instantiation of zero matrices
    // the first two parameters define the dimensions (rows x columns)
    let matz = MatZ::new(5, 10);
    let matzq = MatZq::new(5, 10, 13); // the last parameter defines the modulus
    let matq = MatQ::new(5, 10);

    // instantiations using strings
    // the content of a matrix is written in square brackets and
    // one row of the matrix consists of numbers divided by commas in a square bracket
    let matz = MatZ::from_str("[[1,2],[3,4]]").unwrap();
    let matzq = MatZq::from_str("[[1,2],[3,4]] mod 5").unwrap();
    let matq = MatQ::from_str("[[1/2,2],[3/4,4]]").unwrap();

    // explicit conversions between different matrix types
    let matz = matzq.get_representative_least_absolute_residue();
    let matq = MatQ::from(&matz);
}

These matrices can then be modified in various ways, by redefining parts of the matrices, swapping entries, sorting by rows, etc. To enhance usability, these functions additionally provide some Python-like behavior, e.g., a row addressed with -1 refers to the last row of the matrix.

use qfall_math::{integer::MatZ, traits::*};
use std::str::FromStr;

fn manipulation() {
    let mut matz_1 = MatZ::from_str("[[1,2,3],[4,5,6]]").unwrap();
    let matz_2 = MatZ::from_str("[[5,2,7],[4,2,1]]").unwrap();

    // set the 3rd entry of the second row to value 8
    matz_1.set_entry(1, 2, 8).unwrap();
    // set the first row of matz_1 to the values of the second row of matz_2
    matz_1.set_row(0, &matz_2, 1).unwrap();
}

As vectors can be expressed as matrices, we do not implement explicit vector types. Instead, our matrix types provide several functions specific to vectors if they have appropriate dimensions (e.g., a MatZ matrix with dimensions 1 x n). For example, the compututation of several different norms and dot products is available for vectors of type MatZ.

use qfall_math::integer::MatZ;
use std::str::FromStr;

fn vectors() {
    let vecz = MatZ::from_str("[[1/2,2,3/4]]").unwrap();

    let is_vector = vecz.is_vector();

    let dot_product = vecz.dot_product(&vecz);
    let norm = vecz.norm_eucl();
}

Assuming matching dimensions, arithmetic operations between different types of matrices are well-defined and supported naturally. Beyond matrix multiplication, it is also possible to use scalars.

use qfall_math::{
    integer::MatZ,
    rational::{MatQ, Q},
};
use std::str::FromStr;

fn basic_arithmetics() {
    let matq = MatQ::from_str("[[1/2,2,3/4],[4,5/10,6]]").unwrap();
    let vecz = MatZ::from_str("[[1],[4]]").unwrap();
    let matz = MatZ::from_str("[[1,2,3],[4,5,6]]").unwrap();

    let add: MatQ = &matq + &matq;
    let sub: MatQ = &matq - &matz;
    let mul: MatQ = &matq * &vecz;
    let scalar: MatZ = 42 * &matz;
    let scalar: MatQ = Q::from((17, 42)) * &matz;
}

As with Zq, it is also possible to share a Modulus across several matrix instances.

use qfall_math::{
    integer::MatZ,
    integer_mod_q::{MatZq, Modulus, Zq},
};
use std::str::FromStr;

fn shared_moduli() {
    let modulus = Modulus::from(42);
    let matz_1 = MatZ::from_str("[[1,2,3],[4,5,6]]]").unwrap();
    let matz_2 = MatZ::from_str("[[17,42],[89, 100]]]").unwrap();

    let zq = Zq::from((17, &modulus));

    let matzq_1 = MatZq::from((&matz_1, &modulus));
    let matzq_2 = MatZq::from((&matz_2, &modulus));
}

Polynomials

Just like matrices, polynomials are also defined for all base types and the general behavior is comparable to that of vectors for our matrices. You can compute scalars, access/modify individual coefficients and compute various functions. The instantiation from strings is slightly different, as the string format is imported from FLINT to reduce the preprocessing workload.

use qfall_math::{
    integer::PolyOverZ,
    integer_mod_q::{Modulus, PolyOverZq},
    rational::PolyOverQ,
};
use std::str::FromStr;

fn polynomial_instantiations() {
    // instantiations using strings
    // the first number is the number of coefficients in the polynomial,
    // which is followed by the coefficients in ascending order
    let polyz = PolyOverZ::from_str("4  0 1 2 3").unwrap();
    let polyzq = PolyOverZq::from_str("4  0 1 -2 3 mod 42").unwrap();
    let polyq = PolyOverQ::from_str("5  0 1/3 2/10 -3/2 1").unwrap();

    // instantiations using components
    let modulus = Modulus::from_str("100").unwrap();

    let polyzq = PolyOverZq::from(&modulus);
    let polyzq = PolyOverZq::from((&polyz, &modulus));

    let polyq = PolyOverQ::from(&polyz);
}

For polynomials, we support quotient rings of polynomials, where the context/modulus object itself is a PolyOverZq. We treat the modulus in the same fashion as Modulus and defined ModulusPolynomialRingZq, which can be shared among different instantiations.

use qfall_math::{integer_mod_q::{ModulusPolynomialRingZq, PolyOverZq}, traits::*};

fn instantiate_moduli() {
    let mut polyzq = PolyOverZq::from((1, 17)); // 1 mod 17
    polyzq.set_coeff(4, 1); // becomes X^4 + 1 mod 17
    let modulus_poly = ModulusPolynomialRingZq::from(&polyzq);
}

To instantiate common ModulusPolynomialRingZq, please take a look at qFALL-tools::utils::common_moduli.

A PolynomialRingZq can be instantiated from strings or its components.

use qfall_math::integer::PolyOverZ;
use qfall_math::integer_mod_q::{ModulusPolynomialRingZq, PolynomialRingZq};
use std::str::FromStr;

fn ring_instantiations() {
    // instantiations using components
    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 poly_ring = PolynomialRingZq::from((&poly, &modulus));
}