zz.h(3)

📦
version 2.2.0 · 2 versions
, in fedora 44

💖 NAME 💖

okay so bestie, welcome to zz.h(3) — straight out of the Library Functions Manual, section 3. This is the header for Большие неотрицательные целые числа — aka big non-negative integers. bignum math, but make it cute. 🫶✨

🦋 SYNOPSIS 🦋

#include 'bee2/defs.h'
#include 'bee2/core/safe.h'

🌸 Функции (the functions, the whole roster) 🌸

  • bool_t zzIsEven (const word a[], size_t n) — is this number even? like, even-even? 👀
  • bool_t zzIsOdd (const word a[], size_t n) — is this number odd?
  • word zzAdd (word c[], const word a[], const word b[], size_t n) — adding numbers together 🧮
  • word zzAdd2 (word b[], const word a[], size_t n) — adding a number into another one
  • word zzAdd3 (word c[], const word a[], size_t n, const word b[], size_t m) — adding numbers of arbitrary length
  • word zzAddW (word b[], const word a[], size_t n, register word w) — adding a number and a word
  • word zzAddW2 (word a[], size_t n, register word w) — adding a word in
  • bool_t zzIsSumEq (const word c[], const word a[], const word b[], size_t n) — does the sum of the numbers equal the number?
  • bool_t zzIsSumWEq (const word b[], const word a[], size_t n, register word w) — does a number plus a word equal the number?
  • word zzSub (word c[], const word a[], const word b[], size_t n) — subtracting numbers
  • word zzSub2 (word b[], const word a[], size_t n) — decrementing a number
  • word zzSubW (word b[], const word a[], size_t n, register word w) — subtracting a word from a number
  • word zzSubW2 (word a[], size_t n, register word w) — decrementing a number by a word
  • void zzNeg (word b[], const word a[], size_t n) — minus. negation. the ✨negative✨ vibe
  • word zzMulW (word b[], const word a[], size_t n, register word w) — multiplying a number by a word
  • word zzAddMulW (word b[], const word a[], size_t n, register word w) — adding the product of a number and a word
  • word zzSubMulW (word b[], const word a[], size_t n, register word w) — subtracting the product of a number and a word
  • void zzMul (word c[], const word a[], size_t n, const word b[], size_t m, void *stack) — multiplying numbers
  • void zzSqr (word b[], const word a[], size_t n, void *stack) — squaring a number
  • bool_t zzSqrt (word b[], const word a[], size_t n, void *stack) — square root extraction
  • word zzDivW (word q[], const word a[], size_t n, register word w) — dividing a number by a machine word
  • word zzModW (const word a[], size_t n, register word w) — remainder from dividing a number by a machine word
  • word zzModW2 (const word a[], size_t n, register word w) — remainder from dividing a number by a small machine word
  • void zzDiv (word q[], word r[], const word a[], size_t n, const word b[], size_t m, void *stack) — dividing numbers
  • void zzMod (word r[], const word a[], size_t n, const word b[], size_t m, void *stack) — remainder from dividing numbers
  • void zzGCD (word d[], const word a[], size_t n, const word b[], size_t m, void *stack) — greatest common divisor
  • bool_t zzIsCoprime (const word a[], size_t n, const word b[], size_t m, void *stack) — are they coprime?
  • void zzLCM (word d[], const word a[], size_t n, const word b[], size_t m, void *stack) — least common multiple
  • void zzExGCD (word d[], word da[], word db[], const word a[], size_t n, const word b[], size_t m, void *stack) — the extended Euclidean algorithm
  • int zzJacobi (const word a[], size_t n, const word b[], size_t m, void *stack) — the Jacobi symbol
  • void zzAddMod (word c[], const word a[], const word b[], const word mod[], size_t n) — modular addition of numbers
  • void zzAddWMod (word b[], const word a[], register word w, const word mod[], size_t n) — modular addition of a number and a word
  • void zzSubMod (word c[], const word a[], const word b[], const word mod[], size_t n) — modular subtraction of numbers
  • void zzSubWMod (word b[], const word a[], register word w, const word mod[], size_t n) — modular subtraction of a word from a number
  • void zzNegMod (word b[], const word a[], const word mod[], size_t n) — additive inversion of numbers modulo
  • void zzMulMod (word c[], const word a[], const word b[], const word mod[], size_t n, void *stack) — modular multiplication of numbers
  • void zzMulWMod (word b[], const word a[], register word w, const word mod[], size_t n, void *stack) — modular multiplication of a number by a word
  • void zzSqrMod (word b[], const word a[], const word mod[], size_t n, void *stack) — modular squaring of numbers
  • void zzInvMod (word b[], const word a[], const word mod[], size_t n, void *stack) — modular inversion
  • void zzDivMod (word b[], const word divident[], const word a[], const word mod[], size_t n, void *stack) — modular division
  • void zzDoubleMod (word b[], const word a[], const word mod[], size_t n) — doubling a number modulo
  • void zzHalfMod (word b[], const word a[], const word mod[], size_t n) — halving a number modulo
  • size_t zzAlmostInvMod (word b[], const word a[], const word mod[], size_t n, void *stack) — almost-inversion modulo
  • bool_t zzRandMod (word a[], const word mod[], size_t n, gen_i rng, void *rng_state) — random residue modulo
  • bool_t zzRandNZMod (word a[], const word mod[], size_t n, gen_i rng, void *rng_state) — random non-zero residue modulo
  • void zzRed (word a[], const word mod[], size_t n, void *stack) — standard reduction
  • void zzRedCrand (word a[], const word mod[], size_t n, void *stack) — Crandall reduction
  • void zzRedBarrStart (word barr_param[], const word mod[], size_t n, void *stack) — Barrett reduction init
  • void zzRedBarr (word a[], const word mod[], size_t n, const word barr_param[], void *stack) — Barrett reduction
  • void zzRedMont (word a[], const word mod[], size_t n, register word mont_param, void *stack) — Montgomery reduction
  • void zzRedCrandMont (word a[], const word mod[], size_t n, register word mont_param, void *stack) — Montgomery reduction modulo a Crandall modulus
  • void zzPowerMod (word c[], const word a[], size_t n, const word b[], size_t m, const word mod[], void *stack) — modular exponentiation
  • word zzPowerModW (register word a, register word b, register word mod, void *stack) — modular exponentiation of a machine word

🧚 ПОДРОБНОЕ ОПИСАНИЕ 🧚 (the detailed description, aka the lore)

💜 ОБЩИЕ ПОЛОЖЕНИЯ 💜 (general setup)

okay so the tea is: this whole thing implements operations on big non-negative integers. no negatives unless you zzNeg them, periodt.

A number is given as an array of machine words: word w[n]. Machine word w[0] is the least significant, machine word w[n - 1] is the most significant. big-endian girlies stay mad, this is little-endian energy. 💅

The empty number (n = 0) counts as zero. yes, a whole zero. iconic.

In the function descriptions, B = 2^{B_PER_W} is the base of the numeral system. 🧮

The function zzDoubleMod(), together with zzAddMod() and zzSubMod(), lets you set up fast modular multiplication of a number by a small constant. for example, computing b <- 7 a \mod mod can be arranged like this:

zzDoubleMod(b, a, mod, n);
zzDoubleMod(b, b, mod, n);
zzDoubleMod(b, b, mod, n);
zzSubMod(b, a, mod, n);

Similarly, zzHalfMod() lets you set up fast modular division by certain constants. 🎀

Предусловие (precondition) — read it, bestie, it's not optional:

  • All input pointers are valid. fr.
  • In the functions that work with numbers, at the memory addresses for the numbers, a number of machine words is reserved that is either clear from context or spelled out in the function descriptions.
  • The auxiliary stack buffer does not overlap with any other buffers.

🌈 РЕДУКЦИЯ 🌈 (reduction)

A reduction consists of determining the residue of the number [2n]a modulo [n]mod. The number being processed always consists of 2n machine words, and the result is always returned in place of a (compare with zzMod()). To make these conventions loud and clear, instead of Mod (remainder of division) we write Red (reduction). different word, different rules, iykyk. 👑

Besides the ordinary reduction, fast reductions over special moduli are also implemented. slay.

🔥 ФУНКЦИИ 🔥 (the functions themselves)

✨ word zzAdd (word c[], const word a[], const word b[], size_t n)

The sum [n]c of the numbers [n]a and [n]b is determined:

c <- (a + b) \mod B^n, carry <- (a + b) \div B^n,
c + B^n * carry == a + b.

Предусловие — the buffer c either does not overlap, or coincides with each of the buffers a, b.

Возвращает — the carry word carry.

Аргументы:

  • c — the sum
  • a — the first addend
  • b — the second addend
  • n — the length of a, b in machine words

✨ word zzAdd2 (word b[], const word a[], size_t n)

The number [n]a is added to the number [n]b:

b <- (a + b) \mod B^n, carry <- (a + b) \div B^n.

Предусловие — the buffer b either does not overlap, or coincides with the buffer a.

Возвращает — the carry word carry.

Аргументы

  • b — первое слагаемое / сумма
  • a — второе слагаемое
  • n — длина a, b в машинных словах

word zzAdd3 (word c[], const word a[], size_t n, const word b[], size_t m)

okay so эта штука складывает два числа, которые могут быть разной длины, и результат по длине = max(n, m). Считается сумма [max(n, m)]с чисел [n]a и [m]b:

c <- (a + b) \mod B^{max(n,m)}, carry <- (a + b) \div B^{max(n,m)}.

Предусловие

Буфер c либо не пересекается, либо совпадает с каждым из буферов a, b.

Возвращает

Слово переноса carry.

Аргументы

  • c — сумма
  • a — первое слагаемое
  • n — длина a в машинных словах
  • b — второе слагаемое
  • m — длина b в машинных словах

void FAST zzAddMod (word c[], const word a[], const word b[], const word mod[], size_t n)

Считается сумма [n]c чисел [n]a и [n]b по модулю [n]mod:

с <- (b + a) \mod mod.
🫶 заметь: тут модуль держит всё в узде, так что сумма не разлетается, periodt.

Предусловие

  • a < mod && b < mod.
  • Буфер c либо не пересекается, либо совпадает с каждым из буферов a, b.
  • Буфер с не пересекается с буфером mod.

Регулярность

Имеется ускоренная нерегулярная редакция.

Аргументы

  • c — сумма
  • a — первое слагаемое
  • b — второе слагаемое
  • mod — модуль
  • n — длина чисел в машинных словах

Перекрестные ссылки

zzAddMod().

Используется в

zzAddMod().

word zzAddMulW (word b[], const word a[], size_t n, register word w)

К числу [n]b добавляется произведение числа [n]a на машинное слово w:

b <- (b + a * w) \mod B^n, carry <- (b + a * w) \div B^n.

Предусловие

Буфер b либо не пересекается, либо совпадает с буфером a.

Возвращает

Слово переноса carry.

Аргументы

  • b — слагаемое / сумма
  • a — первый множитель
  • n — длина a, b в машинных словах
  • w — второй множитель

word zzAddW (word b[], const word a[], size_t n, register word w)

Считается сумма [n]b числа [n]a и слова w:

b <- (a + w) \mod B^n, carry <- (a + w) \div B^n.

Предусловие

Буфер b либо не пересекается, либо совпадает с буфером a.

Возвращает

Слово переноса carry.

Аргументы

  • b — сумма
  • a — первое слагаемое
  • n — длина a в машинных словах
  • w — второе слагаемое

word zzAddW2 (word a[], size_t n, register word w)

К числу [n]a добавляется слово w:

a <- (a + w) \mod B^n, carry <- (a + w) \div B^n.

in-place moment — прибавляем прям в тот же буфер, slay ✨

Возвращает

Слово переноса carry.

Аргументы

  • a — слагаемое / сумма
  • n — длина a в машинных словах
  • w — второе слагаемое

void FAST zzAddWMod (word b[], const word a[], register word w, const word mod[], size_t n)

Считается сумма [n]b числа [n]a и слова w по модулю [n]mod:

b <- (a + w) \mod mod.

Предусловие

  • a < mod && w < mod.
  • Буфер b либо не пересекается, либо совпадает с буфером a.
  • Буфер b не пересекается с буфером mod.

Регулярность

Имеется ускоренная нерегулярная редакция.

Аргументы

  • b — сумма
  • a — первое слагаемое
  • w — второе слагаемое
  • mod — модуль
  • n — длина чисел в машинных словах

Перекрестные ссылки

zzAddWMod().

Используется в

zzAddWMod().

size_t zzAlmostInvMod (word b[], const word a[], const word mod[], size_t n, void * stack)

Считается число [n]b, почти-мультипликативно обратное к [n]a по модулю [n]mod:

b <- a^{-1} * 2^k \mod mod,

где wwBitSize(mod) <= k <= 2 * wwBitSize(mod).

Предусловие

  • mod — нечетное && mod[n - 1] != 0.
  • 0 < a < mod.
  • Буфер b не пересекается с буфером mod.

Ожидается

\gcd (a, mod) == 1.

Возвращает

Параметр k.

Прим.

  • Если \gcd (a, mod) != 1, то b <- 0.
  • Применяя k раз zzHalfMod(), можно определить по b обычный обратный элемент. Применяя n * B_PER_W - k раз zzDoubleMod(), можно определить по b обратный элемент относительно умножения Монтгомери.

Схема расчета глубины stack

zzAlmostInvMod_deep(n).

Регулярность

Функция нерегулярна.

Аргументы

  • b — обратное число
  • a — обращаемое число
  • mod — модуль
  • n — длина чисел в машинных словах
  • stack — вспомогательная память

void zzDiv (word q[], word r[], const word a[], size_t n, const word b[], size_t m, void * stack)

Определяются частное [n - m + 1]q и остаток [m]r от деления числа [n]a на число [m]b:

q <- a \div b, r <- r \mod b,
a == q * b + r, r < b.

Предусловие

  • n >= m.
  • m > 0 && b[m - 1] != 0.
  • Буферы q и r не пересекаются.
  • Буфер r либо не пересекается с буфером a, либо r == a.

Схема расчета глубины stack

zzDiv_deep(n, m).

Регулярность

Функция нерегулярна.

Аргументы

  • q — частное
  • r — остаток
  • a — делимое
  • n — длина a в машинных словах
  • b — делитель
  • m — длина b в машинных словах
  • stack — вспомогательная память

void zzDivMod (word b[], const word divident[], const word a[], const word mod[], size_t n, void * stack)

Определяется частное [n]b от деления числа [n]divident на число [n]a по модулю [n]mod:

b <- divident * a^{-1} \mod mod.

Предусловие

  • mod — нечетное && mod[n - 1] != 0.
  • a, divident < mod.
  • Буфер b не пересекается с буфером mod.

Ожидается

\gcd (a, mod) = 1.

Прим.

Если \gcd (a, mod) != 1, то b <- 0.

Схема расчета глубины stack

zzDivMod_deep(n).

Регулярность

Функция нерегулярна.

Аргументы

  • b — частное
  • divident — делимое
  • a — делитель
  • mod — модуль
  • n — длина чисел в машинных словах
  • stack — вспомогательная память

word zzDivW (word q[], const word a[], size_t n, register word w)

Определяется частное [n]q от деления числа [n]a на машинное слово w:

q <- a \div w.

Предусловие

  • w != 0.
  • Буфер q либо не пересекается, либо совпадает с буфером a.

Возвращает

Остаток от деления.

Аргументы

  • q — частное
  • a — делимое
  • n — длина a в машинных словах
  • w — делитель

void FAST zzDoubleMod (word b[], const word a[], const word mod[], size_t n)

Определяется произведение [n]b числа [n]a на число 2 по модулю [n]mod:

b <- 2 * a \mod mod.

умножить на двойку, но по модулю — iconic behavior 💅

Предусловие

  • a < mod.
  • Буфер b либо не пересекается, либо совпадает с буфером a.
  • Буфер b не пересекается с буфером mod.

Регулярность

Имеется ускоренная нерегулярная реализация.

Аргументы

  • b — произведение
  • a — множитель
  • mod — модуль
  • n — длина чисел в машинных словах

Перекрестные ссылки

zzDoubleMod().

Используется в

zzDoubleMod().

void zzExGCD (word d[], word da[], word db[], const word a[], size_t n, const word b[], size_t m, void * stack)

Определяется наибольший общий делитель [min(n, m)]d чисел [n]a и [m]b:

d <- \gcd(a, b),

а также положительные числа [m]da и [n]db (коэффициенты Безу) такие, что

da * a - db * b == d

Предусловие

  • a != 0 && b != 0.
  • Буферы d, da, db не пересекаются между собой и с буферами a, b.

Схема расчета глубины stack

zzExGCD_deep(n, m).

Регулярность

Функция нерегулярна.

Аргументы

  • d — н.о.д.
  • da — первый коэффициент Безу
  • db — второй коэффициент Безу
  • a — первое число
  • n — длина a в машинных словах
  • b — второе число
  • m — длина b в машинных словах
  • stack — вспомогательная память

void zzGCD (word d[], const word a[], size_t n, const word b[], size_t m, void * stack)

Определяется наибольший общий делитель [min(n, m)]d чисел [n]a и [m]b:

d <- \gcd(a, b).

Предусловие

  • a != 0 && b != 0.
  • Буфер d не пересекается с буферами a и b.

Прим.

  • Использование нулевых a и b запрещается для того, чтобы наибольший общий делитель d укладывался в [min(n, m)] слов.
  • Считается, что \gcd (0, b) = b, в частности, \gcd (0, 0) = 0.

Схема расчета глубины stack

zzGCD_deep(n, m).

Регулярность

Функция нерегулярна.

🎀 Аргументы 🎀

  • d — н.о.д.
  • a — первое число
  • n — длина a в машинных словах
  • b — второе число
  • m — длина b в машинных словах
  • stack — вспомогательная память

✨ void FAST zzHalfMod (word b[], const word a[], const word mod[], size_t n) ✨

Окей так вот, эта функция находит частное [n]b от деления числа [n]a на число 2 по модулю [n]mod, типа:

b <- a * 2^{-1} \mod mod.

Предусловие 💅

  • mod — нечетное && mod[n - 1] != 0.
  • a < mod.
  • Буфер b либо не пересекается, либо совпадает с буфером a.
  • Буфер b не пересекается с буфером mod.

Регулярность

Имеется ускоренная нерегулярная реализация. no cap ✨

Аргументы

  • b — частное
  • a — делимое
  • mod — модуль
  • n — длина чисел в машинных словах

Перекрестные ссылки — zzHalfMod().

Используется в — zzHalfMod().

🌸 void zzInvMod (word b[], const word a[], const word mod[], size_t n, void * stack) 🌸

Тут определяется число [n]b, мультипликативно обратное к [n]a по модулю [n]mod, вот так:

b <- a^{-1} \mod mod.

Предусловие 🫶

  • mod — нечетное && mod[n - 1] != 0.
  • a < mod.
  • Буфер b не пересекается с буфером mod.

Ожидается

\gcd (a, mod) == 1.

Прим.

Если \gcd (a, mod) != 1, то b <- 0. ngl это важно, bestie 🫠

Схема расчета глубины stack

zzInvMod_deep(n).

Регулярность

Функция нерегулярна. periodt 💀

Аргументы

  • b — обратное число
  • a — обращаемое число
  • mod — модуль
  • n — длина чисел в машинных словах
  • stack — вспомогательная память

🦋 bool_t zzIsCoprime (const word a[], size_t n, const word b[], size_t m, void * stack) 🦋

Проверяется, что числа [n]a и [m]b взаимно просты, а именно:

\gcd(a, b) == 1?

Возвращает

Признак взаимной простоты a и b. ✨

Схема расчета глубины stack

zzIsCoprime_deep(n, m).

Регулярность

Функция нерегулярна.

Аргументы

  • a — первое число
  • n — длина a в машинных словах
  • b — второе число
  • m — длина b в машинных словах
  • stack — вспомогательная память

💖 bool_t zzIsEven (const word a[], size_t n) 💖

Проверяется, что число [n]a является четным. Просто чек, чет или нет.

Возвращает

Признак четности.

Аргументы

  • a — число
  • n — длина a в машинных словах

💜 bool_t zzIsOdd (const word a[], size_t n) 💜

Проверяется, что число [n]a является нечетным. Обратный вайб от zzIsEven(), iykyk ✨

Возвращает

Признак нечетности.

Аргументы

  • a — число
  • n — длина a в машинных словах

🔥 bool_t FAST zzIsSumEq (const word c[], const word a[], const word b[], size_t n) 🔥

Проверяется, что сумма чисел [n]a и [n]b равняется числу [n]c:

a + b == c?

Прим.

Переставляя операнды, можно проверять не только суммы, но и разности. chef's kiss, fr fr 👑

Возвращает

Признак равенства.

Регулярность

Имеется ускоренная нерегулярная редакция.

Аргументы

  • c — сумма
  • a — первое слагаемое
  • b — второе слагаемое
  • n — длина a, b, c в машинных словах

Перекрестные ссылки — zzIsSumEq().

Используется в — zzIsSumEq().

⭐ bool_t FAST zzIsSumWEq (const word b[], const word a[], size_t n, register word w) ⭐

Проверяется, что сумма числа [n]a и слова w равняется числу [n]b:

a + w == b?

Возвращает

Признак равенства.

Регулярность

Имеется ускоренная нерегулярная редакция.

Аргументы

  • b — сумма
  • a — первое слагаемое
  • n — длина a, b в машинных словах
  • w — второе слагаемое

Перекрестные ссылки — zzIsSumWEq().

Используется в — zzIsSumWEq().

🌈 int zzJacobi (const word a[], size_t n, const word b[], size_t m, void * stack) 🌈

Определяется символ Якоби (a / b) чисел [n]a и [m]b. Это математика, но мы справляемся 💅

Предусловие

b — нечетное.

Прим.

Если b является произведением простых p_1, p_2,.., p_k, то (a / b) = (a / p_1) * (a / p_2) *... * (a / p_k). Здесь (a / p_i) — символ Лежандра: (a / p) равняется 0, если a делится на p, равняется 1, если a — квадратичный вычет \mod p, и равняется -1 в остальных случаях.

Возвращает

Символ Якоби (a / b): 0, 1 или -1.

Схема расчета глубины stack

zzJacobi_deep(n, m).

Регулярность

Функция нерегулярна.

Аргументы

  • a — первое число
  • n — длина a в машинных словах
  • b — второе число
  • m — длина b в машинных словах
  • stack — вспомогательная память

🍓 void zzLCM (word d[], const word a[], size_t n, const word b[], size_t m, void * stack) 🍓

Определяется наименьшее общее кратное [n + m]d чисел [n]a и [m]b:

d <- \lcm[a, b].

Предусловие

  • a != 0 && b != 0.
  • Буфер d не пересекается с буферами a и b.

Прим.

Использование нулевых a и b запрещается для согласованости с zzGCD() и избежания разбора редких, неиспользуемых на практике случаев. lowkey справедливо 🤷‍♀️

Схема расчета глубины stack

zzLCM_deep(n, m).

Регулярность

Функция нерегулярна.

Аргументы

  • d — н.о.к.
  • a — первое число
  • n — длина a в машинных словах
  • b — второе число
  • m — длина b в машинных словах
  • stack — вспомогательная память

🧚 void zzMod (word r[], const word a[], size_t n, const word b[], size_t m, void * stack) 🧚

Определяется остаток [m]r от деления числа [n]a на число [m]b:

a <- a \mod b.

Предусловие

  • m > 0 && b[m - 1] != 0.
  • Буфер r либо не пересекается с буфером a, либо r == a.

Схема расчета глубины stack

zzMod_deep(n, m).

Регулярность

Функция нерегулярна.

Аргументы

  • r — остаток
  • a — делимое
  • n — длина a в машинных словах
  • b — делитель
  • m — длина b в машинных словах
  • stack — вспомогательная память

🌸 word zzModW (const word a[], size_t n, register word w) 🌸

Определяется остаток от деления числа [n]a на машинное слово w:

r <- a \mod w.

Предусловие

w != 0.

Возвращает

Остаток от деления r.

Аргументы

  • a — делимое
  • n — длина a в машинных словах
  • w — делитель

🎀 word zzModW2 (const word a[], size_t n, register word w) 🎀

Определяется остаток от деления числа [n]a на малое машинное слово w:

r <- a \mod w.

Предусловие

w != 0 && w^2 <= B.

Возвращает

Остаток от деления r.

Прим.

Функция zzModW2() работает быстрее zzModW() на тех платформах, где деление не менее чем в 2 раза медленнее умножения. obsessed с этой оптимизацией ✨

Аргументы

  • a — делимое
  • n — длина a в машинных словах
  • w — делитель

💅 void zzMul (word c[], const word a[], size_t n, const word b[], size_t m, void * stack) 💅

Определяется произведение [n + m]c чисел [n]a на [m]b:

c <- a * b.

Предусловие

Буфер c не пересекается с буферами a и b.

Схема расчета глубины stack

zzMul_deep(n, m).

Аргументы

  • c — произведение
  • a — первый множитель
  • n — длина a в машинных словах
  • b — второй множитель
  • m — длина b в машинных словах
  • stack — вспомогательная память

🌈 void zzMulMod (word c[], const word a[], const word b[], const word mod[], size_t n, void * stack) 🌈

Определяется произведение [n]c чисел [n]a и [n]b по модулю [n]mod:

c <- a * b \mod mod.

Предусловие

  • n > 0 && mod[n - 1] != 0.
  • a < mod && b < mod.

Схема расчета глубины stack

zzMulMod_deep(n).

Аргументы

  • c — произведение
  • a — первый множитель
  • b — второй множитель
  • mod — модуль
  • n — длина чисел в машинных словах
  • stack — вспомогательная память

🦋 word zzMulW (word b[], const word a[], size_t n, register word w) 🦋

Определяется произведение [n]b числа [n]a на слово w:

b <- (a * w) \mod B^n, carry <- (a * w) \div B^n.

Предусловие

Буфер b либо не пересекается, либо совпадает с буфером a.

Возвращает

Слово переноса carry.

Аргументы

  • b — произведение
  • a — первый множитель
  • n — длина a, b в машинных словах
  • w — второй множитель

🌸 zzMulWMod — умножение на слово по модулю 🌸

   void zzMulWMod (word b[], const word a[], register word w, const word mod[],
       size_t n, void * stack)

Окей, bestie, вот эта функция вычисляет произведение [n]b числа [n]a на слово w по модулю [n]mod. Звучит как матан? Не, это просто:

b <- a * w \mod mod.

Предусловие (да, проверь, а то будет больно):

  • <yellow>n > 0 && mod[n - 1] != 0.</yellow>
  • <yellow>a < mod.</yellow>

Схема расчета глубины stack:

zzMulWMod_deep(n).

Аргументы:

  • b — произведение 💖
  • a — первый множитель ✨
  • w — второй множитель 🎀
  • mod — модуль 🦋
  • n — длина чисел в машинных словах 🌸
  • stack — вспомогательная память 💅

💜 zzNeg — отрицательное число по модулю B^n 💜

   void zzNeg (word b[], const word a[], size_t n)

Тут мы получаем число [n]b, отрицательное к [n]a по модулю B^n. Это как «отрицательный вайб», но математический:

b <- B^n - a.

Предусловие:

  • Буфер b либо не пересекается, либо совпадает с буфером a. (Да, можно и так, и так, но не иначе!)

Аргументы:

  • b — отрицательное число 🙈
  • a — число ✨
  • n — длина a в машинных словах 🌸

🔥 zzNegMod — аддитивно обратное по модулю 🔥

   void FAST zzNegMod (word b[], const word a[], const word mod[], size_t n)

А вот это уже аддитивно обратное число [n]b к [n]a по модулю [n]mod. То есть:

b <- -a \mod mod.

Предусловие:

  • <yellow>n > 0 && mod[n - 1] != 0.</yellow>
  • <yellow>a < mod.</yellow>
  • Буфер b либо не пересекается, либо совпадает с буфером a.
  • Буфер b не пересекается с буфером mod.

Регулярность:

Имеется ускоренная нерегулярная редакция. (Типа есть быстрый вариант, но он нерегулярный, iykyk.)

Аргументы:

  • b — обратное число 💖
  • a — число ✨
  • mod — модуль 🦋
  • n — длина чисел в машинных словах 🌸

Перекрестные ссылки zzNegMod().

Используется в zzNegMod().

(Да, это выглядит как рекурсия, но так в оригинале. Мы просто копируем факты.)

👑 zzPowerMod — возведение в степень по модулю 👑

   void zzPowerMod (word c[], const word a[], size_t n, const word b[], size_t
       m, const word mod[], void * stack)

Определяется число [n]c, которое является [m]b-ой степенью числа [n]a по модулю [n]mod. Это как pow(), но с модулем:

c <- a^b \mod mod.

Предусловие:

  • <yellow>n > 0 && mod[n - 1] != 0.</yellow>
  • <yellow>a < mod.</yellow>

Прим.:

  • <rainbow>0^0 == 1.</rainbow> (Да, ноль в нулевой — это единица, не спорь.)

Схема расчета глубины stack:

zzPowerMod_deep(n, m).

Регулярность:

todo (пока todo, bestie, не спрашивай.)

Аргументы:

  • c — степень 💖
  • a — основание ✨
  • n — длина a, mod в машинных словах 🌸
  • b — показатель 🎀
  • m — длина b в машинных словах 🦋
  • mod — модуль 💅
  • stack — вспомогательная память 💜

⭐ zzPowerModW — степень по модулю машинного слова ⭐

   word zzPowerModW (register word a, register word b, register word mod, void
       * stack)

Определяется b-ая степень числа a по модулю машинного слова mod. Возвращает степень.

Предусловие:

  • <yellow>mod != 0.</yellow>

Возвращает:

  • Степень.

Схема расчета глубины stack:

zzPowerModW_deep().

Регулярность:

todo (опять todo, ну такое.)

Аргументы:

  • a — основание 💖
  • b — показатель ✨
  • mod — модуль 🦋
  • stack — вспомогательная память 🌸

🎲 zzRandMod — случайный вычет по модулю 🎲

   bool_t zzRandMod (word a[], const word mod[], size_t n, gen_i rng, void *
       rng_state)

С помощью генератора rng с состоянием rng_state определяется случайный вычет [n]a по модулю [n]mod. То есть:

a <-R {0, 1,..., mod - 1}.

Предусловие:

  • <yellow>n > 0 && mod[n - 1] != 0.</yellow>
  • Буфер a не пересекается с буфером mod.

Возвращает:

  • Признак успеха. (Типа true/false, но у них свой тип.)

Прим.:

  • Если <cyan>2^{l - 1} <= mod < 2^l</cyan>, то для генерации a потребуется <cyan>O_OF_B(l) * 2^l / mod <= 2 * O_OF_B(l)</cyan> случайных октетов rng в среднем.
  • Если rng выдает данные низкого статистического качества, то для генерации может потребоваться больше октетов, чем указано выше. Более того, как только количество потребовавшихся октетов превысит определенный порог d, будет возвращен отрицательный результат. Порог d выбирается так, что вероятность события "для генерации потребуется d истинно случайных октетов" не превосходит <red>2^{-B_PER_IMPOSSIBLE}</red>.

Регулярность:

Время выполнения может флуктуировать. По времени выполнения можно судить о выходных данных rng, но не тех, которые используются для формирования a.

Аргументы:

  • a — случайное число 💖
  • mod — модуль ✨
  • n — длина a и mod в машинных словах 🌸
  • rng — генератор случайных чисел 🎀
  • rng_state — состояние генератора 🦋

🚫 zzRandNZMod — случайный ненулевой вычет 🚫

   bool_t zzRandNZMod (word a[], const word mod[], size_t n, gen_i rng, void *
       rng_state)

С помощью генератора rng с состоянием rng_state определяется случайный ненулевой вычет [n]a по модулю [n]mod:

a <-R {1, 2,..., mod - 1}.

Предусловие:

  • <yellow>n > 0 && mod[n - 1] != 0 && mod != 1.</yellow>
  • Буфер a не пересекается с буфером mod.

Возвращает:

  • Признак успеха.

Прим.:

  • Если <cyan>2^{l - 1} <= mod < 2^l</cyan>, то для генерации a потребуется <cyan>O_OF_B(l) * 2^l / (mod - 1) ≤ 2^l / (2^{l - 1} - 1) O_OF_B(l)</cyan> случайных октетов rng в среднем.
  • Повторяется последнее замечание по функции zzRandMod().

Регулярность:

Время выполнения может флуктуировать. По времени выполнения можно судить о выходных данных rng, но не тех, которые используются для формирования a.

Аргументы:

  • a — случайное число 💖
  • mod — модуль ✨
  • n — длина a и mod в машинных словах 🌸
  • rng — генератор случайных чисел 🎀
  • rng_state — состояние генератора 🦋

🔄 zzRed — остаток от деления 🔄

   void zzRed (word a[], const word mod[], size_t n, void * stack)

Определяется остаток [n]a от деления числа [2n]a на модуль [n]mod.

Предусловие:

  • <yellow>n >= 1 && mod[n - 1] != 0.</yellow>
  • Буферы a и mod не пересекаются.

Схема расчета глубины stack:

zzRed_deep(n).

Регулярность:

Функция нерегулярна. (Типа не жди стабильности, детка.)

Аргументы:

  • a — делимое / остаток 💖
  • mod — модуль ✨
  • n — длина mod в машинных словах 🌸
  • stack — вспомогательная память 🎀

🏎️ zzRedBarr — редукция Барретта 🏎️

   void FAST zzRedBarr (word a[], const word mod[], size_t n, const word
       barr_param[], void * stack)

Определяется остаток [n]a от деления числа [2n]a на модуль [n]mod. При вычислениях используется параметр Барретта [n + 2]barr_param.

Предусловие:

  • <yellow>n > 0 && mod[n - 1] != 0.</yellow>
  • Буфер a не пересекается с буфером mod.

Ожидается:

  • barr_param рассчитан с помощью функции zzRedBarrStart().

Схема расчета глубины stack:

zzRedBarr_deep(n).

Регулярность:

Имеется ускоренная нерегулярная редакция.

Аргументы:

  • a — делимое / остаток 💖
  • mod — модуль ✨
  • n — длина mod в машинных словах 🌸
  • barr_param — параметр Барретта 🎀
  • stack — вспомогательная память 🦋

Перекрестные ссылки zzRedBarr().

Используется в zzRedBarr().

🧮 zzRedBarrStart — старт параметра Барретта 🧮

   void zzRedBarrStart (word barr_param[], const word mod[], size_t n, void *
       stack)

По модулю [n]mod определяется параметр [n + 2]barr_param:

barr_param <- B^{2n} \div mod.

Этот параметр используется в редукции Барретта.

Предусловие:

  • <yellow>n > 0 && mod[n] != 0.</yellow>
  • Буферы barr_param и mod не пересекаются.

Схема расчета глубины stack:

zzRedBarrStart_deep(n).

Аргументы:

  • barr_param — параметр Барретта 💖
  • mod — модуль ✨
  • n — длина mod в машинных словах 🌸
  • stack — вспомогательная память 🎀

🌈 zzRedCrand — редукция Крэндалла 🌈

   void FAST zzRedCrand (word a[], const word mod[], size_t n, void * stack)

Определяется остаток [n]a от деления числа [2n]a на модуль [n]mod, который близок снизу к B^n.

Предусловие:

  • <yellow>n >= 2 && mod[n - 1] != 0.</yellow>
  • Модуль mod имеет вид <cyan>B^n - c</cyan>, где <cyan>0 < c < B</cyan>.
  • Буферы a и mod не пересекаются.

Схема расчета глубины stack:

zzRedCrand_deep(n).

Регулярность:

Имеется ускоренная нерегулярная редакция.

Аргументы:

  • a — делимое / остаток 💖
  • mod — модуль Крэндалла ✨
  • n — длина mod в машинных словах 🌸
  • stack — вспомогательная память (не исп.) 🎀

Перекрестные ссылки zzRedCrand().

Используется в zzRedCrand().

💎 zzRedCrandMont — редукция Монтгомери для Крэндалла 💎

   void FAST zzRedCrandMont (word a[], const word mod[], size_t n, register
       word mont_param, void * stack)

Определяется результат [n]a редукции Монтгомери числа [2n]a по модулю [n]mod, который близок снизу к B^n:

a <- a * R^{-1} \mod mod, R == B^n.

При вычислениях используется параметр Монтгомери mont_param.

Предусловие:

  • <yellow>n >= 2 && mod -- нечетное && mod имеет вид B^n - c, где 0 < c < B.</yellow>
  • <yellow>a < mod * R.</yellow>
  • mont_param рассчитан с помощью функции wordNegInv().
  • Буфер a не пересекается с буфером mod.

Схема расчета глубины stack:

zzRedCrandMont_deep(n).

✨ Регулярность ✨

Имеется ускоренная нерегулярная редакция.

Это всё, что дока говорит по этому поводу 💅 просто знай: помимо обычной версии есть ещё ускоренная нерегулярная. Не спрашивай меня, как она выглядит внутри — дока молчит, и я тоже молчу 🫶

🎀 Аргументы 🎀

  • a — входное число / результат
  • mod — модуль
  • n — длина mod в машинных словах
  • mont_param — параметр Монтгомери
  • stack — вспомогательная память

🦋 Перекрестные ссылки 🦋

zzRedCrandMont().

🌸 Используется в 🌸

zzRedCrandMont().

void FAST zzRedMont (word a[], const word mod[], size_t n, register word mont_param, void * stack)

Определяется результат [n]a редукции Монтгомери числа [2n]a по модулю [n]mod:

a <- a * R^{-1} \mod mod, R == B^n.

При вычислениях используется параметр Монтгомери mont_param.

Предусловие

  • mod — нечетное && mod[n - 1] != 0.
  • a < mod * R.
  • mont_param рассчитан с помощью функции wordNegInv().
  • Буфер a не пересекается с буфером mod.

Прим.

Редукция предложена в статье [Montgomery P. L. Modular multiplication without trial division. Mathematics of Computation, 44(170): 519–521, 1985].

То есть у нас тут целая научная родословная, bestie — 1985 год, серьёзная академическая имба 📜✨

Схема расчета глубины stack

zzRedMont_deep(n).

Регулярность

Имеется ускоренная нерегулярная редакция.

Аргументы

  • a — входное число / результат
  • mod — модуль
  • n — длина mod в машинных словах
  • mont_param — параметр Монтгомери
  • stack — вспомогательная память

Перекрестные ссылки

zzRedMont().

Используется в

zzRedMont().

void zzSqr (word b[], const word a[], size_t n, void * stack)

Определяется квадрат [2n]b числа [n]a:

b <- a * a.

Предусловие

Буфер b не пересекается с буфером a.

Схема расчета глубины stack

zzSqr_deep(n).

Аргументы

  • b — квадрат
  • a — множитель
  • n — длина a в машинных словах
  • stack — вспомогательная память

void zzSqrMod (word b[], const word a[], const word mod[], size_t n, void * stack)

Определяется квадрат [n]b числа [n]a по модулю [n]mod:

b <- a * a \mod mod.

Предусловие

  • n > 0 && mod[n - 1] != 0.
  • a < mod.

Схема расчета глубины stack

zzSqrMod_deep(n).

Аргументы

  • b — квадрат
  • a — множитель
  • mod — модуль
  • n — длина чисел в машинных словах
  • stack — вспомогательная память

bool_t zzSqrt (word b[], const word a[], size_t n, void * stack)

Определяется максимальное целое [(n + 1) / 2]b, квадрат которого не превосходит [n]a:

b <- \floor(\sqrt(a)).

Возвращает

Признак того, что a является полным квадратом (a == b * b).

Предусловие

Буфер b не пересекается с буфером a.

Схема расчета глубины stack

zzSqrt_deep(n).

Регулярность

Функция нерегулярна: условные переходы, нерегулярные блоки.

Так и написано — нерегулярна, вот прям буквально. Условные переходы, нерегулярные блоки, вот это всё 😭 Не жди от неё ровного тайминга, она живёт как хочет 🦋

Аргументы

  • b — квадратный корень
  • a — число
  • n — длина a в машинных словах
  • stack — вспомогательная память

word zzSub (word c[], const word a[], const word b[], size_t n)

Определяется разность [n]c чисел [n]a и [n]b:

c <- (a - b) \mod B^n, borrow <- (a < b),
c - B^n * borrow == a - b.

Предусловие

Буфер c либо не пересекается, либо совпадает с каждым из буферов a, b.

Возвращает

Слово заема borrow.

Аргументы

  • c — разность
  • a — уменьшаемое
  • b — вычитаемое
  • n — длина a, b в машинных словах

word zzSub2 (word b[], const word a[], size_t n)

Число [n]b уменьшается на число [n]a:

b <- (b - a) \mod B^n, borrow <- (b < a).

Предусловие

Буфер c либо не пересекается, либо совпадает с каждым из буферов a, b.

Окей, тут реальный момент: в доке буквально написано «Буфер c», хотя параметра c у этой функции вообще нет 🙈 Я это не правлю и не «улучшаю» — переношу ровно как в исходнике, а ты просто держи в голове, что там так написано, фр фр.

Возвращает

Слово заема borrow.

Аргументы

  • b — уменьшаемое / разность
  • a — вычитаемое
  • n — длина a, b в машинных словах

void FAST zzSubMod (word c[], const word a[], const word b[], const word mod[], size_t n)

Определяется разность [n]с чисел [n]a и [n]b по модулю [n]mod:

c <- (a - b) \mod mod.

Предусловие

  • n > 0 && mod[n - 1] != 0.
  • a < mod && b < mod.
  • Буфер c либо не пересекается, либо совпадает с каждым из буферов a, b.
  • Буфер с не пересекается с буфером mod.

Регулярность

Имеется ускоренная нерегулярная редакция.

Аргументы

  • c — разность
  • a — уменьшаемое
  • b — вычитаемое
  • mod — модуль
  • n — длина чисел в машинных словах

Перекрестные ссылки

zzSubMod().

Используется в

zzSubMod().

word zzSubMulW (word b[], const word a[], size_t n, register word w)

Из числа [n]b вычитается произведение числа [n]a на машинное слово w:

b <- (b - a * w) \mod B^n, carry <- (b < a * w).

Предусловие

Буфер b либо не пересекается, либо совпадает с буфером a.

Возвращает

Слово заема borrow.

Аргументы

  • b — вычитаемое / разность
  • a — первый множитель
  • n — длина a, b в машинных словах
  • w — второй множитель

word zzSubW (word b[], const word a[], size_t n, register word w)

Определяется разность [n]b числа [n]a и слова w:

b <- (a - w) \mod B^n, borrow <- (a < w).

Предусловие

Буфер b либо не пересекается, либо совпадает с буфером a.

Возвращает

Слово заема borrow.

Аргументы

  • b — разность
  • a — уменьшаемое
  • n — длина a в машинных словах
  • w — вычитаемое

word zzSubW2 (word a[], size_t n, register word w)

Число [n]a уменьшается на слово w:

a <- (a - w) \mod B^n, borrow <- (a < w).

Возвращает

Слово заема borrow.

Аргументы

  • a — уменьшаемое / разность
  • n — длина a в машинных словах
  • w — вычитаемое

void FAST zzSubWMod (word b[], const word a[], register word w, const word mod[], size_t n)

Определяется разность [n]b числа [n]a и слова w по модулю [n]mod:

b <- (a - w) \mod mod.

Предусловие

  • a < mod && w < mod.
  • Буфер b либо не пересекается, либо совпадает с буфером a.
  • Буфер b не пересекается с буфером mod.

Регулярность

Имеется ускоренная нерегулярная редакция.

Аргументы

  • b — разность
  • a — уменьшаемое
  • w — вычитаемое
  • mod — модуль
  • n — длина чисел в машинных словах

Перекрестные ссылки

zzSubWMod().

Используется в

zzSubWMod().

👑 Автор 👑

Автоматически создано Doxygen для Библиотека Bee2 из исходного текста.

То есть да, bestie, эту доку не человек писал с любовью, а Doxygen нагенерил из исходников — и всё равно получилось читаемо, я считаю это маленьким чудом ✨💖

И вот мы дошли до самого низа страницы, и там подпись: Библиотека Bee2, версия-дата Вс 25 Янв 2026 00:00:00 и имя страницы zz.h(3) — всё, конец, ты дожил(а) до футера, это буквально финальный босс доки 🎀👑 Атте, слэй, периодт, иди пиши код 🫶💅

📦 where this page comes from