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 [in,out] слагаемое / сумма
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 [in,out] делимое / остаток
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.
- Аргументы
a [in,out] делимое / остаток
void ppRedPentanomial (word a[], const pp_pentanom_st * p)
Определяется остаток [W_OF_B(p->m)]a от деления многочлена [2 * W_OF_B(p->m)]a на пятичлен p.
- Предусловие
params->k > params->l > params->l1 > 0.
params->m - params->k >= B_PER_W.
params->k < B_PER_W.
- Аргументы
a [in,out] делимое / остаток
p описание пятичлена
void ppRedTrinomial (word a[], const pp_trinom_st * p)
Определяется остаток [W_OF_B(p->m)]a от деления многочлена [2 * W_OF_B(p->m)]a на трехчлен p.
- Предусловие
p->m % 8 != 0.
p->k > 0.
p->m - p->k >= B_PER_W.
- Аргументы
a [in,out] делимое / остаток
p описание трехчлена
void ppSqr (word b[], const word a[], size_t n, void * stack)
Определяется квадрат [2n]b многочлена [n]a:
b <- a * a.
Предусловие
Буфер b не пересекается с буфером a.
- Схема расчета глубины stack
ppSqr_deep(n, m).
- Аргументы
b квадрат
a множитель
n длина a в машинных словах
stack вспомогательная память
void ppSqrMod (word b[], const word a[], const word mod[], size_t n, void * stack)
Определяется квадрат [n]b многочлена [n]a по модулю [n]mod:
b <- a * a \mod mod.
- Предусловие
n > 0 && mod[n - 1] != 0.
\deg (a) < \deg (mod).
- Схема расчета глубины stack
ppSqrMod_deep(n).
- Аргументы
b квадрат
a множитель
mod модуль
n длина многочленов в машинных словах
stack вспомогательная память
Автор
Автоматически создано Doxygen для Библиотека Bee2 из исходного текста.