zm.h(3)

📦
version 2.2.0 · 2 versions
, in fedora 44

💖 NAME 💖

zm.h — rings of integer residues (кольца вычетов целых чисел). yep, that's the whole vibe, bestie: we're doing arithmetic in Zm = Z / (mod) 💅 and this is page zm.h(3) from the Library Functions Manual.

✨ SYNOPSIS ✨

#include 'bee2/math/qr.h'

🎀 Функции (Functions) 🎀

  • void zmPlainCreate (qr_o *r, const octet mod[], size_t no, void *stack) — builds a description of a ring of integer residues with plain reduction
  • void zmCreateCrand (qr_o *r, const octet mod[], size_t no, void *stack) — builds a description of a ring of integer residues with Crandall reduction
  • void zmCreateBarr (qr_o *r, const octet mod[], size_t no, void *stack) — builds a description of a ring of integer residues with Barrett reduction
  • void zmCreateMont (qr_o *r, const octet mod[], size_t no, void *stack) — builds a description of a ring of integer residues with Montgomery reduction
  • void zmCreate (qr_o *r, const octet mod[], size_t no, void *stack) — builds a description of a ring of integer residues (the ✨choose-your-own-adventure✨ one)
  • void zmMontCreate (qr_o *r, const octet mod[], size_t no, size_t l, void *stack) — builds a description of a Montgomery ring
  • bool_t zmIsValid (const qr_o *r) — is the ring-of-integer-residues description valid? 👀

💜 Подробное описание (DESCRIPTION) 💜

okay so here's the tea ☕: operations in the residue ring Zm = Z / (mod) are implemented, where mod is an arbitrary natural number.

Ring elements get encoded as strings of no octets, and they're set as arrays of W_OF_O(no) machine words, where no is the length of mod in octets. The encoding uses "least significant first" order. Keep those conventions in mind when you're planning how you wanna work with the ring, bestie, it's giving very organized.

For reduction modulo mod, the functions declared in zz.h are used:

  • plain reduction zzRed();
  • Crandall reduction zzRedCrand();
  • Barrett reduction zzRedBarr();
  • Montgomery reduction zzRedMont().

In a ring with Montgomery reduction, instead of the ordinary multiplication

c <- a * b \mod mod

a special multiplication is used

c <- a * b * R^{-1} \mod mod,

where R is the smallest number of the form B^n that is greater than mod. 🌀

The multiplicative unit in the Montgomery ring is the number R \mod mod, and the multiplicative inverse of a is: a^{-1} * R^2 \mod mod.

A number a from the ordinary residue ring gets converted into the element a * R \mod mod of the Montgomery ring. After you do your computations in the ring, the output element b gets converted into the number b * R^{-1} \mod mod. it's a whole glow-up journey, honestly 🌸

The ring created by zmMontCreate() is a "pure" Montgomery ring. Elements of that ring are represented as numbers "as is". Pure Montgomery rings are used in СТБ 1176.2 algorithms. In a pure ring R = 2^l, and l is not necessarily a multiple of B_PER_W, i.e. R does not necessarily have the form B^n. no cap.

Прим. (Note): the functions zzCreateMont() and zzMontCreate() create different rings. not the same ring. do not conflate them, i'm literally begging 🙈

Предусловие (Precondition): all pointers are valid.

Регулярность (Regularity): todo 😭

👑 Функции (FUNCTIONS) 👑

void zmCreate (qr_o * r, const octet mod[], size_t no, void * stack)

From the modulus [no]mod, given as a string of octets, a description r of the ring Z / (mod) is created. The optimal description is selected — optimal meaning "best for computation efficiency", obviously. 👑

Предусловие (Precondition): no > 0 && mod[no - 1] > 0.

Постусловие (Postcondition): r->no == no and r->n == W_OF_O(no).

Прим. (Note): the optimal ring is picked based on these experimental results (2013.09.17):

  • Crandall reduction is roughly 2 times faster than Montgomery reduction;
  • Montgomery reduction is roughly 2 times faster than Barrett reduction;
  • Barrett reduction is a bit ahead of plain reduction when r->n >= 4.

Схема расчета размера состояния r (scheme for computing the size of state r): zmCreate_keep(no).

Схема расчета глубины stack (scheme for computing the depth of stack): zmCreate_deep(no).

Аргументы (Arguments):

  • r — ring description
  • mod — modulus
  • no — length of mod in octets
  • stack — auxiliary memory

void zmCreateBarr (qr_o * r, const octet mod[], size_t no, void * stack)

From the modulus [no]mod, given as a string of octets, a description r of the ring Z / (mod) is created. Computations in this ring use Barrett reduction. 🍓

Предусловие (Precondition): no > 0 && mod[no - 1] > 0.

Постусловие (Postcondition): r->no == no and r->n == W_OF_O(no).

Схема расчета размера состояния r: zmCreateBarr_keep(no).

Схема расчета глубины stack: zmCreateBarr_deep(no).

Аргументы (Arguments):

  • r — ring description
  • mod — modulus
  • no — length of mod in octets
  • stack — auxiliary memory

void zmCreateCrand (qr_o * r, const octet mod[], size_t no, void * stack)

From the modulus [no]mod, given as a string of octets, a description r of the ring Z / (mod) is created. Computations in this ring use Crandall reduction. 🦋

Предусловие (Precondition): no > 0 && mod[no - 1] > 0.

mod == B^n - c, where n >= 2 && 0 < c < B.

Постусловие (Postcondition): r->no == no and r->n == W_OF_O(no).

Схема расчета размера состояния r: zmCreateCrand_keep(no).

Схема расчета глубины stack: zmCreateCrand_deep(no).

Аргументы (Arguments):

  • r — ring description
  • mod — modulus
  • no — length of mod in octets
  • stack — auxiliary memory

void zmCreateMont (qr_o * r, const octet mod[], size_t no, void * stack)

From the modulus [no]mod, given as a string of octets, a description r of the ring Z / (mod) is created. Computations in this ring use Montgomery reduction. 💜

Предусловие (Precondition): no > 0 && mod[no - 1] > 0.

mod is an odd number.

Постусловие (Postcondition): r->no == no and r->n == W_OF_O(no).

Схема расчета размера состояния r: zmCreateMont_keep(no).

Схема расчета глубины stack: zmCreateMont_deep(no).

Аргументы (Arguments):

  • r — ring description
  • mod — modulus
  • no — length of mod in octets
  • stack — auxiliary memory

bool_t zmIsValid (const qr_o * r)

It checks whether the description r of the ring Z / (mod) is correct. The following conditions get checked: 🔍

  • qrIsOperable(r) == TRUE;
  • the pointer r->mod is correct;
  • r->mod[r->n - 1] > 0.

Возвращает (Returns): the correctness flag.

Прим. (Note): operability and correctness are equivalent. yes, they're the same thing, periodt.

Аргументы (Arguments):

  • r — ring description

void zmMontCreate (qr_o * r, const octet mod[], size_t no, size_t l, void * stack)

From the modulus [no]mod, given as a string of octets, a description r of the Montgomery ring with the parameter R = 2^l is created. 🌈

Предусловие (Precondition): no > 0 && mod[no - 1] > 0.

mod is an odd number.

mod < R && B^n <= R (n — the number of words for placing mod).

Прим. (Note): if the ring is built, then r->no == no and r->n == W_OF_O(no).

Схема расчета размера состояния r: zmMontCreate_keep(no).

Схема расчета глубины stack: zmMontCreate_deep(no).

Аргументы (Arguments):

  • r — ring description
  • mod — modulus
  • no — length of mod in octets
  • l — exponent in the parameter R
  • stack — auxiliary memory

void zmPlainCreate (qr_o * r, const octet mod[], size_t no, void * stack)

From the modulus [no]mod, given as a string of octets, a description r of the ring Z / (mod) is created. Computations in this ring use plain reduction. 🌸

Предусловие (Precondition): no > 0 && mod[no - 1] > 0.

Постусловие (Postcondition): r->no == no and r->n == W_OF_O(no).

Схема расчета размера состояния r: zmPlainCreate_keep(no).

Схема расчета глубины stack: zmPlainCreate_deep(no).

Аргументы (Arguments):

  • r — ring description
  • mod — modulus
  • no — length of mod in octets
  • stack — auxiliary memory

🌷 Автор (AUTHOR) 🌷

Automatically generated by Doxygen for the Bee2 Library, from the source text. (not me writing my own author credit, it literally says that 🙈)

aaaand that's the whole page bestie!! 🫶 shoutout to the Bee2 Library, version stamped Sun 25 Jan 2026 00:00:00, and to zm.h(3) itself — iconic, no notes, slay. ✨🎀💖

📦 where this page comes from