bee2-rs 0.2.3

/*
*******************************************************************************
\file pp.h
\brief Binary polynomials
\project bee2 [cryptographic library]
\created 2012.03.01
\version 2023.02.02
\copyright The Bee2 authors
\license Licensed under the Apache License, Version 2.0 (see LICENSE.txt).
*******************************************************************************
*/

/*!
*******************************************************************************
\file pp.h
\brief Двоичные многочлены
*******************************************************************************
*/

#ifndef __BEE2_PP_H
#define __BEE2_PP_H

#include "bee2/defs.h"

#ifdef __cplusplus
extern "C" {
#endif

/*!
*******************************************************************************
\file pp.h

Реализованы операции с многочленами над двоичным полем.

Многочлен p(x) задается массивом машинных слов: word p[n].
Свободный член хранится в младшем бите p[0], коэффициент при старшем
мономе -- в старшем бите p[n - 1].

В описаниях функций X = x^{B_PER_W}. В частности,
	p(x) = p[n - 1]X^{n - 1} + ... + p[1] X + p[0].

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

Для манипуляций с массивом машинных слов могут использоваться функции,
объявленные в файле ww.h. Например, сложение многочленов реализуется
функцией wwXor().

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

\pre Все указатели, передаваемые в функции, действительны.

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

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

/*
*******************************************************************************
Степень
*******************************************************************************
*/

/*! \brief Степень многочлена

	Определяется степень многочлена [n]a.
	\remark Степенью является позиция старшего ненулевого бита a
	(нумерация от 0). Степень нулевого многочлена полагается равной SIZE_MAX.
	\return Степень a.
*/
size_t ppDeg(
	const word a[],	/*!< [in] многочлен */
	size_t n		/*!< [in] длина многочлена в словах */
);

/*
*******************************************************************************
Мультипликативные операции
*******************************************************************************
*/

/*! \brief Умножение многочлена на слово

	Многочлен [n]a умножается на многочлен-слово w:
	\code
		a + X^n * carry <- a * w.
	\endcode
	\pre Буфер b либо не пересекается, либо совпадает с буфером a.
	\return Слово переноса carry.
	\deep{stack} ppMulW_deep(n).
*/
word ppMulW(
	word b[],			/*!< [out] произведение */
	const word a[],		/*!< [in] первый множитель */
	size_t n,			/*!< [in] длина a, b в машинных словах */
	register word w,	/*!< [in] второй множитель */
	void* stack			/*!< [in] вспомогательная память */
);

size_t ppMulW_deep(size_t n);

/*! \brief Сложение с произведением многочлена на слово

	К многочлену [n]b добавляется произведение многочлена [n]a на слово w:
	\code
		b + X^n * carry <- b + a * w.
	\endcode
	\pre Буфер b либо не пересекается, либо совпадает с буфером a.
	\return Слово переноса carry.
	\deep{stack} ppAddMulW_deep(n).
*/
word ppAddMulW(
	word b[],			/*!< [in,out] слагаемое / сумма */
	const word a[],		/*!< [in] первый множитель */
	size_t n,			/*!< [in] длина a в машинных словах */
	register word w,	/*!< [in] второй множитель */
	void* stack			/*!< [in] вспомогательная память */
);

size_t ppAddMulW_deep(size_t n);

/*! \brief Умножение многочленов

	Определяется произведение [n + m]c многочлена [n]a на многочлен [m]b:
	\code
		c <- a * b.
	\endcode
	\pre Буфер c не пересекается с буферами a и b.
	\deep{stack} ppMul_deep(n, m).
*/
void ppMul(
	word c[],		/*!< [out] произведение */
	const word a[],	/*!< [in] первый множитель */
	size_t n,		/*!< [in] длина a в машинных словах */
	const word b[],	/*!< [in] второй множитель */
	size_t m,		/*!< [in] длина b в машинных словах */
	void* stack		/*!< [in] вспомогательная память */
);

size_t ppMul_deep(size_t n, size_t m);

/*! \brief Возведение многочлена в квадрат

	Определяется квадрат [2n]b многочлена [n]a:
	\code
		b <- a * a.
	\endcode
	\pre Буфер b не пересекается с буфером a.
	\deep{stack} ppSqr_deep(n, m).
*/
void ppSqr(
	word b[],		/*!< [out] квадрат */
	const word a[],	/*!< [in] множитель */
	size_t n,		/*!< [in] длина a в машинных словах */
	void* stack		/*!< [in] вспомогательная память */
);

size_t ppSqr_deep(size_t n);

/*! \brief Деление многочленов

	Определяется частное [n - m + 1]q и остаток [n]r от деления многочлена
	[n]a на многочлен [m]b:
	\code
		q <- a \div b, r <- a \mod b,
		a = q * b + r, deg(r) < deg(b).
	\endcode
	\pre n >= m.
	\pre m > 0 && b[m - 1] != 0.
	\pre Буфер r либо не пересекается с буфером a, либо r == a.
	\pre Буферы q и r не пересекаются.
	\deep{stack} ppDiv_deep(n, m).
*/
void ppDiv(
	word q[],		/*!< [out] частное */
	word r[],		/*!< [out] остаток */
	const word a[],	/*!< [in] делимое */
	size_t n,		/*!< [in] длина a в машинных словах */
	const word b[],	/*!< [in] делитель */
	size_t m,		/*!< [in] длина b в машинных словах */
	void* stack		/*!< [in] вспомогательная память */
);

size_t ppDiv_deep(size_t n, size_t m);

/*! \brief Остаток от деления многочленов

	Определяется остаток [m]r от деления многочлена [n]a на многочлен [m]b:
	\code
		r <- a \mod b.
	\endcode
	\pre m > 0 && b[m - 1] != 0.
	\pre Буфер r либо не пересекается с буфером a, либо r == a.
	\deep{stack} ppMod_deep(n, m).
*/
void ppMod(
	word r[],		/*!< [out] остаток */
	const word a[],	/*!< [in] делимое */
	size_t n,		/*!< [in] длина a в машинных словах */
	const word b[],	/*!< [in] делитель */
	size_t m,		/*!< [in] длина b в машинных словах */
	void* stack		/*!< [in] вспомогательная память */
);

size_t ppMod_deep(size_t n, size_t m);

/*
*******************************************************************************
Алгоритм Евклида
*******************************************************************************
*/

/*! \brief Наибольший общий делитель

	Определяется наибольший общий делитель [min(n, m)]d многочленов
	[n]a и [m]b:
	\code
		d <- \gcd(a, b).
	\endcode
	\pre a != 0 && b != 0.
	\pre Буфер d не пересекается с буферами a и b.
	\remark Использование нулевых a и b запрещается для того, чтобы
	наибольший общий делитель d укладывался в [min(n, m)] слов.
	\deep{stack} ppGCD_deep(n, m).
*/
void ppGCD(
	word d[],		/*!< [out] н.о.д. */
	const word a[],	/*!< [in] первый многочлен */
	size_t n,		/*!< [in] длина a в машинных словах */
	const word b[],	/*!< [in] второй многочлен */
	size_t m,		/*!< [in] длина b в машинных словах */
	void* stack		/*!< [in] вспомогательная память */
);

size_t ppGCD_deep(size_t n, size_t m);

/*! \brief Расширенный алгоритм Евклида

	Определяется наибольший общий делитель [min(n, m)]d многочленов
	[n]a и [m]b:
	\code
		d <- \gcd(a, b),
	\endcode
	а также многочлены [m]da и [n]db такие, что
	\code
		a * da + b * db == d
	\endcode
	(коэффициенты Безу).
	\pre a != 0 && b != 0.
	\pre Буферы d, da, db не пересекаются между собой и с буферами a, b.
	\deep{stack} ppExGCD_deep(n, m).
*/
void ppExGCD(
	word d[],		/*!< [out] н.о.д. */
	word da[],		/*!< [out] первый коэффициент Безу */
	word db[],		/*!< [out] второй коэффициент Безу */
	const word a[],	/*!< [in] первый многочлен */
	size_t n,		/*!< [in] длина a в машинных словах */
	const word b[],	/*!< [in] второй многочлен */
	size_t m,		/*!< [in] длина b в машинных словах */
	void* stack		/*!< [in] вспомогательная память */
);

size_t ppExGCD_deep(size_t n, size_t m);

/*!
*******************************************************************************
\file pp.h

\section pp-mod Модулярная арифметика

Если степень deg(mod) модуля [n]mod кратна B_OF_W, т.е. mod[n - 1] == 1,
то остаток r умещается в m - 1 слов. Тем не менее, остаток все равно
определяется как [n]r, т.е. задается n словами, старшее из которых является
нулевым.
*******************************************************************************
*/

/*! \brief Умножение многочленов по модулю

	Определяется произведение [n]c многочленов [n]a и [n]b по модулю [n]mod:
	\code
		c <- a * b \mod mod.
	\endcode
	\pre n > 0 && mod[n - 1] != 0.
	\pre \deg(a) < \deg(mod) && \deg(b) < \deg(mod).
	\deep{stack} ppMulMod_deep(n).
*/
void ppMulMod(
	word c[],			/*!< [out] произведение */
	const word a[],		/*!< [in] первый множитель */
	const word b[],		/*!< [in] второй множитель */
	const word mod[],	/*!< [in] модуль */
	size_t n,			/*!< [in] длина многочленов в машинных словах */
	void* stack			/*!< [in] вспомогательная память */
);

size_t ppMulMod_deep(size_t n);

/*! \brief Возведение многочлена в квадрат по модулю

	Определяется квадрат [n]b многочлена [n]a по модулю [n]mod:
	\code
		b <- a * a \mod mod.
	\endcode
	\pre n > 0 && mod[n - 1] != 0.
	\pre \deg(a) < \deg(mod).
	\deep{stack} ppSqrMod_deep(n).
*/
void ppSqrMod(
	word b[],			/*!< [out] квадрат */
	const word a[],		/*!< [in] множитель */
	const word mod[],	/*!< [in] модуль */
	size_t n,			/*!< [in] длина многочленов в машинных словах */
	void* stack			/*!< [in] вспомогательная память */
);

size_t ppSqrMod_deep(size_t n);

/*! \brief Обращение по модулю

	Определяется многочлен [n]b, мультипликативно обратный к [n]a по модулю [n]mod:
	\code
		b <- a^{-1} \mod mod.
	\endcode
	\pre n > 0 && mod[n - 1] != 0 && mod -- нечетное.
	\pre a < mod.
	\expect \gcd(a, mod) == 1. 
	\remark Если \gcd(a, mod) != 1, то b <- 0.
	\deep{stack} ppInvMod_deep(n).
*/
void ppInvMod(
	word b[],			/*!< [out] обратный многочлен */
	const word a[],		/*!< [in] обращаемый многочлен */
	const word mod[],	/*!< [in] модуль */
	size_t n,			/*!< [in] длина многочленов в машинных словах */
	void* stack			/*!< [in] вспомогательная память */
);

size_t ppInvMod_deep(size_t n);

/*! \brief Деление по модулю

	Определяется частное [n]b от деления многочлена [n]divident на многочлен
	[n]a по модулю [n]mod:
	\code
		b <- divident * a^{-1} \mod mod.
	\endcode
	\pre n > 0 && mod[n - 1] != 0 && mod имеет свободный член.
	\pre a, divident < mod.
	\expect \gcd(a, mod) == 1.
	\remark Если \gcd(a, mod) != 1, то b <- 0.
	\deep{stack} ppDivMod_deep(n).
*/
void ppDivMod(
	word b[],				/*!< [out] частное */
	const word divident[],	/*!< [in] делимое */
	const word a[],			/*!< [in] делитель */
	const word mod[],		/*!< [in] модуль */
	size_t n,				/*!< [in] длина чисел в машинных словах */
	void* stack				/*!< [in] вспомогательная память */
);

size_t ppDivMod_deep(size_t n);

/*!
*******************************************************************************
\file pp.h

\section pp-red Редукция

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

Кроме обычной редукции реализованы быстрые редукции по специальным модулям.
Специальный модуль может задаваться не словом [n]mod, а определенными
параметрами.

Неприводимые трехчлены и пятичлены степени m используются для описания
поля GF(2^m). Редукция по модулю специальных трехчленов и пятичленов
реализована в функциях ppRedTrinomial() и ppRedPentanomial().

Трехчлен p(x) = x^m + x^k + 1 задается числами m > k > 0. Согласно общим
рекомендациям по ускорению приведения mod p(x)
[см. напр. www.secg.org/sec2-v2.pdf] при заданном m выбрается минимальное k,
при котором p(x) оказывается неприводимым. Поэтому при больших m выполняется
ограничение m - k >= B_PER_W, которое используется для ускорения приведения
в функции ppRedTrinomial().

Теорема Свана [Swan R. G. Factorization of Polynomials over Finite Fields,
Pacific J. Math 12, 1962, 1099–1106] означает, что степень неприводимого
трехчлена не может делиться на 8. Данный факт дает дополнительное
ограничение на m.

Пятичлен p(x) = x^m + x^k + x^l + x^l1 + 1 задается числами
m > k > l > l1 > 0. Согласно общим рекомендациям по ускорению приведения
\mod p(x) [см. напр. www.secg.org/sec2-v2.pdf] при заданном m выбирается
минимальное k, при котором p(x) оказывается неприводимым.
Затем при заданных m, k выбирается минимальное l, при котором p(x)
оказывается неприводимым и т.д. Поэтому при больших m выполняются
ограничения k < B_PER_W и m - k >= B_PER_W, которые используются для
ускорения приведения в функции ppRedPentanomial().

В функциях ppRedTrinomial(), ppRedPentanomial() результат является
многочленом из W_OF_B(m) слов, где m -- степень модуля. Например, если
m % B_PER_W == 0, то результат укладывается в m / B_PER_W слов. Для
сравнения, функция ppRed() в той же ситуации возвратит результат из
m / B_PER_W + 1 слов, старшее из которых будет нулевым.
*******************************************************************************
*/

/*! \brief Описание трехчлена */
typedef struct 
{
	size_t m;		/*!< степень трехчлена */
	size_t k;		/*!< степень среднего монома */
} pp_trinom_st;

/*! \brief Описание пятичлена */
typedef struct 
{
	size_t m;		/*!< степень пятичлена */
	size_t k;		/*!< степень старшего из средних мономов */
	size_t l;		/*!< степень среднего из средних мономов */
	size_t l1;		/*!< степень младшего из средних мономов */
} pp_pentanom_st;

/*! \brief Стандартная редукция

	Определяется остаток [n]a от деления многочлена [2n]a на модуль [n]mod.
	\pre n >= 1 && mod[n - 1] != 0.
	\pre Буферы a и mod не пересекаются.
	\deep{stack} ppRed_deep(n).
*/
void ppRed(
	word a[],					/*!< [in,out] делимое / остаток */
	const word mod[],			/*!< [in] модуль */
	size_t n,					/*!< [in] длина mod в машинных словах */
	void* stack					/*!< [in] вспомогательная память */
);

size_t ppRed_deep(size_t n);

/*! \brief Редукция по модулю трехчлена

	Определяется остаток  [W_OF_B(p->m)]a от деления многочлена 
	[2 * W_OF_B(p->m)]a на трехчлен p.
	\pre p->m % 8 != 0.
	\pre p->k > 0.
	\pre p->m - p->k >= B_PER_W.
*/
void ppRedTrinomial(
	word a[],					/*!< [in,out] делимое / остаток */
	const pp_trinom_st* p		/*!< [in] описание трехчлена */
);

/*! \brief Редукция по модулю пятичлена

	Определяется остаток [W_OF_B(p->m)]a от деления многочлена 
	[2 * W_OF_B(p->m)]a на пятичлен p.
	\pre params->k > params->l > params->l1 > 0.
	\pre params->m - params->k >= B_PER_W.
	\pre params->k < B_PER_W.
*/
void ppRedPentanomial(
	word a[],					/*!< [in,out] делимое / остаток */
	const pp_pentanom_st* p		/*!< [in] описание пятичлена */
);

/*! \brief Редукция по модулю многочлена Belt

	Определяется остаток  [W_OF_B(128)]a от деления многочлена [W_OF_B(256)]a 
	на многочлен
		x^128 + x^7 + x^2 + x + 1,
	который используется в стандартах Belt и GCM.
*/
void ppRedBelt(
	word a[]					/*!< [in,out] делимое / остаток */
);

/*
*******************************************************************************
Неприводимость
*******************************************************************************
*/

/*! \brief Проверка неприводимости

	Проверяется, что многочлен [n]a является неприводимым.
	\return TRUE, если a неприводим, и FALSE в противном случае.
	\deep{stack} ppIsIrred_deep(n).
*/
bool_t ppIsIrred(
	const word a[],		/*!< [in] многочлен */
	size_t n,			/*!< [in] длина a в машинных словах */
	void* stack			/*!< [in] вспомогательная память */
);

size_t ppIsIrred_deep(size_t n);

/*
*******************************************************************************
Минимальный многочлен
*******************************************************************************
*/

/*! \brief Минимальный многочлен последовательности

	Определяется минимальный многочлен [W_OF_B(l + 1)]b последовательности 
	из 2 * l битов слова [W_OF_B(2 * l)]a. Первым элементом 
	последовательности является бит с номером 2 * l - 1, вторым элементом -- 
	бит с номером 2 * l - 2,.., последним -- бит с номером 0.
	\remark Минимальный многочлен нулевой последовательности: 1.
	\remark Минимальный многочлен последовательности из 1: x + 1.
	\deep{stack} ppMinPoly_deep(l).
*/
void ppMinPoly(
	word b[],			/*!< [out] минимальный многочлен */
	const word a[],		/*!< [in] последовательность */
	size_t l,			/*!< [in] половина длины последовательности в битах */
	void* stack			/*!< [in] вспомогательная память */
);

size_t ppMinPoly_deep(size_t l);

/*! \brief Минимальный многочлен по модулю многочлена

	Определяется минимальный многочлен [n]b многочлена [n]a как элемента 
	факторкольца F_2[x]/([n]mod(x)). 
	\pre \deg(mod) > 1 && \deg(a) < \deg(mod).
	\remark Если \deg(mod) кратно B_PER_W, то a умещается в n - 1 
	машинное слово. Тем не менее, все равно используется дополнительное
	нулевое старшее слово.
	\remark Теория изложена в [Shoup V. A Computational Introduction 
	to Number Theory and Algebra, http://www.shoup.net/ntb/, 2008] 
	(версия 2, глава 18).
	\remark Если mod --- неприводим и a != 0, то b будет неприводимым.
	Этот факт можно использовать для построения одного неприводимого 
	многочлена по другому.
	\deep{stack} deep(ppMinPolyMod, n).
*/
void ppMinPolyMod(
	word b[],			/*!< [out] минимальный многочлен */
	const word a[],		/*!< [in] многочлен факторкольца */
	const word mod[],	/*!< [in] модуль */
	size_t n,			/*!< [in] длина многочленов в машинных словах */
	void* stack			/*!< [in] вспомогательная память */
);

size_t ppMinPolyMod_deep(size_t n);

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

#endif /* __BEE2_PP_H */