Complex Structures

Rather than saving Vec<Zq> or Vec<Vec<Zq>> to represent vectors/polynomials and matrices, qFALL-math has explicit struct with explicitly implemented functionalities that simplify prototyping.

Matrices

Each base type (Z, Q, Zq) has a matrix version (MatZ, MatQ, MatZq) that can be instantiated from strings or as the all 0 matrix.

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

fn matrix_instantiations() {
    // instantiations using new
    // the first number is the number of rows and the second one the number of columns
    let matz = MatZ::new(5, 10);
    let matzq = MatZq::new(5, 10, 13);
    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();

    // explicitly converting between different 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, … For ease of-usage, these functions also have 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();
}

We do not have explicit vector types like VecZ, VecZq and VecQ, but all matrices can serve as vectors if they have the correct dimensions. On vectors (e.g., a MatZ matrix with dimensions 1 x n) can be used as a normal vector, so you can for instance compute different norms and dot products.

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_sqrd();
}

Assuming matching dimensions, arithmetic operations between different types of matrices are well-defined and supported naturally. Beyond matrix-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 between different matrices.

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 is slightly different, as the string format is imported from FLINT reducing 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 have defined ModulusPolynomialRingZq, which can be shared among different instantiations.

use qfall_math::integer_mod_q::{ModulusPolynomialRingZq, PolyOverZq};
use std::str::FromStr;

fn instantiate_moduli() {
    let polyzq = PolyOverZq::from_str("4  1 0 0 1 mod 17").unwrap();
    let modulus_poly = ModulusPolynomialRingZq::from(&polyzq);
}

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));
}