1gf2.h(3) Library Functions Manual gf2.h(3)
2
3
4
6 gf2.h - Двоичные поля
7
8
10 #include 'bee2/math/qr.h'
11
12
13 Функции
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
33 Элементы кольца кодируются строками из O_OF_B(m) октетов и задаются
34 массивами из W_OF_B(m) машинных слов. При кодировании используются
35 порядок 'от младших к старшим'. Перечисленные соглашения можно
36 учитывать при планировании работы в поле.
37
38 Многочлен 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
42 При p[2] == 0 должно выполняться также p[3] == 0 и p(x) -- трехчлен.
43
44 При p[1] == 0 должно выполняться также p[2] == p[3] == 0 и поле f
45 описывается нормальным базисом (на будущее).
46
47 Для трехчленов и пятичленов p(x) должны выполняться ограничения,
48 заданные в функциях ppRedTrinomial(), ppRedPentanomial().
49
50 Поле создается с помощью функции gf2Create(). При создании поля
51 анализируется p(x) и в зависимости от его вида выбирается одна из общих
52 функций редукции ppRedTrinomial() или ppRedPentanomial().
53
54 Массив 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
60 Некоторые неприводимые многочлены из криптографических стандартов:
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
65 Предусловие
66 Все указатели, передаваемые в функции, действительны.
67
68 Регулярность
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
77 Ожидается
78 p(x) -- неприводим.
79
80 Возвращает
81 Признак успеха.
82
83 Постусловие
84 Cтепень расширения m совпадает с p[0].
85
86 f->n == W_OF_B(m) и f->no == O_OF_B(m).
87
88 Схема расчета размера состояния f
89 gf2Create_keep(m).
90
91 Схема расчета глубины stack
92 gf2Create_deep(m).
93
94 Аргументы
95 f описание поля
96 p описание p(x)
97 stack вспомогательная память
98
99 size_t gf2Deg (const qr_o * f)
100 Определяется степень расширения m поля f = GF(2^m).
101
102 Предусловие
103 Описание f работоспособно.
104
105 Возвращает
106 Степень расширения.
107
108 Аргументы
109 f описание поля
110
111 bool_t gf2IsOperable (const qr_o * f)
112 Проверяется работоспособность описания f поля GF(2^m). Проверяются
113 следующие условия:
114
115 • qrIsOperable(f) == TRUE;
116
117 • указатель f->mod корректен;
118
119 • указатель f->params корректен;
120
121 • f->params указывает на массив [4]p;
122
123 • p[0] > p[1] >= p[2] >= p[3] >= 0;
124
125 • p[2] > 0 => предыдущие неравенства строгие (для пятичленов);
126
127 • последнее слово f->mod ненулевое;
128
129 • f->n == W_OF_B(m) (m == p[0]);
130
131 • f->no == O_OF_B(m).
132
133 Возвращает
134 Признак работоспособности.
135
136 Прим.
137 Не проверяется согласованность f->mod и [4]p, а также
138 неприводимость f->mod.
139
140 Аргументы
141 f описание поля
142
143 bool_t gf2IsValid (const qr_o * f, void * stack)
144 Проверяется корректность описания f поля GF(2^m). Проверяются следующие
145 условия:
146
147 • gf2IsOperable(f) == TRUE;
148
149 • если p[1] > 0, то f->mod и массив [4]p описывают одинаковые
150 многочлены;
151
152 • если p[1] > 0, то многочлен f->mod неприводим.
153
154 Здесь [4]p -- это массив по адресу f->params.
155
156 Возвращает
157 Признак корректности.
158
159 Схема расчета глубины stack
160 gf2IsValid_deep(f->n).
161
162 Аргументы
163 f описание поля
164 stack вспомогательная память
165
166 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
171 x^2 + a x + b == 0.
172
173
174 Предусловие
175 Описание f работоспособно.
176
177 m -- нечетное.
178
179 Буфер x не пересекается с буферами a, b.
180
181 Элементы a и b принадлежат f.
182
183 Ожидается
184 Описание f корректно.
185
186 Возвращает
187 TRUE, если решение есть, и FALSE в противном случае.
188
189 Прим.
190 Если x -- решение, то и x + a -- решение.
191
192 Схема расчета глубины stack
193 gf2QSolve_deep(f->n, f->deep).
194
195 Аргументы
196 x решение
197 a коэффициент a
198 b коэффициент b
199 f описание поля
200 stack вспомогательная память
201
202 bool_t gf2Tr (const word a[], const qr_o * f, void * stack)
203 В поле f = GF(2^m) определяется абсолютный след элемента [f->n]a:
204
205 \tr(a) <- \sum {i = 0}^{m - 1} a^{2^i}.
206
207
208 След совпадает либо с нулем, либо с единицей поля.
209
210 Предусловие
211 Описание f работоспособно.
212
213 Элемент a принадлежит f.
214
215 Ожидается
216 Описание f корректно.
217
218 Возвращает
219 FALSE, если след равняется 0, и TRUE, если след равняется 1.
220
221 Схема расчета глубины stack
222 gf2Tr_deep(f->n, f->deep).
223
224 Аргументы
225 a элемент
226 f описание поля
227 stack вспомогательная память
228
230 Автоматически создано Doxygen для Библиотека Bee2 из исходного текста.
231
232
233
234Библиотека Bee2 Ср 19 Июл 2023 00:00:00 gf2.h(3)