pp.h - Man Page

Двоичные многочлены

Synopsis

#include 'bee2/defs.h'

Классы

struct pp_trinom_st
Описание трехчлена
struct pp_pentanom_st
Описание пятичлена

size_t ppDeg (const word a[], size_t n)
Степень многочлена
word ppMulW (word b[], const word a[], size_t n, register word w, void *stack)
Умножение многочлена на слово
word ppAddMulW (word b[], const word a[], size_t n, register word w, void *stack)
Сложение с произведением многочлена на слово
void ppMul (word c[], const word a[], size_t n, const word b[], size_t m, void *stack)
Умножение многочленов
void ppSqr (word b[], const word a[], size_t n, void *stack)
Возведение многочлена в квадрат
void ppDiv (word q[], word r[], const word a[], size_t n, const word b[], size_t m, void *stack)
Деление многочленов
void ppMod (word r[], const word a[], size_t n, const word b[], size_t m, void *stack)
Остаток от деления многочленов
void ppGCD (word d[], const word a[], size_t n, const word b[], size_t m, void *stack)
Наибольший общий делитель
void ppExGCD (word d[], word da[], word db[], const word a[], size_t n, const word b[], size_t m, void *stack)
Расширенный алгоритм Евклида
void ppMulMod (word c[], const word a[], const word b[], const word mod[], size_t n, void *stack)
Умножение многочленов по модулю
void ppSqrMod (word b[], const word a[], const word mod[], size_t n, void *stack)
Возведение многочлена в квадрат по модулю
void ppInvMod (word b[], const word a[], const word mod[], size_t n, void *stack)
Обращение по модулю
void ppDivMod (word b[], const word divident[], const word a[], const word mod[], size_t n, void *stack)
Деление по модулю
void ppRed (word a[], const word mod[], size_t n, void *stack)
Стандартная редукция
void ppRedTrinomial (word a[], const pp_trinom_st *p)
Редукция по модулю трехчлена
void ppRedPentanomial (word a[], const pp_pentanom_st *p)
Редукция по модулю пятичлена
void ppRedBelt (word a[])
Редукция по модулю многочлена Belt.
bool_t ppIsIrred (const word a[], size_t n, void *stack)
Проверка неприводимости
void ppMinPoly (word b[], const word a[], size_t l, void *stack)
Минимальный многочлен последовательности
void ppMinPolyMod (word b[], const word a[], const word mod[], size_t n, void *stack)
Минимальный многочлен по модулю многочлена

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

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

Многочлен 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, через который передается вспомогательная память, необходимая для размещения локальных переменных.

Предусловие

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

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

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

Модулярная арифметика

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

Редукция

Редукция состоит в определении вычета многочлена [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 слов, старшее из которых будет нулевым.

Функции

word ppAddMulW (word b[], const word a[], size_t n, register word w, void * stack)

К многочлену [n]b добавляется произведение многочлена [n]a на слово w:

b + X^n * carry <- b + a * w.

Предусловие

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

Возвращает

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

Схема расчета глубины stack: ppAddMulW_deep(n).
Аргументы: b слагаемое / сумма
a первый множитель
n длина a в машинных словах
w второй множитель
stack вспомогательная память

size_t ppDeg (const word a[], size_t n)

Определяется степень многочлена [n]a.

Прим.

Степенью является позиция старшего ненулевого бита a (нумерация от 0). Степень нулевого многочлена полагается равной SIZE_MAX.

Возвращает

Степень a.

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

void ppDiv (word q[], word r[], const word a[], size_t n, const word b[], size_t m, void * stack)

Определяется частное [n - m + 1]q и остаток [n]r от деления многочлена [n]a на многочлен [m]b:

q <- a \div b, r <- a \mod b,
a = q * b + r, deg(r) < deg(b).

Предусловие

n >= m.

m > 0 && b[m - 1] != 0.

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

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

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

ppDiv_deep(n, m).

Аргументы

q частное
r остаток
a делимое
n длина a в машинных словах
b делитель
m длина b в машинных словах
stack вспомогательная память

void ppDivMod (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.

Предусловие

n > 0 && mod[n - 1] != 0 && mod имеет свободный член.

a, divident < mod.

Ожидается

\gcd(a, mod) == 1.

Прим.

Если \gcd(a, mod) != 1, то b <- 0.

Схема расчета глубины stack: ppDivMod_deep(n).
Аргументы: b частное
divident делимое
a делитель
mod модуль
n длина чисел в машинных словах
stack вспомогательная память

void ppExGCD (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 такие, что

a * da + b * db == d

(коэффициенты Безу).

Предусловие

a != 0 && b != 0.

Буферы d, da, db не пересекаются между собой и с буферами a, b.

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

ppExGCD_deep(n, m).

Аргументы

d н.о.д.
da первый коэффициент Безу
db второй коэффициент Безу
a первый многочлен
n длина a в машинных словах
b второй многочлен
m длина b в машинных словах
stack вспомогательная память

void ppGCD (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)] слов.

Схема расчета глубины stack: ppGCD_deep(n, m).
Аргументы: d н.о.д.
a первый многочлен
n длина a в машинных словах
b второй многочлен
m длина b в машинных словах
stack вспомогательная память

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

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

b <- a^{-1} \mod mod.

Предусловие

n > 0 && mod[n - 1] != 0 && mod -- нечетное.

a < mod.

Ожидается

\gcd(a, mod) == 1.

Прим.

Если \gcd(a, mod) != 1, то b <- 0.

Схема расчета глубины stack: ppInvMod_deep(n).
Аргументы: b обратный многочлен
a обращаемый многочлен
mod модуль
n длина многочленов в машинных словах
stack вспомогательная память

bool_t ppIsIrred (const word a[], size_t n, void * stack)

Проверяется, что многочлен [n]a является неприводимым.

Возвращает: TRUE, если a неприводим, и FALSE в противном случае.
Схема расчета глубины stack: ppIsIrred_deep(n).
Аргументы: a многочлен
n длина a в машинных словах
stack вспомогательная память

void ppMinPoly (word b[], const word a[], size_t l, void * stack)

Определяется минимальный многочлен [W_OF_B(l + 1)]b последовательности из 2 * l битов слова [W_OF_B(2 * l)]a. Первым элементом последовательности является бит с номером 2 * l - 1, вторым элементом -- бит с номером 2 * l - 2,.., последним -- бит с номером 0.

Прим.

Минимальный многочлен нулевой последовательности: 1.

Минимальный многочлен последовательности из 1: x + 1.

Схема расчета глубины stack: ppMinPoly_deep(l).
Аргументы: b минимальный многочлен
a последовательность
l половина длины последовательности в битах
stack вспомогательная память

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

Определяется минимальный многочлен [n]b многочлена [n]a как элемента факторкольца F_2[x]/([n]mod(x)).

Предусловие

\deg(mod) > 1 && \deg(a) < \deg(mod).

Прим.

Если \deg(mod) кратно B_PER_W, то a умещается в n - 1 машинное слово. Тем не менее, все равно используется дополнительное нулевое старшее слово.

Теория изложена в [Shoup V. A Computational Introduction to Number Theory and Algebra, http://www.shoup.net/ntb/, 2008] (версия 2, глава 18).

Если mod --- неприводим и a != 0, то b будет неприводимым. Этот факт можно использовать для построения одного неприводимого многочлена по другому.

Схема расчета глубины stack: deep(ppMinPolyMod, n).
Аргументы: b минимальный многочлен
a многочлен факторкольца
mod модуль
n длина многочленов в машинных словах
stack вспомогательная память

void ppMod (word r[], const word a[], size_t n, const word b[], size_t m, void * stack)

Определяется остаток [m]r от деления многочлена [n]a на многочлен [m]b:

r <- a \mod b.

Предусловие

m > 0 && b[m - 1] != 0.

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

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

ppMod_deep(n, m).

Аргументы

r остаток
a делимое
n длина a в машинных словах
b делитель
m длина b в машинных словах
stack вспомогательная память

void ppMul (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: ppMul_deep(n, m).
Аргументы: c произведение
a первый множитель
n длина a в машинных словах
b второй множитель
m длина b в машинных словах
stack вспомогательная память

void ppMulMod (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.

\deg(a) < \deg(mod) && \deg(b) < \deg(mod).

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

ppMulMod_deep(n).

Аргументы

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

word ppMulW (word b[], const word a[], size_t n, register word w, void * stack)

Многочлен [n]a умножается на многочлен-слово w:

a + X^n * carry <- a * w.

Предусловие

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

Возвращает

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

Схема расчета глубины stack: ppMulW_deep(n).
Аргументы: b произведение
a первый множитель
n длина a, b в машинных словах
w второй множитель
stack вспомогательная память

void ppRed (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

ppRed_deep(n).

Аргументы

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

void ppRedBelt (word a[])

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