1pp.h(3) Library Functions Manual pp.h(3)
2
6 pp.h - Двоичные многочлены
7
10 #include 'bee2/defs.h'
11 Классы
14 struct pp_trinom_st
15 Описание трехчлена
16 struct pp_pentanom_st
17 Описание пятичлена
18 Функции
20 size_t ppDeg (const word a[], size_t n)
21 Степень многочлена
22 word ppMulW (word b[], const word a[], size_t n, register word w, void
23 *stack)
24 Умножение многочлена на слово
25 word ppAddMulW (word b[], const word a[], size_t n, register word w,
26 void *stack)
27 Сложение с произведением многочлена на слово
28 void ppMul (word c[], const word a[], size_t n, const word b[], size_t
29 m, void *stack)
30 Умножение многочленов
31 void ppSqr (word b[], const word a[], size_t n, void *stack)
32 Возведение многочлена в квадрат
33 void ppDiv (word q[], word r[], const word a[], size_t n, const word
34 b[], size_t m, void *stack)
35 Деление многочленов
36 void ppMod (word r[], const word a[], size_t n, const word b[], size_t
37 m, void *stack)
38 Остаток от деления многочленов
39 void ppGCD (word d[], const word a[], size_t n, const word b[], size_t
40 m, void *stack)
41 Наибольший общий делитель
42 void ppExGCD (word d[], word da[], word db[], const word a[], size_t n,
43 const word b[], size_t m, void *stack)
44 Расширенный алгоритм Евклида
45 void ppMulMod (word c[], const word a[], const word b[], const word
46 mod[], size_t n, void *stack)
47 Умножение многочленов по модулю
48 void ppSqrMod (word b[], const word a[], const word mod[], size_t n,
49 void *stack)
50 Возведение многочлена в квадрат по модулю
51 void ppInvMod (word b[], const word a[], const word mod[], size_t n,
52 void *stack)
53 Обращение по модулю
54 void ppDivMod (word b[], const word divident[], const word a[], const
55 word mod[], size_t n, void *stack)
56 Деление по модулю
57 void ppRed (word a[], const word mod[], size_t n, void *stack)
58 Стандартная редукция
59 void ppRedTrinomial (word a[], const pp_trinom_st *p)
60 Редукция по модулю трехчлена
61 void ppRedPentanomial (word a[], const pp_pentanom_st *p)
62 Редукция по модулю пятичлена
63 void ppRedBelt (word a[])
64 Редукция по модулю многочлена Belt.
65 bool_t ppIsIrred (const word a[], size_t n, void *stack)
66 Проверка неприводимости
67 void ppMinPoly (word b[], const word a[], size_t l, void *stack)
68 Минимальный многочлен последовательности
69 void ppMinPolyMod (word b[], const word a[], const word mod[], size_t
70 n, void *stack)
71 Минимальный многочлен по модулю многочлена
72
74 Реализованы операции с многочленами над двоичным полем.
75 Многочлен p(x) задается массивом машинных слов: word p[n]. Свободный
77 член хранится в младшем бите p[0], коэффициент при старшем мономе -- в
78 старшем бите p[n - 1].
79 В описаниях функций X = x^{B_PER_W}. В частности, p(x) = p[n - 1]X^{n -
81 1} + ... + p[1] X + p[0].
82 Пустой многочлен (n = 0) считается нулевым.
84 Для манипуляций с массивом машинных слов могут использоваться функции,
86 объявленные в файле ww.h. Например, сложение многочленов реализуется
87 функцией wwXor().
88 В некоторых функциях используется вспомогательный буфер stack, через
90 который передается вспомогательная память, необходимая для размещения
91 локальных переменных.
92 Предусловие
94 Все указатели, передаваемые в функции, действительны.
95 Вспомогательный буфер stack не пересекается с другими буферами.
97 Регулярность
99 todo
100
102 Если степень deg(mod) модуля [n]mod кратна B_OF_W, т.е. mod[n - 1] ==
103 1, то остаток r умещается в m - 1 слов. Тем не менее, остаток все равно
104 определяется как [n]r, т.е. задается n словами, старшее из которых
105 является нулевым.
106
108 Редукция состоит в определении вычета многочлена [2n]a по модулю
109 [n]mod. Обрабатываемый многочлен всегда состоит из 2n машинных слов и
110 результат всегда возвращается на месте а (ср. с zzMod()). Чтобы
111 подчеркнуть данные соглашения вместо Mod (остаток от деления) пишется
112 Red (редукция).
113 Кроме обычной редукции реализованы быстрые редукции по специальным
115 модулям. Специальный модуль может задаваться не словом [n]mod, а
116 определенными параметрами.
117 Неприводимые трехчлены и пятичлены степени m используются для описания
119 поля GF(2^m). Редукция по модулю специальных трехчленов и пятичленов
120 реализована в функциях ppRedTrinomial() и ppRedPentanomial().
121 Трехчлен p(x) = x^m + x^k + 1 задается числами m > k > 0. Согласно
123 общим рекомендациям по ускорению приведения mod p(x) [см. напр.
124 www.secg.org/sec2-v2.pdf] при заданном m выбрается минимальное k, при
125 котором p(x) оказывается неприводимым. Поэтому при больших m
126 выполняется ограничение m - k >= B_PER_W, которое используется для
127 ускорения приведения в функции ppRedTrinomial().
128 Теорема Свана [Swan R. G. Factorization of Polynomials over Finite
130 Fields, Pacific J. Math 12, 1962, 1099–1106] означает, что степень
131 неприводимого трехчлена не может делиться на 8. Данный факт дает
132 дополнительное ограничение на m.
133 Пятичлен p(x) = x^m + x^k + x^l + x^l1 + 1 задается числами m > k > l >
135 l1 > 0. Согласно общим рекомендациям по ускорению приведения \mod p(x)
136 [см. напр. www.secg.org/sec2-v2.pdf] при заданном m выбирается
137 минимальное k, при котором p(x) оказывается неприводимым. Затем при
138 заданных m, k выбирается минимальное l, при котором p(x) оказывается
139 неприводимым и т.д. Поэтому при больших m выполняются ограничения k <
140 B_PER_W и m - k >= B_PER_W, которые используются для ускорения
141 приведения в функции ppRedPentanomial().
142 В функциях ppRedTrinomial(), ppRedPentanomial() результат является
144 многочленом из W_OF_B(m) слов, где m -- степень модуля. Например, если
145 m % B_PER_W == 0, то результат укладывается в m / B_PER_W слов. Для
146 сравнения, функция ppRed() в той же ситуации возвратит результат из m /
147 B_PER_W + 1 слов, старшее из которых будет нулевым.
148
150 word ppAddMulW (word b[], const word a[], size_t n, register word w, void *
151 stack)
152 К многочлену [n]b добавляется произведение многочлена [n]a на слово w:
153 b + X^n * carry <- b + a * w.
155 Предусловие
158 Буфер b либо не пересекается, либо совпадает с буфером a.
159 Возвращает
161 Слово переноса carry.
162 Схема расчета глубины stack
164 ppAddMulW_deep(n).
165 Аргументы
167 b слагаемое / сумма
168 a первый множитель
169 n длина a в машинных словах
170 w второй множитель
171 stack вспомогательная память
172 size_t ppDeg (const word a[], size_t n)
174 Определяется степень многочлена [n]a.
175 Прим.
177 Степенью является позиция старшего ненулевого бита a (нумерация от
178 0). Степень нулевого многочлена полагается равной SIZE_MAX.
179 Возвращает
181 Степень a.
182 Аргументы
184 a многочлен
185 n длина многочлена в словах
186 void ppDiv (word q[], word r[], const word a[], size_t n, const word b[],
188 size_t m, void * stack)
189 Определяется частное [n - m + 1]q и остаток [n]r от деления многочлена
190 [n]a на многочлен [m]b:
191 q <- a \div b, r <- a \mod b,
193 a = q * b + r, deg(r) < deg(b).
194 Предусловие
197 n >= m.
198 m > 0 && b[m - 1] != 0.
200 Буфер r либо не пересекается с буфером a, либо r == a.
202 Буферы q и r не пересекаются.
204 Схема расчета глубины stack
206 ppDiv_deep(n, m).
207 Аргументы
209 q частное
210 r остаток
211 a делимое
212 n длина a в машинных словах
213 b делитель
214 m длина b в машинных словах
215 stack вспомогательная память
216 void ppDivMod (word b[], const word divident[], const word a[], const word
218 mod[], size_t n, void * stack)
219 Определяется частное [n]b от деления многочлена [n]divident на
220 многочлен [n]a по модулю [n]mod:
221 b <- divident * a^{-1} \mod mod.
223 Предусловие
226 n > 0 && mod[n - 1] != 0 && mod имеет свободный член.
227 a, divident < mod.
229 Ожидается
231 \gcd(a, mod) == 1.
232 Прим.
234 Если \gcd(a, mod) != 1, то b <- 0.
235 Схема расчета глубины stack
237 ppDivMod_deep(n).
238 Аргументы
240 b частное
241 divident делимое
242 a делитель
243 mod модуль
244 n длина чисел в машинных словах
245 stack вспомогательная память
246 void ppExGCD (word d[], word da[], word db[], const word a[], size_t n,
248 const word b[], size_t m, void * stack)
249 Определяется наибольший общий делитель [min(n, m)]d многочленов [n]a и
250 [m]b:
251 d <- \gcd(a, b),
253 а также многочлены [m]da и [n]db такие, что
256 a * da + b * db == d
258 (коэффициенты Безу).
261 Предусловие
263 a != 0 && b != 0.
264 Буферы d, da, db не пересекаются между собой и с буферами a, b.
266 Схема расчета глубины stack
268 ppExGCD_deep(n, m).
269 Аргументы
271 d н.о.д.
272 da первый коэффициент Безу
273 db второй коэффициент Безу
274 a первый многочлен
275 n длина a в машинных словах
276 b второй многочлен
277 m длина b в машинных словах
278 stack вспомогательная память
279 void ppGCD (word d[], const word a[], size_t n, const word b[], size_t m,
281 void * stack)
282 Определяется наибольший общий делитель [min(n, m)]d многочленов [n]a и
283 [m]b:
284 d <- \gcd(a, b).
286 Предусловие
289 a != 0 && b != 0.
290 Буфер d не пересекается с буферами a и b.
292 Прим.
294 Использование нулевых a и b запрещается для того, чтобы наибольший
295 общий делитель d укладывался в [min(n, m)] слов.
296 Схема расчета глубины stack
298 ppGCD_deep(n, m).
299 Аргументы
301 d н.о.д.
302 a первый многочлен
303 n длина a в машинных словах
304 b второй многочлен
305 m длина b в машинных словах
306 stack вспомогательная память
307 void ppInvMod (word b[], const word a[], const word mod[], size_t n, void *
309 stack)
310 Определяется многочлен [n]b, мультипликативно обратный к [n]a по модулю
311 [n]mod:
312 b <- a^{-1} \mod mod.
314 Предусловие
317 n > 0 && mod[n - 1] != 0 && mod -- нечетное.
318 a < mod.
320 Ожидается
322 \gcd(a, mod) == 1.
323 Прим.
325 Если \gcd(a, mod) != 1, то b <- 0.
326 Схема расчета глубины stack
328 ppInvMod_deep(n).
329 Аргументы
331 b обратный многочлен
332 a обращаемый многочлен
333 mod модуль
334 n длина многочленов в машинных словах
335 stack вспомогательная память
336 bool_t ppIsIrred (const word a[], size_t n, void * stack)
338 Проверяется, что многочлен [n]a является неприводимым.
339 Возвращает
341 TRUE, если a неприводим, и FALSE в противном случае.
342 Схема расчета глубины stack
344 ppIsIrred_deep(n).
345 Аргументы
347 a многочлен
348 n длина a в машинных словах
349 stack вспомогательная память
350 void ppMinPoly (word b[], const word a[], size_t l, void * stack)
352 Определяется минимальный многочлен [W_OF_B(l + 1)]b последовательности
353 из 2 * l битов слова [W_OF_B(2 * l)]a. Первым элементом
354 последовательности является бит с номером 2 * l - 1, вторым элементом
355 -- бит с номером 2 * l - 2,.., последним -- бит с номером 0.
356 Прим.
358 Минимальный многочлен нулевой последовательности: 1.
359 Минимальный многочлен последовательности из 1: x + 1.
361 Схема расчета глубины stack
363 ppMinPoly_deep(l).
364 Аргументы
366 b минимальный многочлен
367 a последовательность
368 l половина длины последовательности в битах
369 stack вспомогательная память
370 void ppMinPolyMod (word b[], const word a[], const word mod[], size_t n,
372 void * stack)
373 Определяется минимальный многочлен [n]b многочлена [n]a как элемента
374 факторкольца F_2[x]/([n]mod(x)).
375 Предусловие
377 \deg(mod) > 1 && \deg(a) < \deg(mod).
378 Прим.
380 Если \deg(mod) кратно B_PER_W, то a умещается в n - 1 машинное
381 слово. Тем не менее, все равно используется дополнительное нулевое
382 старшее слово.
383 Теория изложена в [Shoup V. A Computational Introduction to Number
385 Theory and Algebra, http://www.shoup.net/ntb/, 2008] (версия 2,
386 глава 18).
387 Если mod --- неприводим и a != 0, то b будет неприводимым. Этот
389 факт можно использовать для построения одного неприводимого
390 многочлена по другому.
391 Схема расчета глубины stack
393 deep(ppMinPolyMod, n).
394 Аргументы
396 b минимальный многочлен
397 a многочлен факторкольца
398 mod модуль
399 n длина многочленов в машинных словах
400 stack вспомогательная память
401 void ppMod (word r[], const word a[], size_t n, const word b[], size_t m,
403 void * stack)
404 Определяется остаток [m]r от деления многочлена [n]a на многочлен [m]b:
405 r <- a \mod b.
407 Предусловие
410 m > 0 && b[m - 1] != 0.
411 Буфер r либо не пересекается с буфером a, либо r == a.
413 Схема расчета глубины stack
415 ppMod_deep(n, m).
416 Аргументы
418 r остаток
419 a делимое
420 n длина a в машинных словах
421 b делитель
422 m длина b в машинных словах
423 stack вспомогательная память
424 void ppMul (word c[], const word a[], size_t n, const word b[], size_t m,
426 void * stack)
427 Определяется произведение [n + m]c многочлена [n]a на многочлен [m]b:
428 c <- a * b.
430 Предусловие
433 Буфер c не пересекается с буферами a и b.
434 Схема расчета глубины stack
436 ppMul_deep(n, m).
437 Аргументы
439 c произведение
440 a первый множитель
441 n длина a в машинных словах
442 b второй множитель
443 m длина b в машинных словах
444 stack вспомогательная память
445 void ppMulMod (word c[], const word a[], const word b[], const word mod[],
447 size_t n, void * stack)
448 Определяется произведение [n]c многочленов [n]a и [n]b по модулю
449 [n]mod:
450 c <- a * b \mod mod.
452 Предусловие
455 n > 0 && mod[n - 1] != 0.
456 \deg(a) < \deg(mod) && \deg(b) < \deg(mod).
458 Схема расчета глубины stack
460 ppMulMod_deep(n).
461 Аргументы
463 c произведение
464 a первый множитель
465 b второй множитель
466 mod модуль
467 n длина многочленов в машинных словах
468 stack вспомогательная память
469 word ppMulW (word b[], const word a[], size_t n, register word w, void *
471 stack)
472 Многочлен [n]a умножается на многочлен-слово w:
473 a + X^n * carry <- a * w.
475 Предусловие
478 Буфер b либо не пересекается, либо совпадает с буфером a.
479 Возвращает
481 Слово переноса carry.
482 Схема расчета глубины stack
484 ppMulW_deep(n).
485 Аргументы
487 b произведение
488 a первый множитель
489 n длина a, b в машинных словах
490 w второй множитель
491 stack вспомогательная память
492 void ppRed (word a[], const word mod[], size_t n, void * stack)
494 Определяется остаток [n]a от деления многочлена [2n]a на модуль [n]mod.
495 Предусловие
497 n >= 1 && mod[n - 1] != 0.
498 Буферы a и mod не пересекаются.
500 Схема расчета глубины stack
502 ppRed_deep(n).
503 Аргументы
505 a делимое / остаток
506 mod модуль
507 n длина mod в машинных словах
508 stack вспомогательная память
509 void ppRedBelt (word a[])
511 Определяется остаток [W_OF_B(128)]a от деления многочлена
512 [W_OF_B(256)]a на многочлен x^128 + x^7 + x^2 + x + 1, который
513 используется в стандартах Belt и GCM.
514 Аргументы
516 a делимое / остаток
517 void ppRedPentanomial (word a[], const pp_pentanom_st * p)
519 Определяется остаток [W_OF_B(p->m)]a от деления многочлена [2 *
520 W_OF_B(p->m)]a на пятичлен p.
521 Предусловие
523 params->k > params->l > params->l1 > 0.
524 params->m - params->k >= B_PER_W.
526 params->k < B_PER_W.
528 Аргументы
530 a делимое / остаток
531 p описание пятичлена
532 void ppRedTrinomial (word a[], const pp_trinom_st * p)
534 Определяется остаток [W_OF_B(p->m)]a от деления многочлена [2 *
535 W_OF_B(p->m)]a на трехчлен p.
536 Предусловие
538 p->m % 8 != 0.
539 p->k > 0.
541 p->m - p->k >= B_PER_W.
543 Аргументы
545 a делимое / остаток
546 p описание трехчлена
547 void ppSqr (word b[], const word a[], size_t n, void * stack)
549 Определяется квадрат [2n]b многочлена [n]a:
550 b <- a * a.
552 Предусловие
555 Буфер b не пересекается с буфером a.
556 Схема расчета глубины stack
558 ppSqr_deep(n, m).
559 Аргументы
561 b квадрат
562 a множитель
563 n длина a в машинных словах
564 stack вспомогательная память
565 void ppSqrMod (word b[], const word a[], const word mod[], size_t n, void *
567 stack)
568 Определяется квадрат [n]b многочлена [n]a по модулю [n]mod:
569 b <- a * a \mod mod.
571 Предусловие
574 n > 0 && mod[n - 1] != 0.
575 \deg(a) < \deg(mod).
577 Схема расчета глубины stack
579 ppSqrMod_deep(n).
580 Аргументы
582 b квадрат
583 a множитель
584 mod модуль
585 n длина многочленов в машинных словах
586 stack вспомогательная память
587
589 Автоматически создано Doxygen для Библиотека Bee2 из исходного текста.
590Библиотека Bee2 Пт 23 Июн 2023 pp.h(3)