Skip to content

rnx api

Jump to bottom
Nicolas Gama edited this page Jun 10, 2024 · 2 revisions

Spqlios RNX-arithmetic library

The spqlios arithmetic library provides fast approximate arithmetic over vectors of real polynomials (typically suited for cases where 52 bits of floating point precision are sufficient). It exposes fast prepared vector-matrix and prepared scalar-vector products, internally powered by FFT.

Summary of main modules

double representation of $\mathbb{R}_N[X]$

Definition of the layout

A single small polynomial $\in \mathbb{R}_N[X]$ is represented by its $N$ double coefficients in natural order, forming an double[N] contiguous array.

A vector of $\ell$ small polynomials (i.e. $\mathbb{R}_N[X]^\ell$) is represented by $\ell$ arrays regularly spaced in memory.

Concretely, given the ring dimension uint64_t N, a vector of polynomial is represented by one pointer double* p, the size of the vector ell, and a stride/slice size slice >= N. The $j$-th coefficient of the $i$-th polynomial is at address &p[i*slice+j] (C notation): For $i\in[0,\ell-1]$ and $j\in[0,N-1]$, the double element at this address shall be properly allocated and accessible.

Allocation/deallocation

The double* pointer can be allocated and freed using standard allocators (malloc, new double[], ...), using the default endianess of the machine (usually little-endian on most cpus). The structure can be allocated, filled, and read externally to the library. If the layout is not contiguous (slice is $>N$), the functions of the library will never dereference addresses in the inter-slice space.

Alignment: An alignment of 64-bytes is recommended for speed reasons, but not mandatory. Serialization/IO: fread and fwrite-based are fine. Some care may be needed to make the endianess canonical (TBD)

Representations of $\mathbb{T}_N[X]$

Real numbers modulo 1 can be represented either as:

  • a double whose value in the interval $[-0.5,0.5)$. Functions using this representation are qualified with the prefix or suffix tnxdbl. In this case, the number has $\approx$ 52 bits of precision.
  • an torus32: it shares its bit layout with a 32-bit integers mod $2^{32}$ (a.k.a we can typedef int32_t torus32), but the value it represents is implicitly scaled by a factor $2^{-32}$: If an int32_t x represents an integer value $v\in[-2^{31}; 2^{31}[$ mod $2^{32}$, then the same 32 bits typed as torus32 x represents $v.2^{-32}\in[-0.5,0.5)$ mod 1. torus32 and int32_t arithmetic are bit-wise equivalent: addition, subtraction between two torus32 can use the standard +,- operators, and the external multiplication between an integer and a torus32 can use the * operator. (it also holds for the assembly instructions)

Elementary operations

/**
 * @brief obtain a module for ring dimension N
 * currently, the only module_type supported is FFT64
 */
MOD_RNX* new_rnx_module_info(uint64_t N, MODULE_TYPE mode);
void delete_module_info(MOD_RNX* module_info);
uint64_t module_get_n(const MOD_RNX* module);

/** @brief sets res = 0 */
void vec_rnx_zero(const MOD_RNX* module,                           // N
                  double* res, uint64_t res_size, uint64_t res_sl  // res
);

/** @brief sets res = a */
void vec_rnx_copy(const MOD_RNX* module,                            // N
                  double* res, uint64_t res_size, uint64_t res_sl,  // res
                  const double* a, uint64_t a_size, uint64_t a_sl   // a
);

/** @brief sets res = -a */
void vec_rnx_negate(const MOD_RNX* module,                            // N
                    double* res, uint64_t res_size, uint64_t res_sl,  // res
                    const double* a, uint64_t a_size, uint64_t a_sl   // a
);

/** @brief sets res = a + b */
void vec_rnx_add(const MOD_RNX* module,                            // N
                 double* res, uint64_t res_size, uint64_t res_sl,  // res
                 const double* a, uint64_t a_size, uint64_t a_sl,  // a
                 const double* b, uint64_t b_size, uint64_t b_sl   // b
);

/** @brief sets res = a - b */
void vec_rnx_sub(const MOD_RNX* module,                            // N
                 double* res, uint64_t res_size, uint64_t res_sl,  // res
                 const double* a, uint64_t a_size, uint64_t a_sl,  // a
                 const double* b, uint64_t b_size, uint64_t b_sl   // b
);



/** @brief sets res = a . X^p */
void vec_rnx_rotate(
    const MOD_RNX* module,                            // N
    const int64_t p,                                  // rotation value
    double* res, uint64_t res_size, uint64_t res_sl,  // res
    const double* a, uint64_t a_size, uint64_t a_sl   // a
);

/** @brief sets res = a . (X^p - 1) */
void vec_rnx_mul_xp_minus_one(
    const MOD_RNX* module,                            // N
    const int64_t p,                                  // rotation value
    double* res, uint64_t res_size, uint64_t res_sl,  // res
    const double* a, uint64_t a_size, uint64_t a_sl   // a
);

/** @brief sets res = a(X^p) */
void vec_rnx_automorphism(
    const MOD_RNX* module,                            // N
    int64_t p,                                        // X -> X^p
    double* res, uint64_t res_size, uint64_t res_sl,  // res
    const double* a, uint64_t a_size, uint64_t a_sl   // a
);

/** @brief res = a * b : small polynomial product  */
void rnx_small_single_product(const MOD_RNX* module,  // N
                              double* res,            // output
                              const double* a,        // a
                              const double* b,        // b
                              uint8_t* tmp);          // scratch space

/** @brief res = a * b centermod 1: small polynomial product  */
void tnxdbl_small_single_product(const MOD_RNX* module,  // N
                                 double* torus_res,      // output
                                 const double* int_a,    // a
                                 const double* torus_b,  // b
                                 uint8_t* tmp);          // scratch space

/** @brief res = a * b: small polynomial product  */
void znx32_small_single_product(const MOD_RNX* module, // N
                                int32_t* int_res,      // output
                                const int32_t* int_a,  // a
                                const int32_t* int_b,  // b
                                uint8_t* tmp);         // scratch space

/** @brief res = a * b centermod 1: small polynomial product  */
void tnx32_small_single_product(const MOD_RNX* module,   // N
                                int32_t* torus_res,      // output
                                const int32_t* int_a,    // a
                                const int32_t* torus_b,  // b
                                uint8_t* tmp);           // scratch space

Conversions $\mathbb{R}_N[X]$ to/from $\mathbb{T}_N[X]$ and $\mathbb{Z}_N[X]$ 

void vec_rnx_to_znx32(MOD_RNX* module,                                  // N
                      int32_t* res, uint64_t res_size, uint64_t res_sl, // res
                      const double* a, uint64_t a_size, uint64_t a_sl   // a
);

void vec_rnx_from_znx32(MOD_RNX* module,                                 // N
                        double* res, uint64_t res_size, uint64_t res_sl, // res
                        const int32_t* a, uint64_t a_size, uint64_t a_sl // a
);

void vec_rnx_to_tnx32(MOD_RNX* module,                                  // N
                      int32_t* res, uint64_t res_size, uint64_t res_sl, // res
                      const double* a, uint64_t a_size, uint64_t a_sl   // a
);

void vec_rnx_from_tnx32(MOD_RNX* module,                                 // N
                        double* res, uint64_t res_size, uint64_t res_sl, // res
                        const int32_t* a, uint64_t a_size, uint64_t a_sl // a
);

void vec_rnx_to_tnx32x2(MOD_RNX* module,                                  // N
                        int32_t* res, uint64_t res_size, uint64_t res_sl, // res
                        const double* a, uint64_t a_size, uint64_t a_sl   // a
);

void vec_rnx_from_tnx32x2(MOD_RNX* module,                                 // N
                          double* res, uint64_t res_size, uint64_t res_sl, // res
                          const int32_t* a, uint64_t a_size, uint64_t a_sl // a
);

void vec_rnx_to_tnxdbl(MOD_RNX* module,                                 // N
                       double* res, uint64_t res_size, uint64_t res_sl, // res
                       const double* a, uint64_t a_size, uint64_t a_sl  // a
);

Gadget Approx-Decompositions from $\mathbb{T}_N[X]$ 

/** @brief new gadget: delete with delete_tnx32_approxdec_gadget */
TNX32_APPROXDEC_GADGET* new_tnx32_approxdec_gadget(
    const MOD_RNX* module           // N
    uint64_t k, uint64_t ell        // base 2^K and size
);

/** @brief new gadget: delete with delete_tnx32_approxdec_gadget */
TNXDBL_APPROXDEC_GADGET* new_tnxdbl_approxdec_gadget(
    const MOD_RNX* module,           // N
    uint64_t k, uint64_t ell        // base 2^K and size
);

/** @brief new gadget: delete with delete_tnx32_approxdec_gadget */
TNX32X2_APPROXDEC_GADGET* new_tnx32x2_approxdec_gadget(
    const MOD_RNX* module           // N
    uint64_t k, uint64_t ell        // base 2^K and size
);

/** @brief sets res = gadget_decompose(a) */
void vec_rnx_approxdec_from_tnx32(
    MOD_RNX* module,                                   // N
    const TNX32_APPROXDEC_GADGET* gadget,              // output base 2^K
    double* res, uint64_t res_size, uint64_t res_sl,   // res
    const int32_t* a, uint64_t a_size, uint64_t a_sl  // a
);

/** @brief sets res = gadget_decompose(a) */
void vec_rnx_approxdec_from_tnx32x2(
    const MOD_RNX* module,                             // N
    const TNX32X2_APPROXDEC_GADGET* gadget,            // output base 2^K
    double* res, uint64_t res_size, uint64_t res_sl,   // res
    const int32_t* a, uint64_t a_size, uint64_t a_sl  // a
);

/** @brief sets res = gadget_decompose(a) */
void vec_rnx_approxdec_from_tnxdbl(
    const MOD_RNX* module,                            // N
    const TNXDBL_APPROXDEC_GADGET* gadget,            // output base 2^K
    double* res, uint64_t res_size, uint64_t res_sl,  // res
    const double* a, uint64_t a_size, uint64_t a_sl  // a
);

Vector-matrix products (vmp)

  1. Allocate the space for a pmat matrix to the right dimension

    /** @brief allocates a prepared matrix (release with delete_rnx_vmp_pmat) */
RNX_VMP_PMAT* new_rnx_vmp_pmat(const MOD_RNX* module,           // N
                               uint64_t nrows, uint64_t ncols); // dimensions

// it also is possible to use a standard allocation function: 
// malloc/free, new int8_t[...]/delete[],
// or spqlios_alloc/spqlios_free
// in this case, the number of bytes to allocate are: 

/** @brief number of bytes in a RNX_VMP_PMAT (for manual allocation) */
uint64_t bytes_of_rnx_vmp_pmat(const MOD_RNX* module,           // N
                               uint64_t nrows, uint64_t ncols); // dimensions

  2. Prepare the matrix

    /** @brief prepares a vmp matrix (contiguous row-major version) */
void rnx_vmp_prepare_contiguous(
    MOD_RNX* module,                           // N
    RNX_VMP_PMAT* pmat,               // output
    double* input_mat, nrows, ncols   // a
);

  3. Execute a vector matrix product

    /** @brief applies a vmp product res = a x pmat (result in DFT space) */
void rnx_vmp_apply_tmp_a(
    MOD_RNX* module,                    // N
    double* res, res_size, res_sl       // res
    double* tmpa, a_size, a_sl,         // a (will be overwritten)
    const VMP_PMAT* pmat, nrows, ncols  // prep matrix
);

    It is possible to use dimensions a_size <= nrows and res_size <= ncols. If the dimensions are smaller, this function will do a product with a submatrix.

    tmpa will be overwritten by the function: it the content is important, please copy it beforehand.

  4. Remember that the product is done over $\mathbb{R}_N[X]$. If the result is meant to be mod 1, use the conversion or gadget decomposition functions.

Scalar-vector products (svp)

  1. Allocate the space for a pmat matrix to the right dimension

    /** @brief allocates a prepared matrix (release with delete_rnx_vmp_pmat) */
RNX_SVP_PPOL* new_rnx_svp_ppol(const MOD_RNX* module);   // N

// it also is possible to use a standard allocation function: 
// malloc/free, new int8_t[...]/delete[],
// or spqlios_alloc/spqlios_free
// in this case, the number of bytes to allocate are: 

/** @brief number of bytes in a RNX_VMP_PMAT (for manual allocation) */
uint64_t bytes_of_rnx_svp_ppol(const MOD_RNX* module);   // N

  2. Prepare the vector

    /** @brief prepares a svp polynomial  */
void rnx_svp_prepare(const MOD_RNX* module,  // N
                     RNX_SVP_PPOL* ppol,     // output
                     const double* pol       // a
);

  3. Execute a vector matrix product

    /** @brief apply a svp product, result = ppol * a */
void rnx_svp_apply(
    const MOD_RNX* module,                            // N
    double* res, uint64_t res_size, uint64_t res_sl,  // output
    const RNX_SVP_PPOL* ppol,                         // prepared pol
    const double* a, uint64_t a_size, uint64_t a_sl   // a
);

  4. Remember that the product is done over $\mathbb{R}_N[X]$. If the result is meant to be mod 1, use the conversion or gadget decomposition functions.

SPQlios arithmetic lib and API

General Overview

DFT api

VEC_ZNX arithmetic api

RNX arithmetic api (WIP)

ZN arithmetic api (WIP)

Clone this wiki locally