1gf2.h(3) Library Functions Manual gf2.h(3)
2
6 gf2.h - Двоичные поля
7
10 #include 'bee2/math/qr.h'
11 Функции
14 bool_t gf2Create (qr_o *f, const size_t p[4], void *stack)
15 Создание описания поля GF(2^m)
16 bool_t gf2IsOperable (const qr_o *f)
17 Описание поля GF(2^m) работоспособно?
18 bool_t gf2IsValid (const qr_o *f, void *stack)
19 Описание поля GF(2^m) корректно?
20 size_t gf2Deg (const qr_o *f)
21 Степень расширения поля GF(2^m)
22 bool_t gf2Tr (const word a[], const qr_o *f, void *stack)
23 След элемента поля GF(2^m)
24 bool_t gf2QSolve (word x[], const word a[], const word b[], const qr_o
25 *f, void *stack)
26 Решение квадратного уравнения в поле GF(2^m)
27
29 Реализованы операции в поле GF(2^m). Элементы поля интерпретируются как
30 элементы кольца вычетов GF(2) / (p(x)), где p(x) --- неприводимый
31 многочлен степени m. Реализована поддержка трехчленов и пятичленов.
32 Элементы кольца кодируются строками из O_OF_B(m) октетов и задаются
34 массивами из W_OF_B(m) машинных слов. При кодировании используются
35 порядок 'от младших к старшим'. Перечисленные соглашения можно
36 учитывать при планировании работы в поле.
37 Многочлен p(x) задается массивом size_t p[4]: p(x) = x^p[0] + x^p[1] +
39 x^p[2] + x^p[3] + 1. В частности, m == p[0] --- степень расширения
40 поля.
41 При p[2] == 0 должно выполняться также p[3] == 0 и p(x) -- трехчлен.
43 При p[1] == 0 должно выполняться также p[2] == p[3] == 0 и поле f
45 описывается нормальным базисом (на будущее).
46 Для трехчленов и пятичленов p(x) должны выполняться ограничения,
48 заданные в функциях ppRedTrinomial(), ppRedPentanomial().
49 Поле создается с помощью функции gf2Create(). При создании поля
51 анализируется p(x) и в зависимости от его вида выбирается одна из общих
52 функций редукции ppRedTrinomial() или ppRedPentanomial().
53 Массив p, описывающий p(x), при создании поля фиксируется
55 по адресу params (см. описание типа qr_o). При создании поля также
56 формируется модуль mod. Модуль представляется либо n машинными словами
57 (степень p(x) кратна B_PER_W), либо n + 1 словом (степень p(x) не
58 кратна B_PER_W).
59 Некоторые неприводимые многочлены из криптографических стандартов:
61 Belt, GCM: x^128 + x^7 + x^2 + x + 1, NIST163: x^163 + x^7 + x^6 + x^3
62 + 1, NIST233: x^233 + x^74 + 1, NIST283: x^283 + x^12 + x^7 + x^5 + 1,
63 NIST409: x^409 + x^87 + 1, NIST571: x^571 + x^10 + x^5 + x^2 + 1.
64 Предусловие
66 Все указатели, передаваемые в функции, действительны.
67 Регулярность
69 todo
70
72 bool_t gf2Create (qr_o * f, const size_t p[4], void * stack)
73 По описанию p многочлена p(x) создается описание f поля GF(2^m) =
74 GF(2)/(p(x)). Подбирается оптимальное (с точки зрения эффективности
75 вычислений) описание поля.
76 Ожидается
78 p(x) -- неприводим.
79 Возвращает
81 Признак успеха.
82 Постусловие
84 Cтепень расширения m совпадает с p[0].
85 f->n == W_OF_B(m) и f->no == O_OF_B(m).
87 Схема расчета размера состояния f
89 gf2Create_keep(m).
90 Схема расчета глубины stack
92 gf2Create_deep(m).
93 Аргументы
95 f описание поля
96 p описание p(x)
97 stack вспомогательная память
98 size_t gf2Deg (const qr_o * f)
100 Определяется степень расширения m поля f = GF(2^m).
101 Предусловие
103 Описание f работоспособно.
104 Возвращает
106 Степень расширения.
107 Аргументы
109 f описание поля
110 bool_t gf2IsOperable (const qr_o * f)
112 Проверяется работоспособность описания f поля GF(2^m). Проверяются
113 следующие условия:
114 • qrIsOperable(f) == TRUE;
116 • указатель f->mod корректен;
118 • указатель f->params корректен;
120 • f->params указывает на массив [4]p;
122 • p[0] > p[1] >= p[2] >= p[3] >= 0;
124 • p[2] > 0 => предыдущие неравенства строгие (для пятичленов);
126 • последнее слово f->mod ненулевое;
128 • f->n == W_OF_B(m) (m == p[0]);
130 • f->no == O_OF_B(m).
132 Возвращает
134 Признак работоспособности.
135 Прим.
137 Не проверяется согласованность f->mod и [4]p, а также
138 неприводимость f->mod.
139 Аргументы
141 f описание поля
142 bool_t gf2IsValid (const qr_o * f, void * stack)
144 Проверяется корректность описания f поля GF(2^m). Проверяются следующие
145 условия:
146 • gf2IsOperable(f) == TRUE;
148 • если p[1] > 0, то f->mod и массив [4]p описывают одинаковые
150 многочлены;
151 • если p[1] > 0, то многочлен f->mod неприводим.
153 Здесь [4]p -- это массив по адресу f->params.
155 Возвращает
157 Признак корректности.
158 Схема расчета глубины stack
160 gf2IsValid_deep(f->n).
161 Аргументы
163 f описание поля
164 stack вспомогательная память
165 bool_t gf2QSolve (word x[], const word a[], const word b[], const qr_o * f,
167 void * stack)
168 В поле f = GF(2^m) для заданных элементов [f->n]a, [f->n]b определяется
169 решение [n]x квадратного уравнения
170 x^2 + a x + b == 0.
172 Предусловие
175 Описание f работоспособно.
176 m -- нечетное.
178 Буфер x не пересекается с буферами a, b.
180 Элементы a и b принадлежат f.
182 Ожидается
184 Описание f корректно.
185 Возвращает
187 TRUE, если решение есть, и FALSE в противном случае.
188 Прим.
190 Если x -- решение, то и x + a -- решение.
191 Схема расчета глубины stack
193 gf2QSolve_deep(f->n, f->deep).
194 Аргументы
196 x решение
197 a коэффициент a
198 b коэффициент b
199 f описание поля
200 stack вспомогательная память
201 bool_t gf2Tr (const word a[], const qr_o * f, void * stack)
203 В поле f = GF(2^m) определяется абсолютный след элемента [f->n]a:
204 \tr(a) <- \sum {i = 0}^{m - 1} a^{2^i}.
206 След совпадает либо с нулем, либо с единицей поля.
209 Предусловие
211 Описание f работоспособно.
212 Элемент a принадлежит f.
214 Ожидается
216 Описание f корректно.
217 Возвращает
219 FALSE, если след равняется 0, и TRUE, если след равняется 1.
220 Схема расчета глубины stack
222 gf2Tr_deep(f->n, f->deep).
223 Аргументы
225 a элемент
226 f описание поля
227 stack вспомогательная память
228
230 Автоматически создано Doxygen для Библиотека Bee2 из исходного текста.
231Библиотека Bee2 Пт 23 Июн 2023 gf2.h(3)