zm.h - Man Page
Кольца вычетов целых чисел
Synopsis
#include 'bee2/math/qr.h'
Функции
void zmCreatePlain (qr_o *r, const octet mod[], size_t no, void *stack)
Создание описания кольца вычетов целых чисел с обычной редукцией
void zmCreateCrand (qr_o *r, const octet mod[], size_t no, void *stack)
Создание описания кольца вычетов целых чисел с редукцией Крэндалла
void zmCreateBarr (qr_o *r, const octet mod[], size_t no, void *stack)
Создание описания кольца вычетов целых чисел с редукцией Барретта
void zmCreateMont (qr_o *r, const octet mod[], size_t no, void *stack)
Создание описания кольца вычетов целых чисел с редукцией Монтгомери
void zmCreate (qr_o *r, const octet mod[], size_t no, void *stack)
Создание описания кольца вычетов целых чисел
void zmMontCreate (qr_o *r, const octet mod[], size_t no, size_t l, void *stack)
Создание описания кольца Монтгомери
bool_t zmIsValid (const qr_o *r)
Описание кольца вычетов целых чисел корректно?
Подробное описание
Реализованы операции в кольце вычетов Zm = Z / (mod), где mod -- произвольное натуральное число.
Элементы кольца кодируются строками из no октетов и задаются массивами из W_OF_O(no) машинных слов, где no -- длина mod в октетах. При кодировании используются порядок 'от младших к старшим'. Перечисленные соглашения можно учитывать при планировании работы с кольцом.
Для редукции по модулю mod используются функции, объявленные в zz.h:
- обычная редукция zzRed();
- редукция Крэндалла zzRedCrand();
- редукция Барретта zzRedBarr();
- редукция Монтгомери zzRedMont().
В кольце с редукцией Монтгомери вместо обычного умножения
c <- a * b \mod mod
используется специальное умножение
c <- a * b * R^{-1} \mod mod,где R -- минимальное число вида B^n, большее mod.
Мультипликативной единицей в кольце Монтгомери является число R \mod mod, мультипликативно обратный к a элемент: a^{-1} * R^2 \mod mod.
Число a из обычного кольца вычетов преобразуется в элемент a * R \mod mod кольца Монтгомери. После вычислений в кольце выходной элемент b преобразуется в число b * R^{-1} \mod mod.
Кольцо, которое создается с помощью функции zmMontCreate(), является 'чистым' кольцом Монтгомери. Элементы этого кольца представляются числами 'как есть'. Чистые кольца Монтгомери используются в алгоритмах СТБ 1176.2. В чистом кольце R = 2^l, причем l не обязательно кратно B_PER_W, т.е. R не обязательно имеет вид B^n.
Прим.
Функции zzCreateMont() и zzMontCreate() создают разные кольца.
Предусловие
Все указатели действительны.
- Регулярность
todo
Функции
void zmCreate (qr_o * r, const octet mod[], size_t no, void * stack)
По модулю [no]mod, представленному строкой октетов, создается описание r кольца Z / (mod). Подбирается оптимальное (с точки зрения эффективности вычислений) описание.
- Предусловие
no > 0 && mod[no - 1] > 0.
- Постусловие
r->no == no и r->n == W_OF_O(no).
Прим.
Оптимальное кольцо подбирается с учетом следующих результатов экспериментов (2013.09.17):
- редукция Крэндалла примерно в 2 раза быстрее редукции Монтгомери;
- редукция Монтгомери примерно в 2 раза быстрее редукции Барретта;
- редукция Барретта несколько опережает обычную редукцию при r->n >= 4.
- Схема расчета размера состояния r
zmCreate_keep(no).
- Схема расчета глубины stack
zmCreate_deep(no).
- Аргументы
r описание кольца
mod модуль
no длина mod в октетах
stack вспомогательная память
void zmCreateBarr (qr_o * r, const octet mod[], size_t no, void * stack)
По модулю [no]mod, представленному строкой октетов, создается описание r кольца Z / (mod). При вычислениях в кольце используется редукция Барретта.
- Предусловие
no > 0 && mod[no - 1] > 0.
- Постусловие
r->no == no и r->n == W_OF_O(no).
- Схема расчета размера состояния r
zmCreateBarr_keep(no).
- Схема расчета глубины stack
zmCreateBarr_deep(no).
- Аргументы
r описание кольца
mod модуль
no длина mod в октетах
stack вспомогательная память
void zmCreateCrand (qr_o * r, const octet mod[], size_t no, void * stack)
По модулю [no]mod, представленному строкой октетов, создается описание r кольца Z / (mod). При вычислениях в кольце используется редукция Крэндалла.
- Предусловие
no > 0 && mod[no - 1] > 0.
mod == B^n - c, где n >= 2 && 0 < c < B.
- Постусловие
r->no == no и r->n == W_OF_O(no).
- Схема расчета размера состояния r
zmCreateCrand_keep(no).
- Схема расчета глубины stack
zmCreateCrand_deep(no).
- Аргументы
r описание кольца
mod модуль
no длина mod в октетах
stack вспомогательная память
void zmCreateMont (qr_o * r, const octet mod[], size_t no, void * stack)
По модулю [no]mod, представленному строкой октетов, создается описание r кольца Z / (mod). При вычислениях в кольце используется редукция Монтгомери.
- Предусловие
no > 0 && mod[no - 1] > 0.
mod -- нечетное число.
- Постусловие
r->no == no и r->n == W_OF_O(no).
- Схема расчета размера состояния r
zmCreateMont_keep(no).
- Схема расчета глубины stack
zmCreateMont_deep(no).
- Аргументы
r описание кольца
mod модуль
no длина mod в октетах
stack вспомогательная память
void zmCreatePlain (qr_o * r, const octet mod[], size_t no, void * stack)
По модулю [no]mod, представленному строкой октетов, создается описание r кольца Z / (mod). При вычислениях в кольце используется обычная редукция.
- Предусловие
no > 0 && mod[no - 1] > 0.
- Постусловие
r->no == no и r->n == W_OF_O(no).
- Схема расчета размера состояния r
zmCreatePlain_keep(no).
- Схема расчета глубины stack
zmCreatePlain_deep(no).
- Аргументы
r описание кольца
mod модуль
no длина mod в октетах
stack вспомогательная память
bool_t zmIsValid (const qr_o * r)
Проверяется корректность описания r кольца Z / (mod). Проверяются следующие условия:
- qrIsOperable(r) == TRUE;
- указатель r->mod корректен;
- r->mod[r->n - 1] > 0.
Возвращает
Признак корректности.
Прим.
Работоспособность и корректность эквивалентны.
- Аргументы
r описание кольца
void zmMontCreate (qr_o * r, const octet mod[], size_t no, size_t l, void * stack)
По модулю [no]mod, представленному строкой октетов, создается описание r кольца Монтгомери c параметром R = 2^l.
- Предусловие
no > 0 && mod[no - 1] > 0.
mod -- нечетное число.
mod < R && B^n <= R (n -- число слов для размещения mod).
Прим.
Если кольцо построено, то r->no == no и r->n == W_OF_O(no).
- Схема расчета размера состояния r
zmMontCreate_keep(no).
- Схема расчета глубины stack
zmMontCreate_deep(no).
- Аргументы
r описание кольца
mod модуль
no длина mod в октетах
l показатель в параметре R
stack вспомогательная память
Автор
Автоматически создано Doxygen для Библиотека Bee2 из исходного текста.