qr.h - Man Page

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

Пусть R -- кольцо, I -- его идеал. Кольцом вычетов называется кольцо R / I, в котором сложение и умножение элементов выполняется по модулю I: (a + I) + (b + I) = (a + b) + I, (a + I) * (b + I) = (a * b) + I.

В интересующих нас случаях кольцо R является коммутативным, а идеал I -- главным, т.е. порожденным единственным элементом mod ∈ R: I = (mod) = {mod * a: a ∈ R}. В этих случаях приведение по модулю I состоит в редукции (определении вычета) по модулю mod.

Кольцо вычетов описывается структурой типа qr_o.

Структура qr_o проектировалась с прицелом на поддержку следующих колец:

• R = Z, mod = n --- произвольное натуральное [кольцо вычетов целых чисел ZZ_n];
• R = Z, mod = p -- простое число [простое поле GF(p)];
• R = GF(2)[x], mod = f(x) --- неприводимый многочлен степени e [поле GF(2^e)].

В этих кольцах может применяться умножение Монтгомери, умножение в нормальном базисе и другие ускоренные мультипликативные операции. Особенные операции требуют особенного описания кольца и особенного представления его элементов. В связи с этим вводится структура qr_o, которая задает:

• описание кольца вычетов;
• описание элементов кольца;
• интерфейсы арифметических операций в кольце.

Идеал I описывается модулем mod. Для ускорения редукции по модулю mod могут использоваться параметры params. Параметры params могут рассчитываться по mod при создании кольца, могут дублировать mod, или заменять его. Параметры params имеют самостоятельное значение и могут использоваться не только для редукции.

Элемент кольца представляется массивом из n машинных слов. Размерность n определяется при построении кольца и сохраняется в его описании.

Нулевому элементу всегда соответствует нулевой массив.

Мультипликативные единицы могут отличаться. Мультипликативная единица unity инициализируется при построении кольца.

Размерность модуля mod жестко не регламентируется. Эта размерность определяется в функциях работы с элементами кольца по params и (или) n. В кольцах чисел mod задается n словами. Если mod = 2^{B_PER_W * (n - 1)}, то последнее слово mod равняется 1, а последние слова элементов поля всегда равняются 0. В кольцах многочленов mod задается n или n + 1 словом (в зависимости от выполнения равенства deg(mod) == B_PER_W * n).

Элементы кольца экспортируются в строки октетов и импортируются из этих строк. Длина строки no определяется при построении кольца и сохраняется в его описании. Для экспорта / импорта элементов кольца используются функции типов qr_to_i, qr_from_i. Способ определения длины строки указывается при описании колец конкретных типов. Нулевому элементу обязательно соответствует нулевая строка.

Аддитивные операции в кольце, как правило, не меняются при различных его описаниях. Тем не менее, в структуру qr_o включены функции интерфейсов qr_add_i, qr_sub_i и qr_neg_i, которые определяют аддитивные операции.

Мультипликативные операции в кольце задаются интерфейсами qr_mul_i и qr_sqr_i.

Некоторые элементы кольца допускают мультипликативное обращение и, следовательно, определенные пары элементов можно делить друг на друга. Обращение и деление поддерживается интерфейсами qr_inv_i, qr_div_i.

Описание кольца организовано как объект, и можно применять функции, описанные в заголовочном файле obj.h.

Кольцо должно создаваться специальной функцией qrCreate(), которая является аналогом конструктора. В эту функцию должен передаваться указатель r на структуру типа qr_o. По этому указателю будет размещаться описание (состояние) кольца. По адресу r может быть зарезервировано больше памяти, чем sizeof(qr_o). Дело в том, что значения mod, unity, params могут размещаться в поле descr открытого размера. Функция qrCreate() должна сопровождаться функцией qrCreate_keep(), которая поддерживает расчет длины состояния (в октетах).

Функция qrCreate_keep() должна оценивать длину состояния сверху. Оценка может быть неточной. Точная длина состояния фиксируется при непосредственном выполнении qrCreate() и сохраняется в поле keep описания кольца.

В функцию qrCreate() должен передаваться указатель на память для стека. Функция qrCreate() должна сопровождаться функцией qrCreate_deep(), которая выполняет расчет глубины стека. При расчете глубины следует предполагать, что в qrCreate() явно или неявно вызываются все функции кольца. Получив результат работы qrCreate_deep(), внешние программы могут определить, сколько вспомогательной памяти потребуется при всевозможных способах работы с кольцом.

В описании qrCreate() должны быть даны оценки сверху для размерностей n и no. Эти оценки могут использоваться высокоуровневыми функциями при подготовке памяти для размещения элементов кольца.

Оценка глубины стека, определяемая функцией qrCreate_deep(), может быть неточной. Точная глубина фиксируется при непосредственном выполнении qrCreate() и сохраняется в поле deep описания кольца.

Предусловие

Предупреждения

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

todo

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