bee2-rs 0.2.3

/*
*******************************************************************************
\file qr.h
\brief Quotient rings
\project bee2 [cryptographic library]
\created 2013.08.09
\version 2015.09.01
\copyright The Bee2 authors
\license Licensed under the Apache License, Version 2.0 (see LICENSE.txt).
*******************************************************************************
*/

/*!
*******************************************************************************
\file qr.h
\brief Кольца вычетов
*******************************************************************************
*/

#ifndef __BEE2_QR_H
#define __BEE2_QR_H

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

#ifdef __cplusplus
extern "C" {
#endif


/*!
*******************************************************************************
\file qr.h

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

В интересующих нас случаях кольцо R является коммутативным, а идеал I -- 
главным, т.е. порожденным единственным элементом mod \in R:
	I = (mod) = {mod * a: a \in 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 описания кольца.

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

\pre Буферы элементов кольца или их кодовых представлений не пересекаются 
с буферами, поддерживающими описание кольца.

\warning В интерфейсах мультипликативных функций не предполагается, что буфер
результата либо не пересекается, либо совпадает с буферами входных элементов.

\safe todo
*******************************************************************************
*/

struct qr_o;

/*!	\brief Импорт элемента кольца вычетов

	По кодовому представлению [r->no]a строится элемент [r->n]b 
	кольца вычетов r.
	\pre Описание кольца r работоспособно.
	\pre Буферы a и b либо не пересекаются, либо указатели a и b совпадают.
	\expect Описание кольца r корректно.
	\return TRUE, если кодовое представление корректно и импорт успешно 
	выполнен, и FALSE в противном случае.
*/
typedef bool_t (*qr_from_i)(
	word b[],				/*!< [out] элемент кольца */
	const octet a[],		/*!< [in] кодовое представление элемента кольца */
	const struct qr_o* r,	/*!< [in] описание кольца */
	void* stack				/*!< [in] вспомогательная память */
);

/*!	\brief Экспорт элемента кольца вычетов

	Строится кодовое представление [r->no]b элемента [r->n]a кольца вычетов r.
	\pre Описание кольца r работоспособно.
	\pre Буферы a и b либо не пересекаются, либо указатели a и b совпадают.
	\expect Описание кольца r корректно.
*/
typedef void (*qr_to_i)(
	octet b[],				/*!< [out] кодовое представление элемента кольца */
	const word a[],			/*!< [in] элемент кольца */
	const struct qr_o* r,	/*!< [in] описание кольца */
	void* stack				/*!< [in] вспомогательная память */
);

/*!	\brief Сложение в кольце вычетов

	Определяется сумма [r->n]c элементов [r->n]a и [r->n]b кольца вычетов r:
	\code
		c <- a + b.
	\endcode
	\pre Описание кольца r работоспособно.
	\pre Буфер c либо не пересекается, либо совпадает с каждым из буферов a, b.
	\pre Элементы a и b принадлежат r.
	\expect Описание кольца r корректно.
*/
typedef void (*qr_add_i)(
	word c[],				/*!< [out] сумма */
	const word a[],			/*!< [in] первое слагаемое */
	const word b[],			/*!< [in] второе слагаемое */
	const struct qr_o* r	/*!< [in] описание кольца */
);

/*!	\brief Вычитание в кольце вычетов

	Определяется разность [r->n]c элементов [r->n]a и [r->n]b кольца вычетов r:
	\code
		c <- a - b.
	\endcode
	\pre Описание кольца r работоспособно.
	\pre Буфер c либо не пересекается, либо совпадает с каждым из буферов a, b.
	\pre Элементы a и b принадлежат r.
	\expect Описание кольца r корректно.
*/
typedef void (*qr_sub_i)(
	word c[],				/*!< [out] разность */
	const word a[],			/*!< [in] уменьшаемое */
	const word b[],			/*!< [in] вычитаемое */
	const struct qr_o* r	/*!< [in] описание кольца */
);

/*!	\brief Аддитивное обращение в кольце вычетов

	Определяется элемент [r->n]b кольца r, аддитивно обратный к [r->n]a:
	\code
		b <- -a.
	\endcode
	\pre Описание кольца r работоспособно.
	\pre Буфер b либо не пересекается, либо совпадает с буфером a.
	\pre Элемент a принадлежит r.
	\expect Описание кольца r корректно.
*/
typedef void (*qr_neg_i)(
	word b[],				/*!< [out] обратный элемент */
	const word a[],			/*!< [in] обращаемый элемент */
	const struct qr_o* r	/*!< [in] описание кольца */
);

/*!	\brief Умножение в кольце вычетов

	Определяется произведение [r->n]c элементов [r->n]a и [r->n]b 
	кольца вычетов r:
	\code
		с <- a * b.
	\endcode
	\pre Описание кольца r работоспособно.
	\pre Элементы a и b принадлежат r.
	\expect Описание кольца r корректно.
*/
typedef void (*qr_mul_i)(
	word c[],				/*!< [out] произведение */
	const word a[],			/*!< [in] первый множитель */
	const word b[],			/*!< [in] второй множитель */
	const struct qr_o* r,	/*!< [in] описание кольца */
	void* stack				/*!< [in] вспомогательная память */
);

/*!	\brief Возведение в квадрат в кольце вычетов

	Определяется квадрат [r->n]b элемента [r->n]a кольца r:
	\code
		с <- a * a.
	\endcode
	\pre Описание кольца r работоспособно.
	\pre Элемент a принадлежит r.
	\expect Описание кольца r корректно.
*/
typedef void (*qr_sqr_i)(
	word b[],				/*!< [out] квадрат */
	const word a[],			/*!< [in] множитель */
	const struct qr_o* r,	/*!< [in] описание кольца */
	void* stack				/*!< [in] вспомогательная память */
);

/*!	\brief Мультипликативное обращение в кольце вычетов

	Определяется элемент [r->n]b кольца r, мультипликативно обратный 
	к элементу [r->n]a:
	\code
		b <- a^{-1}.
	\endcode
	\pre Описание кольца r работоспособно.
	\pre Элемент a принадлежит r.
	\expect Описание кольца r корректно.
	\expect Элемент a обратим. Если a не обратим, то b может быть любым.
*/
typedef void (*qr_inv_i)(
	word b[],				/*!< [out] обратный элемент */
	const word a[],			/*!< [in] обращаемый элемент */
	const struct qr_o* r,	/*!< [in] описание кольца */
	void* stack				/*!< [in] вспомогательная память */
);

/*!	\brief Деление в кольце вычетов

	Определяется частное [r->n]b от деления элемента [r->n]divident 
	на элемент [r->n]a в кольце вычетов r:
	\code
		b <- divident * a^{-1}.
	\endcode
	\pre Описание кольца r работоспособно.
	\pre Элементы divident и a принадлежат r.
	\expect Описание кольца r корректно.
	\expect Элемент a обратим. Если a не обратим, то b может быть любым.
*/
typedef void (*qr_div_i)(
	word b[],				/*!< [out] частное */
	const word divident[],	/*!< [in] делимое */
	const word a[],			/*!< [in] делитель */
	const struct qr_o* r,	/*!< [in] описание кольца */
	void* stack				/*!< [in] вспомогательная память */
);

/*!	\brief Описание кольца вычетов

	Описывается кольцо вычетов, правила представления его элементов и функции, 
	реализующие операции в кольце.
	\remark В таблицу указателей описания кольца как объекта входят поля 
	mod, unity, params.
*/
typedef struct qr_o
{
	obj_hdr_t hdr;		/*!< заголовок */
// ptr_table {
	word* mod;			/*!< модуль */
	word* unity;		/*!< мультипликативная единица */
	void* params;		/*!< дополнительные параметры */
// }
	size_t n;			/*!< размерность */
	size_t no;			/*!< длина кодового представления */
	qr_from_i from;		/*!< функция импорта */
	qr_to_i to;			/*!< функция экспорта */
	qr_add_i add;		/*!< функция сложения */
	qr_sub_i sub;		/*!< функция вычитания */
	qr_neg_i neg;		/*!< функция аддитивного обращения */
	qr_mul_i mul;		/*!< функция умножения */
	qr_sqr_i sqr;		/*!< функция возведения в квадрат */
	qr_inv_i inv;		/*!< функция мультипликативного обращения */
	qr_div_i div;		/*!< функция деления */
	size_t deep;		/*!< максимальная глубина стека функций */
	octet descr[];		/*!< память для размещения данных */
} qr_o;

/*
*******************************************************************************
Псевдонимы
*******************************************************************************
*/

#define qrIsZero(a, r)\
	wwIsZero(a, (r)->n)

#define qrSetZero(a, r)\
	wwSetZero(a, (r)->n)

#define qrIsUnity(a, r)\
	wwEq(a, (r)->unity, (r)->n)

#define qrSetUnity(a, r)\
	wwCopy(a, (r)->unity, (r)->n)

#define qrCopy(b, a, r)\
	wwCopy(b, a, (r)->n)

#define qrCmp(b, a, r)\
	wwCmp(b, a, (r)->n)

#define qrFrom(b, a, r, stack)\
	(r)->from(b, a, r, stack)

#define qrTo(b, a, r, stack)\
	(r)->to(b, a, r, stack)

#define qrAdd(c, a, b, r)\
	(r)->add(c, a, b, r)

#define qrAddUnity(b, a, r)\
	(r)->add(b, a, (r)->unity, r)

#define qrSub(c, a, b, r)\
	(r)->sub(c, a, b, r)

#define qrSubUnity(a, r)\
	(r)->sub(a, a, (r)->unity, r)

#define qrNeg(b, a, r)\
	(r)->neg(b, a, r)

#define qrMul(c, a, b, r, stack)\
	(r)->mul(c, a, b, r, stack)

#define qrSqr(b, a, r, stack)\
	(r)->sqr(b, a, r, stack)

#define qrInv(b, a, r, stack)\
	(r)->inv(b, a, r, stack)

#define qrDiv(b, divident, a, r, stack)\
	(r)->div(b, divident, a, r, stack)

/*
*******************************************************************************
Управление описанием кольца
*******************************************************************************
*/

/*!	\brief Описание кольца вычетов работоспособно?

	Проверяется работоспособность описания r кольца вычетов. Проверяются 
	следующие условия:
	-	объект r работоспособен;
	-	objKeep(r) >= sizeof(qr_o);
	-	objPCount(r) == 3 && objOCount(r) == 0;
	-	указатель r->unity корректен;
	-	r->n > 0 && r->no > 0;
	-	указатели r->from, r->to, ..., r->div корректны.
	\return Признак работоспособности.
*/
bool_t qrIsOperable(
	const qr_o* r			/*!< [in] описание кольца */
);

/*
*******************************************************************************
Макрооперации в кольце
*******************************************************************************
*/

/*! \brief Возведение в степень в кольце вычетов

	В кольце вычетов r определяется элемент [r->n]c, который является [m]b-ой 
	степенью элемента [r->n]a:
	\code
		c <- a^b.
	\endcode
	\pre Описание кольца r работоспособно.
	\pre Элемент a принадлежит r.
	\expect Описание кольца r корректно.
	\remark При b == 0 возвращается r->unity.
	\deep{stack} qrPower_deep(r->n, m, r->deep).
*/
void qrPower(
	word c[],				/*!< [out] степень */
	const word a[],			/*!< [in] основание */
	const word b[],			/*!< [in] показатель */
	size_t m,				/*!< [in] длина b в машинных словах */
	const qr_o* r,			/*!< [in] описание кольца */
	void* stack				/*!< [in] вспомогательная память */
);

size_t qrPower_deep(size_t n, size_t m, size_t r_deep);

#ifdef __cplusplus
} /* extern "C" */
#endif

#endif /* __BEE2_QR_H */