zz.h - Man Page

Большие неотрицательные целые числа

Synopsis

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

bool_t zzIsEven (const word a[], size_t n)
Четное число?
bool_t zzIsOdd (const word a[], size_t n)
Нечетное число?
word zzAdd (word c[], const word a[], const word b[], size_t n)
Сложение чисел
word zzAdd2 (word b[], const word a[], size_t n)
Добавление числа
word zzAdd3 (word c[], const word a[], size_t n, const word b[], size_t m)
Сложение чисел проивольной длины
word zzAddW (word b[], const word a[], size_t n, register word w)
Сложение числа со словом
word zzAddW2 (word a[], size_t n, register word w)
Добавление слова
bool_t zzIsSumEq (const word c[], const word a[], const word b[], size_t n)
Сумма чисел равняется числу?
bool_t zzIsSumWEq (const word b[], const word a[], size_t n, register word w)
Сумма числа и слова равняется числу?
word zzSub (word c[], const word a[], const word b[], size_t n)
Вычитание чисел
word zzSub2 (word b[], const word a[], size_t n)
Уменьшение числа
word zzSubW (word b[], const word a[], size_t n, register word w)
Вычитание из числа слова
word zzSubW2 (word a[], size_t n, register word w)
Уменьшение числа на слова
void zzNeg (word b[], const word a[], size_t n)
Минус
word zzMulW (word b[], const word a[], size_t n, register word w)
Умножение числа на слово
word zzAddMulW (word b[], const word a[], size_t n, register word w)
Сложение с произведением числа на слово
word zzSubMulW (word b[], const word a[], size_t n, register word w)
Вычитание произведения числа на слово
void zzMul (word c[], const word a[], size_t n, const word b[], size_t m, void *stack)
Умножение чисел
void zzSqr (word b[], const word a[], size_t n, void *stack)
Возведение числа в квадрат
bool_t zzSqrt (word b[], const word a[], size_t n, void *stack)
Извлечение квадратного корня
word zzDivW (word q[], const word a[], size_t n, register word w)
Деление числа на машинное слово
word zzModW (const word a[], size_t n, register word w)
Остаток от деления числа на машинное слово
word zzModW2 (const word a[], size_t n, register word w)
Остаток от деления числа на малое машинное слово
void zzDiv (word q[], word r[], const word a[], size_t n, const word b[], size_t m, void *stack)
Деление чисел
void zzMod (word r[], const word a[], size_t n, const word b[], size_t m, void *stack)
Остаток от деления чисел
void zzGCD (word d[], const word a[], size_t n, const word b[], size_t m, void *stack)
Наибольший общий делитель
bool_t zzIsCoprime (const word a[], size_t n, const word b[], size_t m, void *stack)
Взаимная простота
void zzLCM (word d[], const word a[], size_t n, const word b[], size_t m, void *stack)
Наименьшее общее кратное
void zzExGCD (word d[], word da[], word db[], const word a[], size_t n, const word b[], size_t m, void *stack)
Расширенный алгоритм Евклида
int zzJacobi (const word a[], size_t n, const word b[], size_t m, void *stack)
Символ Якоби
void zzAddMod (word c[], const word a[], const word b[], const word mod[], size_t n)
Сложение чисел по модулю
void zzAddWMod (word b[], const word a[], register word w, const word mod[], size_t n)
Сложение числа со словом по модулю
void zzSubMod (word c[], const word a[], const word b[], const word mod[], size_t n)
Вычитание чисел по модулю
void zzSubWMod (word b[], const word a[], register word w, const word mod[], size_t n)
Вычитание из числа слова по модулю
void zzNegMod (word b[], const word a[], const word mod[], size_t n)
Аддитивное обращение чисел по модулю
void zzMulMod (word c[], const word a[], const word b[], const word mod[], size_t n, void *stack)
Умножение чисел по модулю
void zzSqrMod (word b[], const word a[], const word mod[], size_t n, void *stack)
Возведение чисел в квадрат по модулю
void zzInvMod (word b[], const word a[], const word mod[], size_t n, void *stack)
Обращение по модулю
void zzDivMod (word b[], const word divident[], const word a[], const word mod[], size_t n, void *stack)
Деление по модулю
void zzDoubleMod (word b[], const word a[], const word mod[], size_t n)
Удвоение числа по модулю
void zzHalfMod (word b[], const word a[], const word mod[], size_t n)
Половина числа по модулю
size_t zzAlmostInvMod (word b[], const word a[], const word mod[], size_t n, void *stack)
Почти-обращение по модулю
bool_t zzRandMod (word a[], const word mod[], size_t n, gen_i rng, void *rng_state)
Случайный вычет по модулю
bool_t zzRandNZMod (word a[], const word mod[], size_t n, gen_i rng, void *rng_state)
Случайный ненулевой вычет по модулю
void zzRed (word a[], const word mod[], size_t n, void *stack)
Стандартная редукция
void zzRedCrand (word a[], const word mod[], size_t n, void *stack)
Редукция Крэндалла
void zzRedBarrStart (word barr_param[], const word mod[], size_t n, void *stack)
Инициализация редукции Барретта
void zzRedBarr (word a[], const word mod[], size_t n, const word barr_param[], void *stack)
Редукция Барретта
void zzRedMont (word a[], const word mod[], size_t n, register word mont_param, void *stack)
Редукция Монтгомери
void zzRedCrandMont (word a[], const word mod[], size_t n, register word mont_param, void *stack)
Редукция Монтгомери по модулю Крэндалла
void zzPowerMod (word c[], const word a[], size_t n, const word b[], size_t m, const word mod[], void *stack)
Возведение в степень по модулю
word zzPowerModW (register word a, register word b, register word mod, void *stack)
Возведение в степень по модулю машинного слова

Подробное описание

Общие положения

Реализованы операции с большими неотрицательными целыми числами.

Число задается массивом машинных слов: word w[n]. Машинное слово w[0] -- младшее, машинное слово w[n - 1] -- старшее.

Пустое число (n = 0) считается нулевым.

В описаниях функций B = 2^{B_PER_W} --- основание системы счисления.

Функция zzDoubleMod() совместно с функциями zzAddMod() и zzSubMod() позволяет организовать быстрое модулярное умножение числа на малую константу. Например, вычисление b <- 7 a \mod mod может быть организовано следующим образом:

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

Аналогично, функция zzHalfMod() позволяет организовать быстрое модулярное деление на определенные константы.

Предусловие

Все входные указатели действительны.

В функциях работы с числами по адресам памяти для чисел зарезервировано ясное из конекста либо уточняемое в описаниях функций число машинных слов.

Вспомогательный буфер stack не пересекается с другими буферами.

Редукция

Редукция состоит в определении вычета числа [2n]a по модулю [n]mod. Обрабатываемое число всегда состоит из 2n машинных слов и результат всегда возвращается на месте а (ср. с zzMod()). Чтобы подчеркнуть данные соглашения вместо Mod (остаток от деления) пишется Red (редукция).

Кроме обычной редукции реализованы быстрые редукции по специальным модулям.

Функции

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

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

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

Предусловие

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

Возвращает

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

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

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

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

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

Предусловие

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

Возвращает

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

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

word zzAdd3 (word c[], const word a[], size_t n, const word b[], size_t 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.

Предусловие

a < mod && b < mod.

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

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

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

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

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

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.

Возвращает

Слово переноса 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 длина чисел в машинных словах

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.

Предусловие

a < mod.

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

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

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

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

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

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.

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

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

Аргументы: b частное
a делимое
mod модуль
n длина чисел в машинных словах

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.

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

zzInvMod_deep(n).

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

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

Аргументы: 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 является нечетным.

Возвращает

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

Аргументы: 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?

Прим.

Переставляя операнды, можно проверять не только суммы, но и разности.

Возвращает

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

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

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

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

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 второе слагаемое

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() и избежания разбора редких, неиспользуемых на практике случаев.

Схема расчета глубины 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 раза медленнее умножения.

Аргументы: 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 второй множитель

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 в машинных словах

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

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

b <- -a \mod mod.

Предусловие

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

a < mod.

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

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

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

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

Аргументы: b обратное число
a число
mod модуль
n длина чисел в машинных словах

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:

c <- a^b \mod mod.

Предусловие

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

a < mod.

Прим.

0^0 == 1.

Схема расчета глубины stack: zzPowerMod_deep(n, m).
Регулярность: todo
Аргументы: c степень
a основание
n длина a, mod в машинных словах
b показатель
m длина b в машинных словах
mod модуль
stack вспомогательная память

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

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

Предусловие: mod != 0.

Возвращает

Степень.

Схема расчета глубины stack: zzPowerModW_deep().
Регулярность: todo
Аргументы: a основание
b показатель
mod модуль
stack вспомогательная память

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}.

Предусловие

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

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

Возвращает

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

Прим.

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

Если rng выдает данные низкого статистического качества, то для генерации может потребоваться больше октетов, чем указано выше. Более того, как только количество потребовавшихся октетов превысит определенный порог d, будет возвращен отрицательный результат. Порог d выбирается так, что вероятность события 'для генерации потребуется d истинно случайных октетов' не превосходит 2^{-B_PER_IMPOSSIBLE}.

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

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

Аргументы: a случайное число
mod модуль
n длина a и mod в машинных словах
rng генератор случайных чисел
rng_state состояние генератора

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}.

Предусловие

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

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

Возвращает

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

Прим.

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

Повторяется последнее замечание по функции zzRandMod().

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

Аргументы: a случайное число
mod модуль
n длина a и mod в машинных словах
rng генератор случайных чисел
rng_state состояние генератора

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

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

Предусловие

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

Буферы a и mod не пересекаются.

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

zzRed_deep(n).

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

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

Аргументы: a делимое / остаток
mod модуль
n длина mod в машинных словах
stack вспомогательная память

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.

Предусловие

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

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

Ожидается

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

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

zzRedBarr_deep(n).

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

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

Аргументы: a делимое / остаток
mod модуль
n длина mod в машинных словах
barr_param параметр Барретта
stack вспомогательная память

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.

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

Предусловие

n > 0 && mod[n] != 0.

Буферы barr_param и mod не пересекаются.

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

zzRedBarrStart_deep(n).

Аргументы

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

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

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

Предусловие

n >= 2 && mod[n - 1] != 0.

Модуль mod имеет вид B^n - c, где 0 < c < B.

Буферы a и mod не пересекаются.

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

zzRedCrand_deep(n).

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

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

Аргументы: a делимое / остаток
mod модуль Крэндалла
n длина mod в машинных словах
stack вспомогательная память (не исп.)

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.

Предусловие

n >= 2 && mod -- нечетное && mod имеет вид B^n - c, где 0 < c < B.

a < mod * R.

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

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

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

zzRedCrandMont_deep(n).

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

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

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

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].

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

zzRedMont_deep(n).

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

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

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

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.

Возвращает

Слово заема 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 длина чисел в машинных словах

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 длина чисел в машинных словах

Автор

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

Info

Вт 23 Янв 2024 00:00:00 Библиотека Bee2