Introduction

Welcome to the section Getting Started with qFALL-math. qFALL-math is a rust crate for fast number theory with arbitrarily large numbers. It builds upon FLINT and uses the FFI flint-sys to call methods from FLINT. This crate acts as an abstraction layer and takes over all worries regarding memory management. Additionally it provides an easy-to-use interface with easy-to-understand notation and a wide range of operations possible with the related data types.

The crate is a work in progress and will be expanded. If you are missing a feature, an operation or a datatype, feel free to open an issue so we can work on your request.

What does qFALL-math offer?

qFALL-math gives the mathematical foundation to build on. It does not implement cryptographic schemes. It offers several different number types, over which we give a basic overview in the following.

We divide all types into three categories integer, integer_mod_q and rational. Within these categories, we have defined several types:

  • integer
    • integers \(\mathbb Z\) are called Z
    • matrices over integers \(\mathbb Z^{n\times m}\) are called MatZ
    • polynomials over integers \(\mathbb Z[X]\) are called PolyOverZ
    • matrices over polynomials over integers \(\mathbb Z[X]^{n \times m}\) are called MatPolyOverZ
  • integer_mod_q
    • integers modulo a natural number \(\mathbb Z_q\) are called Zq
    • matrices over integers modulo a natural number \(\mathbb Z_q^{n\times m}\) are called MatZq
    • polynomials over integers modulo a natural number \(\mathbb Z_q[X]\) are called PolyOverZq
    • elements of a polynomial ring over integers modulo a natural number \(\mathbb Z_q[X]/\Phi(X)\) are called PolynomialRingZq, where \(\Phi(X)\) is a polynomial over X
    • matrices with elements of a polynomial ring over integers modulo a natural number \(\mathbb Z_q[X]/\Phi(X)^{n \times m}\) are called MatPolynomialRingZq
  • rational
    • rationals \(\mathbb Q\) are called Q
    • matrices over rationals \(\mathbb Q^{n\times m}\) are called MatQ
    • polynomials over integers \(\mathbb Q[X]\) are called PolyOverQ

As this list may be extended and is already relatively long, we will not be able to cover all types in this tutorial. Anyway, our documentation provides examples for every function and should therefore make it easily applicable.

Who is this Section for

Anyone trying to implement code founded on basic number theoretic types. Anyone who wants to implement relatively fast code with reliable memory management.

How to Use this Section

Use this book as a starting point, not as an entire reference. It helps you to get familiar with qFALL-math, but not with Rust. If you are not familiar with Rust, we highly advise you to have a look into the Rust book to get to know the basics.

How is this Section structured?

  1. qFALL-math basics: We show how to instantiate the three base types Z, Zq, Q and introduce some features and present some arithmetics.
  2. qFALL-math advanced types: We present the more advanced types MatZ, PolyZ, PolynomialRingZq and give some intuition on how they work, as all similar types also behave similarly, this allows you to figure out how to use the others.
  3. qFALL-math beyond types: We implement some additional features we want to showcase, such as sampling elements from a certain type.
  4. using qFALL-math: We show how qFALL-math can be used as a building block. Therefore, we implement some cryptographic schemes in a step-by-step tutorial.