1zz.h(3) Library Functions Manual zz.h(3)
2
6 zz.h - Большие неотрицательные целые числа
7
10 #include 'bee2/defs.h'
11 #include 'bee2/core/safe.h'
12 Функции
15 bool_t zzIsEven (const word a[], size_t n)
16 Четное число?
17 bool_t zzIsOdd (const word a[], size_t n)
18 Нечетное число?
19 word zzAdd (word c[], const word a[], const word b[], size_t n)
20 Сложение чисел
21 word zzAdd2 (word b[], const word a[], size_t n)
22 Добавление числа
23 word zzAdd3 (word c[], const word a[], size_t n, const word b[], size_t
24 m)
25 Сложение чисел проивольной длины
26 word zzAddW (word b[], const word a[], size_t n, register word w)
27 Сложение числа со словом
28 word zzAddW2 (word a[], size_t n, register word w)
29 Добавление слова
30 bool_t zzIsSumEq (const word c[], const word a[], const word b[],
31 size_t n)
32 Сумма чисел равняется числу?
33 bool_t zzIsSumWEq (const word b[], const word a[], size_t n, register
34 word w)
35 Сумма числа и слова равняется числу?
36 word zzSub (word c[], const word a[], const word b[], size_t n)
37 Вычитание чисел
38 word zzSub2 (word b[], const word a[], size_t n)
39 Уменьшение числа
40 word zzSubW (word b[], const word a[], size_t n, register word w)
41 Вычитание из числа слова
42 word zzSubW2 (word a[], size_t n, register word w)
43 Уменьшение числа на слова
44 void zzNeg (word b[], const word a[], size_t n)
45 Минус
46 word zzMulW (word b[], const word a[], size_t n, register word w)
47 Умножение числа на слово
48 word zzAddMulW (word b[], const word a[], size_t n, register word w)
49 Сложение с произведением числа на слово
50 word zzSubMulW (word b[], const word a[], size_t n, register word w)
51 Вычитание произведения числа на слово
52 void zzMul (word c[], const word a[], size_t n, const word b[], size_t
53 m, void *stack)
54 Умножение чисел
55 void zzSqr (word b[], const word a[], size_t n, void *stack)
56 Возведение числа в квадрат
57 bool_t zzSqrt (word b[], const word a[], size_t n, void *stack)
58 Извлечение квадратного корня
59 word zzDivW (word q[], const word a[], size_t n, register word w)
60 Деление числа на машинное слово
61 word zzModW (const word a[], size_t n, register word w)
62 Остаток от деления числа на машинное слово
63 word zzModW2 (const word a[], size_t n, register word w)
64 Остаток от деления числа на малое машинное слово
65 void zzDiv (word q[], word r[], const word a[], size_t n, const word
66 b[], size_t m, void *stack)
67 Деление чисел
68 void zzMod (word r[], const word a[], size_t n, const word b[], size_t
69 m, void *stack)
70 Остаток от деления чисел
71 void zzGCD (word d[], const word a[], size_t n, const word b[], size_t
72 m, void *stack)
73 Наибольший общий делитель
74 bool_t zzIsCoprime (const word a[], size_t n, const word b[], size_t m,
75 void *stack)
76 Взаимная простота
77 void zzLCM (word d[], const word a[], size_t n, const word b[], size_t
78 m, void *stack)
79 Наименьшее общее кратное
80 void zzExGCD (word d[], word da[], word db[], const word a[], size_t n,
81 const word b[], size_t m, void *stack)
82 Расширенный алгоритм Евклида
83 int zzJacobi (const word a[], size_t n, const word b[], size_t m, void
84 *stack)
85 Символ Якоби
86 void zzAddMod (word c[], const word a[], const word b[], const word
87 mod[], size_t n)
88 Сложение чисел по модулю
89 void zzAddWMod (word b[], const word a[], register word w, const word
90 mod[], size_t n)
91 Сложение числа со словом по модулю
92 void zzSubMod (word c[], const word a[], const word b[], const word
93 mod[], size_t n)
94 Вычитание чисел по модулю
95 void zzSubWMod (word b[], const word a[], register word w, const word
96 mod[], size_t n)
97 Вычитание из числа слова по модулю
98 void zzNegMod (word b[], const word a[], const word mod[], size_t n)
99 Аддитивное обращение чисел по модулю
100 void zzMulMod (word c[], const word a[], const word b[], const word
101 mod[], size_t n, void *stack)
102 Умножение чисел по модулю
103 void zzSqrMod (word b[], const word a[], const word mod[], size_t n,
104 void *stack)
105 Возведение чисел в квадрат по модулю
106 void zzInvMod (word b[], const word a[], const word mod[], size_t n,
107 void *stack)
108 Обращение по модулю
109 void zzDivMod (word b[], const word divident[], const word a[], const
110 word mod[], size_t n, void *stack)
111 Деление по модулю
112 void zzDoubleMod (word b[], const word a[], const word mod[], size_t n)
113 Удвоение числа по модулю
114 void zzHalfMod (word b[], const word a[], const word mod[], size_t n)
115 Половина числа по модулю
116 size_t zzAlmostInvMod (word b[], const word a[], const word mod[],
117 size_t n, void *stack)
118 Почти-обращение по модулю
119 bool_t zzRandMod (word a[], const word mod[], size_t n, gen_i rng, void
120 *rng_state)
121 Случайный вычет по модулю
122 bool_t zzRandNZMod (word a[], const word mod[], size_t n, gen_i rng,
123 void *rng_state)
124 Случайный ненулевой вычет по модулю
125 void zzRed (word a[], const word mod[], size_t n, void *stack)
126 Стандартная редукция
127 void zzRedCrand (word a[], const word mod[], size_t n, void *stack)
128 Редукция Крэндалла
129 void zzRedBarrStart (word barr_param[], const word mod[], size_t n,
130 void *stack)
131 Инициализация редукции Барретта
132 void zzRedBarr (word a[], const word mod[], size_t n, const word
133 barr_param[], void *stack)
134 Редукция Барретта
135 void zzRedMont (word a[], const word mod[], size_t n, register word
136 mont_param, void *stack)
137 Редукция Монтгомери
138 void zzRedCrandMont (word a[], const word mod[], size_t n, register
139 word mont_param, void *stack)
140 Редукция Монтгомери по модулю Крэндалла
141 void zzPowerMod (word c[], const word a[], size_t n, const word b[],
142 size_t m, const word mod[], void *stack)
143 Возведение в степень по модулю
144 word zzPowerModW (register word a, register word b, register word mod,
145 void *stack)
146 Возведение в степень по модулю машинного слова
147
150 Реализованы операции с большими неотрицательными целыми числами.
151 Число задается массивом машинных слов: word w[n]. Машинное слово w[0]
153 -- младшее, машинное слово w[n - 1] -- старшее.
154 Пустое число (n = 0) считается нулевым.
156 В описаниях функций B = 2^{B_PER_W} --- основание системы счисления.
158 Функция zzDoubleMod() совместно с функциями zzAddMod() и zzSubMod()
160 позволяет организовать быстрое модулярное умножение числа на малую
161 константу. Например, вычисление b <- 7 a \mod mod может быть
162 организовано следующим образом:
163 zzDoubleMod(b, a, mod, n);
165 zzDoubleMod(b, b, mod, n);
166 zzDoubleMod(b, b, mod, n);
167 zzSubMod(b, a, mod, n);
168 Аналогично, функция zzHalfMod() позволяет организовать быстрое
171 модулярное деление на определенные константы.
172 Предусловие
174 Все входные указатели действительны.
175 В функциях работы с числами по адресам памяти для чисел
177 зарезервировано ясное из конекста либо уточняемое в описаниях
178 функций число машинных слов.
179 Вспомогательный буфер stack не пересекается с другими буферами.
181
183 Редукция состоит в определении вычета числа [2n]a по модулю [n]mod.
184 Обрабатываемое число всегда состоит из 2n машинных слов и результат
185 всегда возвращается на месте а (ср. с zzMod()). Чтобы подчеркнуть
186 данные соглашения вместо Mod (остаток от деления) пишется Red
187 (редукция).
188 Кроме обычной редукции реализованы быстрые редукции по специальным
190 модулям.
191
193 word zzAdd (word c[], const word a[], const word b[], size_t n)
194 Определяется сумма [n]с чисел [n]a и [n]b:
195 c <- (a + b) \mod B^n, carry <- (a + b) \div B^n,
197 c + B^n * carry == a + b.
198 Предусловие
201 Буфер c либо не пересекается, либо совпадает с каждым из буферов a,
202 b.
203 Возвращает
205 Слово переноса carry.
206 Аргументы
208 c сумма
209 a первое слагаемое
210 b второе слагаемое
211 n длина a, b в машинных словах
212 word zzAdd2 (word b[], const word a[], size_t n)
214 К числу [n]b добавляется число [n]a:
215 b <- (a + b) \mod B^n, carry <- (a + b) \div B^n.
217 Предусловие
220 Буфер b либо не пересекается, либо совпадает с буфером a.
221 Возвращает
223 Слово переноса carry.
224 Аргументы
226 b первое слагаемое / сумма
227 a второе слагаемое
228 n длина a, b в машинных словах
229 word zzAdd3 (word c[], const word a[], size_t n, const word b[], size_t m)
231 Определяется сумма [max(n, m)]с чисел [n]a и [m]b:
232 c <- (a + b) \mod B^{max(n,m)}, carry <- (a + b) \div B^{max(n,m)}.
234 Предусловие
237 Буфер c либо не пересекается, либо совпадает с каждым из буферов a,
238 b.
239 Возвращает
241 Слово переноса carry.
242 Аргументы
244 c сумма
245 a первое слагаемое
246 n длина a в машинных словах
247 b второе слагаемое
248 m длина b в машинных словах
249 void zzAddMod (word c[], const word a[], const word b[], const word mod[],
251 size_t n)
252 Определяется сумма [n]c чисел [n]a и [n]b по модулю [n]mod:
253 с <- (b + a) \mod mod.
255 Предусловие
258 a < mod && b < mod.
259 Буфер c либо не пересекается, либо совпадает с каждым из буферов a,
261 b.
262 Буфер с не пересекается с буфером mod.
264 Регулярность
266 Имеется ускоренная нерегулярная редакция.
267 Аргументы
269 c сумма
270 a первое слагаемое
271 b второе слагаемое
272 mod модуль
273 n длина чисел в машинных словах
274 word zzAddMulW (word b[], const word a[], size_t n, register word w)
276 К числу [n]b добавляется произведение числа [n]a на машинное слово w:
277 b <- (b + a * w) \mod B^n, carry <- (b + a * w) \div B^n.
279 Предусловие
282 Буфер b либо не пересекается, либо совпадает с буфером a.
283 Возвращает
285 Слово переноса carry.
286 Аргументы
288 b слагаемое / сумма
289 a первый множитель
290 n длина a, b в машинных словах
291 w второй множитель
292 word zzAddW (word b[], const word a[], size_t n, register word w)
294 Определяется сумма [n]b числа [n]a и слова w:
295 b <- (a + w) \mod B^n, carry <- (a + w) \div B^n.
297 Предусловие
300 Буфер b либо не пересекается, либо совпадает с буфером a.
301 Возвращает
303 Слово переноса carry.
304 Аргументы
306 b сумма
307 a первое слагаемое
308 n длина a в машинных словах
309 w второе слагаемое
310 word zzAddW2 (word a[], size_t n, register word w)
312 К числу [n]a добавляется слово w:
313 a <- (a + w) \mod B^n, carry <- (a + w) \div B^n.
315 Возвращает
318 Слово переноса carry.
319 Аргументы
321 a слагаемое / сумма
322 n длина a в машинных словах
323 w второе слагаемое
324 void zzAddWMod (word b[], const word a[], register word w, const word
326 mod[], size_t n)
327 Определяется сумма [n]b числа [n]a и слова w по модулю [n]mod:
328 b <- (a + w) \mod mod.
330 Предусловие
333 a < mod && w < mod.
334 Буфер b либо не пересекается, либо совпадает с буфером a.
336 Буфер b не пересекается с буфером mod.
338 Регулярность
340 Имеется ускоренная нерегулярная редакция.
341 Аргументы
343 b сумма
344 a первое слагаемое
345 w второе слагаемое
346 mod модуль
347 n длина чисел в машинных словах
348 size_t zzAlmostInvMod (word b[], const word a[], const word mod[], size_t
350 n, void * stack)
351 Определяется число [n]b, почти-мультипликативно обратное к [n]a по
352 модулю [n]mod:
353 b <- a^{-1} * 2^k \mod mod,
355 где wwBitSize(mod) <= k <= 2 * wwBitSize(mod).
358 Предусловие
360 mod -- нечетное && mod[n - 1] != 0.
361 0 < a < mod.
363 Буфер b не пересекается с буфером mod.
365 Ожидается
367 \gcd(a, mod) == 1.
368 Возвращает
370 Параметр k.
371 Прим.
373 Если \gcd(a, mod) != 1, то b <- 0.
374 Применяя k раз zzHalfMod(), можно определить по b обычный обратный
376 элемент. Применяя n * B_PER_W - k раз zzDoubleMod(), можно
377 определить по b обратный элемент относительно умножения Монтгомери.
378 Схема расчета глубины stack
380 zzAlmostInvMod_deep(n).
381 Регулярность
383 Функция нерегулярна.
384 Аргументы
386 b обратное число
387 a обращаемое число
388 mod модуль
389 n длина чисел в машинных словах
390 stack вспомогательная память
391 void zzDiv (word q[], word r[], const word a[], size_t n, const word b[],
393 size_t m, void * stack)
394 Определяются частное [n - m + 1]q и остаток [m]r от деления числа [n]a
395 на число [m]b:
396 q <- a \div b, r <- r \mod b,
398 a == q * b + r, r < b.
399 Предусловие
402 n >= m.
403 m > 0 && b[m - 1] != 0.
405 Буферы q и r не пересекаются.
407 Буфер r либо не пересекается с буфером a, либо r == a.
409 Схема расчета глубины stack
411 zzDiv_deep(n, m).
412 Регулярность
414 Функция нерегулярна.
415 Аргументы
417 q частное
418 r остаток
419 a делимое
420 n длина a в машинных словах
421 b делитель
422 m длина b в машинных словах
423 stack вспомогательная память
424 void zzDivMod (word b[], const word divident[], const word a[], const word
426 mod[], size_t n, void * stack)
427 Определяется частное [n]b от деления числа [n]divident на число [n]a по
428 модулю [n]mod:
429 b <- divident * a^{-1} \mod mod.
431 Предусловие
434 mod -- нечетное && mod[n - 1] != 0.
435 a, divident < mod.
437 Буфер b не пересекается с буфером mod.
439 Ожидается
441 \gcd(a, mod) = 1.
442 Прим.
444 Если \gcd(a, mod) != 1, то b <- 0.
445 Схема расчета глубины stack
447 zzDivMod_deep(n).
448 Регулярность
450 Функция нерегулярна.
451 Аргументы
453 b частное
454 divident делимое
455 a делитель
456 mod модуль
457 n длина чисел в машинных словах
458 stack вспомогательная память
459 word zzDivW (word q[], const word a[], size_t n, register word w)
461 Определяется частное [n]q от деления числа [n]a на машинное слово w:
462 q <- a \div w.
464 Предусловие
467 w != 0.
468 Буфер q либо не пересекается, либо совпадает с буфером a.
470 Возвращает
472 Остаток от деления.
473 Аргументы
475 q частное
476 a делимое
477 n длина a в машинных словах
478 w делитель
479 void zzDoubleMod (word b[], const word a[], const word mod[], size_t n)
481 Определяется произведение [n]b числа [n]a на число 2 по модулю [n]mod:
482 b <- 2 * a \mod mod.
484 Предусловие
487 a < mod.
488 Буфер b либо не пересекается, либо совпадает с буфером a.
490 Буфер b не пересекается с буфером mod.
492 Регулярность
494 Имеется ускоренная нерегулярная реализация.
495 Аргументы
497 b произведение
498 a множитель
499 mod модуль
500 n длина чисел в машинных словах
501 void zzExGCD (word d[], word da[], word db[], const word a[], size_t n,
503 const word b[], size_t m, void * stack)
504 Определяется наибольший общий делитель [min(n, m)]d чисел [n]a и [m]b:
505 d <- \gcd(a, b),
507 а также положительные числа [m]da и [n]db (коэффициенты Безу) такие,
510 что
511 da * a - db * b == d
513 Предусловие
516 a != 0 && b != 0.
517 Буферы d, da, db не пересекаются между собой и с буферами a, b.
519 Схема расчета глубины stack
521 zzExGCD_deep(n, m).
522 Регулярность
524 Функция нерегулярна.
525 Аргументы
527 d н.о.д.
528 da первый коэффициент Безу
529 db второй коэффициент Безу
530 a первое число
531 n длина a в машинных словах
532 b второе число
533 m длина b в машинных словах
534 stack вспомогательная память
535 void zzGCD (word d[], const word a[], size_t n, const word b[], size_t m,
537 void * stack)
538 Определяется наибольший общий делитель [min(n, m)]d чисел [n]a и [m]b:
539 d <- \gcd(a, b).
541 Предусловие
544 a != 0 && b != 0.
545 Буфер d не пересекается с буферами a и b.
547 Прим.
549 Использование нулевых a и b запрещается для того, чтобы наибольший
550 общий делитель d укладывался в [min(n, m)] слов.
551 Считается, что \gcd(0, b) = b, в частности, \gcd(0, 0) = 0.
553 Схема расчета глубины stack
555 zzGCD_deep(n, m).
556 Регулярность
558 Функция нерегулярна.
559 Аргументы
561 d н.о.д.
562 a первое число
563 n длина a в машинных словах
564 b второе число
565 m длина b в машинных словах
566 stack вспомогательная память
567 void zzHalfMod (word b[], const word a[], const word mod[], size_t n)
569 Определяется частное [n]b от деления числа [n]a на число 2 по модулю
570 [n]mod:
571 b <- a * 2^{-1} \mod mod.
573 Предусловие
576 mod -- нечетное && mod[n - 1] != 0.
577 a < mod.
579 Буфер b либо не пересекается, либо совпадает с буфером a.
581 Буфер b не пересекается с буфером mod.
583 Регулярность
585 Имеется ускоренная нерегулярная реализация.
586 Аргументы
588 b частное
589 a делимое
590 mod модуль
591 n длина чисел в машинных словах
592 void zzInvMod (word b[], const word a[], const word mod[], size_t n, void *
594 stack)
595 Определяется число [n]b, мультипликативно обратное к [n]a по модулю
596 [n]mod:
597 b <- a^{-1} \mod mod.
599 Предусловие
602 mod -- нечетное && mod[n - 1] != 0.
603 a < mod.
605 Буфер b не пересекается с буфером mod.
607 Ожидается
609 \gcd(a, mod) == 1.
610 Прим.
612 Если \gcd(a, mod) != 1, то b <- 0.
613 Схема расчета глубины stack
615 zzInvMod_deep(n).
616 Регулярность
618 Функция нерегулярна.
619 Аргументы
621 b обратное число
622 a обращаемое число
623 mod модуль
624 n длина чисел в машинных словах
625 stack вспомогательная память
626 bool_t zzIsCoprime (const word a[], size_t n, const word b[], size_t m,
628 void * stack)
629 Проверяется, что числа [n]a и [m]b взаимно просты:
630 \gcd(a, b) == 1?
632 Возвращает
635 Признак взаимной простоты a и b.
636 Схема расчета глубины stack
638 zzIsCoprime_deep(n, m).
639 Регулярность
641 Функция нерегулярна.
642 Аргументы
644 a первое число
645 n длина a в машинных словах
646 b второе число
647 m длина b в машинных словах
648 stack вспомогательная память
649 bool_t zzIsEven (const word a[], size_t n)
651 Проверяется, что число [n]a является четным.
652 Возвращает
654 Признак четности.
655 Аргументы
657 a число
658 n длина a в машинных словах
659 bool_t zzIsOdd (const word a[], size_t n)
661 Проверяется, что число [n]a является нечетным.
662 Возвращает
664 Признак нечетности.
665 Аргументы
667 a число
668 n длина a в машинных словах
669 bool_t zzIsSumEq (const word c[], const word a[], const word b[], size_t n)
671 Проверяется, что сумма чисел [n]a и [n]b равняется числу [n]c:
672 a + b == c?
674 Прим.
677 Переставляя операнды, можно проверять не только суммы, но и
678 разности.
679 Возвращает
681 Признак равенства.
682 Регулярность
684 Имеется ускоренная нерегулярная редакция.
685 Аргументы
687 c сумма
688 a первое слагаемое
689 b второе слагаемое
690 n длина a, b, c в машинных словах
691 bool_t zzIsSumWEq (const word b[], const word a[], size_t n, register word
693 w)
694 Проверяется, что сумма числа [n]a и слова w равняется числу [n]b:
695 a + w == b?
697 Возвращает
700 Признак равенства.
701 Регулярность
703 Имеется ускоренная нерегулярная редакция.
704 Аргументы
706 b сумма
707 a первое слагаемое
708 n длина a, b в машинных словах
709 w второе слагаемое
710 int zzJacobi (const word a[], size_t n, const word b[], size_t m, void *
712 stack)
713 Определяется символ Якоби (a / b) чисел [n]a и [m]b.
714 Предусловие
716 b -- нечетное.
717 Прим.
719 Если b является произведением простых p_1, p_2,.., p_k, то (a / b)
720 = (a / p_1) * (a / p_2) *... * (a / p_k). Здесь (a / p_i) ---
721 символ Лежандра: (a / p) равняется 0, если a делится на p,
722 равняется 1, если a -- квадратичный вычет \mod p, и равняется -1 в
723 остальных случаях.
724 Возвращает
726 Символ Якоби (a / b): 0, 1 или -1.
727 Схема расчета глубины stack
729 zzJacobi_deep(n, m).
730 Регулярность
732 Функция нерегулярна.
733 Аргументы
735 a первое число
736 n длина a в машинных словах
737 b второе число
738 m длина b в машинных словах
739 stack вспомогательная память
740 void zzLCM (word d[], const word a[], size_t n, const word b[], size_t m,
742 void * stack)
743 Определяется наименьшее общее кратное [n + m]d чисел [n]a и [m]b:
744 d <- \lcm[a, b].
746 Предусловие
749 a != 0 && b != 0.
750 Буфер d не пересекается с буферами a и b.
752 Прим.
754 Использование нулевых a и b запрещается для согласованости с
755 zzGCD() и избежания разбора редких, неиспользуемых на практике
756 случаев.
757 Схема расчета глубины stack
759 zzLCM_deep(n, m).
760 Регулярность
762 Функция нерегулярна.
763 Аргументы
765 d н.о.к.
766 a первое число
767 n длина a в машинных словах
768 b второе число
769 m длина b в машинных словах
770 stack вспомогательная память
771 void zzMod (word r[], const word a[], size_t n, const word b[], size_t m,
773 void * stack)
774 Определяется остаток [m]r от деления числа [n]a на число [m]b:
775 a <- a \mod b.
777 Предусловие
780 m > 0 && b[m - 1] != 0.
781 Буфер r либо не пересекается с буфером a, либо r == a.
783 Схема расчета глубины stack
785 zzMod_deep(n, m).
786 Регулярность
788 Функция нерегулярна.
789 Аргументы
791 r остаток
792 a делимое
793 n длина a в машинных словах
794 b делитель
795 m длина b в машинных словах
796 stack вспомогательная память
797 word zzModW (const word a[], size_t n, register word w)
799 Определяется остаток от деления числа [n]a на машинное слово w:
800 r <- a \mod w.
802 Предусловие
805 w != 0.
806 Возвращает
808 Остаток от деления r.
809 Аргументы
811 a делимое
812 n длина a в машинных словах
813 w делитель
814 word zzModW2 (const word a[], size_t n, register word w)
816 Определяется остаток от деления числа [n]a на малое машинное слово w:
817 r <- a \mod w.
819 Предусловие
822 w != 0 && w^2 <= B.
823 Возвращает
825 Остаток от деления r.
826 Прим.
828 Функция zzModW2() работает быстрее zzModW() на тех платформах, где
829 деление не менее чем в 2 раза медленнее умножения.
830 Аргументы
832 a делимое
833 n длина a в машинных словах
834 w делитель
835 void zzMul (word c[], const word a[], size_t n, const word b[], size_t m,
837 void * stack)
838 Определяется произведение [n + m]c чисел [n]a на [m]b:
839 c <- a * b.
841 Предусловие
844 Буфер c не пересекается с буферами a и b.
845 Схема расчета глубины stack
847 zzMul_deep(n, m).
848 Аргументы
850 c произведение
851 a первый множитель
852 n длина a в машинных словах
853 b второй множитель
854 m длина b в машинных словах
855 stack вспомогательная память
856 void zzMulMod (word c[], const word a[], const word b[], const word mod[],
858 size_t n, void * stack)
859 Определяется произведение [n]c чисел [n]a и [n]b по модулю [n]mod:
860 c <- a * b \mod mod.
862 Предусловие
865 n > 0 && mod[n - 1] != 0.
866 a < mod && b < mod.
868 Схема расчета глубины stack
870 zzMulMod_deep(n).
871 Аргументы
873 c произведение
874 a первый множитель
875 b второй множитель
876 mod модуль
877 n длина чисел в машинных словах
878 stack вспомогательная память
879 word zzMulW (word b[], const word a[], size_t n, register word w)
881 Определяется произведение [n]b числа [n]a на слово w:
882 b <- (a * w) \mod B^n, carry <- (a * w) \div B^n.
884 Предусловие
887 Буфер b либо не пересекается, либо совпадает с буфером a.
888 Возвращает
890 Слово переноса carry.
891 Аргументы
893 b произведение
894 a первый множитель
895 n длина a, b в машинных словах
896 w второй множитель
897 void zzNeg (word b[], const word a[], size_t n)
899 Определяется число [n]b, отрицательное к [n]a по модулю B^n:
900 b <- B^n - a.
902 Предусловие
905 Буфер b либо не пересекается, либо совпадает с буфером a.
906 Аргументы
908 b отрицательное число
909 a число
910 n длина a в машинных словах
911 void zzNegMod (word b[], const word a[], const word mod[], size_t n)
913 Определяется число [n]b, аддитивно обратное к [n]a по модулю [n]mod:
914 b <- -a \mod mod.
916 Предусловие
919 n > 0 && mod[n - 1] != 0.
920 a < mod.
922 Буфер b либо не пересекается, либо совпадает с буфером a.
924 Буфер b не пересекается с буфером mod.
926 Регулярность
928 Имеется ускоренная нерегулярная редакция.
929 Аргументы
931 b обратное число
932 a число
933 mod модуль
934 n длина чисел в машинных словах
935 void zzPowerMod (word c[], const word a[], size_t n, const word b[], size_t
937 m, const word mod[], void * stack)
938 Определяется число [n]c, которое является [m]b-ой степенью числа [n]a
939 по модулю [n]mod:
940 c <- a^b \mod mod.
942 Предусловие
945 n > 0 && mod[n - 1] != 0.
946 a < mod.
948 Прим.
950 0^0 == 1.
951 Схема расчета глубины stack
953 zzPowerMod_deep(n, m).
954 Регулярность
956 todo
957 Аргументы
959 c степень
960 a основание
961 n длина a, mod в машинных словах
962 b показатель
963 m длина b в машинных словах
964 mod модуль
965 stack вспомогательная память
966 word zzPowerModW (register word a, register word b, register word mod, void
968 * stack)
969 Определяется b-ая степень числа a по модулю машинного слова mod.
970 Предусловие
972 mod != 0.
973 Возвращает
975 Степень.
976 Схема расчета глубины stack
978 zzPowerModW_deep().
979 Регулярность
981 todo
982 Аргументы
984 a основание
985 b показатель
986 mod модуль
987 stack вспомогательная память
988 bool_t zzRandMod (word a[], const word mod[], size_t n, gen_i rng, void *
990 rng_state)
991 С помощью генератора rng с состоянием rng_state определяется случайный
992 вычет [n]a по модулю [n]mod:
993 a <-R {0, 1,..., mod - 1}.
995 Предусловие
998 n > 0 && mod[n - 1] != 0.
999 Буфер a не пересекается с буфером mod.
1001 Возвращает
1003 Признак успеха.
1004 Прим.
1006 Если 2^{l - 1} <= mod < 2^l, то для генерации a потребуется
1007 O_OF_B(l) * 2^l / mod <= 2 * O_OF_B(l) случайных октетов rng в
1008 среднем.
1009 Если rng выдает данные низкого статистического качества, то для
1011 генерации может потребоваться больше октетов, чем указано выше.
1012 Более того, как только количество потребовавшихся октетов превысит
1013 определенный порог d, будет возвращен отрицательный результат.
1014 Порог d выбирается так, что вероятность события 'для генерации
1015 потребуется d истинно случайных октетов' не превосходит
1016 2^{-B_PER_IMPOSSIBLE}.
1017 Регулярность
1019 Время выполнения может флуктуировать. По времени выполнения можно
1020 судить о выходных данных rng, но не тех, которые используются для
1021 формирования a.
1022 Аргументы
1024 a случайное число
1025 mod модуль
1026 n длина a и mod в машинных словах
1027 rng генератор случайных чисел
1028 rng_state состояние генератора
1029 bool_t zzRandNZMod (word a[], const word mod[], size_t n, gen_i rng, void *
1031 rng_state)
1032 С помощью генератора rng с состоянием rng_state определяется случайный
1033 ненулевой вычет [n]a по модулю [n]mod:
1034 a <-R {1, 2,..., mod - 1}.
1036 Предусловие
1039 n > 0 && mod[n - 1] != 0 && mod != 1.
1040 Буфер a не пересекается с буфером mod.
1042 Возвращает
1044 Признак успеха.
1045 Прим.
1047 Если 2^{l - 1} <= mod < 2^l, то для генерации a потребуется
1048 O_OF_B(l) * 2^l / (mod - 1) ≤ 2^l / (2^{l - 1} - 1) O_OF_B(l)
1049 случайных октетов rng в среднем.
1050 Повторяется последнее замечание по функции zzRandMod().
1052 Регулярность
1054 Время выполнения может флуктуировать. По времени выполнения можно
1055 судить о выходных данных rng, но не тех, которые используются для
1056 формирования a.
1057 Аргументы
1059 a случайное число
1060 mod модуль
1061 n длина a и mod в машинных словах
1062 rng генератор случайных чисел
1063 rng_state состояние генератора
1064 void zzRed (word a[], const word mod[], size_t n, void * stack)
1066 Определяется остаток [n]a от деления числа [2n]a на модуль [n]mod.
1067 Предусловие
1069 n >= 1 && mod[n - 1] != 0.
1070 Буферы a и mod не пересекаются.
1072 Схема расчета глубины stack
1074 zzRed_deep(n).
1075 Регулярность
1077 Функция нерегулярна.
1078 Аргументы
1080 a делимое / остаток
1081 mod модуль
1082 n длина mod в машинных словах
1083 stack вспомогательная память
1084 void zzRedBarr (word a[], const word mod[], size_t n, const word
1086 barr_param[], void * stack)
1087 Определяется остаток [n]a от деления числа [2n]a на модуль [n]mod. При
1088 вычислениях используется параметр Барретта [n + 2]barr_param.
1089 Предусловие
1091 n > 0 && mod[n - 1] != 0.
1092 Буфер a не пересекается с буфером mod.
1094 Ожидается
1096 barr_param рассчитан с помощью функции zzRedBarrStart().
1097 Схема расчета глубины stack
1099 zzRedBarr_deep(n).
1100 Регулярность
1102 Имеется ускоренная нерегулярная редакция.
1103 Аргументы
1105 a делимое / остаток
1106 mod модуль
1107 n длина mod в машинных словах
1108 barr_param параметр Барретта
1109 stack вспомогательная память
1110 void zzRedBarrStart (word barr_param[], const word mod[], size_t n, void *
1112 stack)
1113 По модулю [n]mod определяется параметр [n + 2]barr_param:
1114 barr_param <- B^{2n} \div mod.
1116 Этот параметр используется в редукции Барретта.
1119 Предусловие
1121 n > 0 && mod[n] != 0.
1122 Буферы barr_param и mod не пересекаются.
1124 Схема расчета глубины stack
1126 zzRedBarrStart_deep(n).
1127 Аргументы
1129 barr_param параметр Барретта
1130 mod модуль
1131 n длина mod в машинных словах
1132 stack вспомогательная память
1133 void zzRedCrand (word a[], const word mod[], size_t n, void * stack)
1135 Определяется остаток [n]a от деления числа [2n]a на модуль [n]mod,
1136 который близок снизу к B^n.
1137 Предусловие
1139 n >= 2 && mod[n - 1] != 0.
1140 Модуль mod имеет вид B^n - c, где 0 < c < B.
1142 Буферы a и mod не пересекаются.
1144 Схема расчета глубины stack
1146 zzRedCrand_deep(n).
1147 Регулярность
1149 Имеется ускоренная нерегулярная редакция.
1150 Аргументы
1152 a делимое / остаток
1153 mod модуль Крэндалла
1154 n длина mod в машинных словах
1155 stack вспомогательная память (не исп.)
1156 void zzRedCrandMont (word a[], const word mod[], size_t n, register word
1158 mont_param, void * stack)
1159 Определяется результат [n]a редукции Монтгомери числа [2n]a по модулю
1160 [n]mod, который близок снизу к B^n:
1161 a <- a * R^{-1} \mod mod, R == B^n.
1163 При вычислениях используется параметр Монтгомери mont_param.
1166 Предусловие
1168 n >= 2 && mod -- нечетное && mod имеет вид B^n - c, где 0 < c < B.
1169 a < mod * R.
1171 mont_param рассчитан с помощью функции wordNegInv().
1173 Буфер a не пересекается с буфером mod.
1175 Схема расчета глубины stack
1177 zzRedCrandMont_deep(n).
1178 Регулярность
1180 Имеется ускоренная нерегулярная редакция.
1181 Аргументы
1183 a входное число / результат
1184 mod модуль
1185 n длина mod в машинных словах
1186 mont_param параметр Монтгомери
1187 stack вспомогательная память
1188 void zzRedMont (word a[], const word mod[], size_t n, register word
1190 mont_param, void * stack)
1191 Определяется результат [n]a редукции Монтгомери числа [2n]a по модулю
1192 [n]mod:
1193 a <- a * R^{-1} \mod mod, R == B^n.
1195 При вычислениях используется параметр Монтгомери mont_param.
1198 Предусловие
1200 mod -- нечетное && mod[n - 1] != 0.
1201 a < mod * R.
1203 mont_param рассчитан с помощью функции wordNegInv().
1205 Буфер a не пересекается с буфером mod.
1207 Прим.
1209 Редукция предложена в статье [Montgomery P. L. Modular
1210 multiplication without trial division. Mathematics of Computation,
1211 44(170): 519–521, 1985].
1212 Схема расчета глубины stack
1214 zzRedMont_deep(n).
1215 Регулярность
1217 Имеется ускоренная нерегулярная редакция.
1218 Аргументы
1220 a входное число / результат
1221 mod модуль
1222 n длина mod в машинных словах
1223 mont_param параметр Монтгомери
1224 stack вспомогательная память
1225 void zzSqr (word b[], const word a[], size_t n, void * stack)
1227 Определяется квадрат [2n]b числа [n]a:
1228 b <- a * a.
1230 Предусловие
1233 Буфер b не пересекается с буфером a.
1234 Схема расчета глубины stack
1236 zzSqr_deep(n).
1237 Аргументы
1239 b квадрат
1240 a множитель
1241 n длина a в машинных словах
1242 stack вспомогательная память
1243 void zzSqrMod (word b[], const word a[], const word mod[], size_t n, void *
1245 stack)
1246 Определяется квадрат [n]b числа [n]a по модулю [n]mod:
1247 b <- a * a \mod mod.
1249 Предусловие
1252 n > 0 && mod[n - 1] != 0.
1253 a < mod.
1255 Схема расчета глубины stack
1257 zzSqrMod_deep(n).
1258 Аргументы
1260 b квадрат
1261 a множитель
1262 mod модуль
1263 n длина чисел в машинных словах
1264 stack вспомогательная память
1265 bool_t zzSqrt (word b[], const word a[], size_t n, void * stack)
1267 Определяется максимальное целое [(n + 1) / 2]b, квадрат которого не
1268 превосходит [n]a:
1269 b <- \floor(\sqrt(a)).
1271 Возвращает
1274 Признак того, что a является полным квадратом (a == b * b).
1275 Предусловие
1277 Буфер b не пересекается с буфером a.
1278 Схема расчета глубины stack
1280 zzSqrt_deep(n).
1281 Регулярность
1283 Функция нерегулярна: условные переходы, нерегулярные блоки.
1284 Аргументы
1286 b квадратный корень
1287 a число
1288 n длина a в машинных словах
1289 stack вспомогательная память
1290 word zzSub (word c[], const word a[], const word b[], size_t n)
1292 Определяется разность [n]c чисел [n]a и [n]b:
1293 c <- (a - b) \mod B^n, borrow <- (a < b),
1295 c - B^n * borrow == a - b.
1296 Предусловие
1299 Буфер c либо не пересекается, либо совпадает с каждым из буферов a,
1300 b.
1301 Возвращает
1303 Слово заема borrow.
1304 Аргументы
1306 c разность
1307 a уменьшаемое
1308 b вычитаемое
1309 n длина a, b в машинных словах
1310 word zzSub2 (word b[], const word a[], size_t n)
1312 Число [n]b уменьшается на число [n]a:
1313 b <- (b - a) \mod B^n, borrow <- (b < a).
1315 Предусловие
1318 Буфер c либо не пересекается, либо совпадает с каждым из буферов a,
1319 b.
1320 Возвращает
1322 Слово заема borrow.
1323 Аргументы
1325 b уменьшаемое / разность
1326 a вычитаемое
1327 n длина a, b в машинных словах
1328 void zzSubMod (word c[], const word a[], const word b[], const word mod[],
1330 size_t n)
1331 Определяется разность [n]с чисел [n]a и [n]b по модулю [n]mod:
1332 c <- (a - b) \mod mod.
1334 Предусловие
1337 n > 0 && mod[n - 1] != 0.
1338 a < mod && b < mod.
1340 Буфер c либо не пересекается, либо совпадает с каждым из буферов a,
1342 b.
1343 Буфер с не пересекается с буфером mod.
1345 Регулярность
1347 Имеется ускоренная нерегулярная редакция.
1348 Аргументы
1350 c разность
1351 a уменьшаемое
1352 b вычитаемое
1353 mod модуль
1354 n длина чисел в машинных словах
1355 word zzSubMulW (word b[], const word a[], size_t n, register word w)
1357 Из числа [n]b вычитается произведение числа [n]a на машинное слово w:
1358 b <- (b - a * w) \mod B^n, carry <- (b < a * w).
1360 Предусловие
1363 Буфер b либо не пересекается, либо совпадает с буфером a.
1364 Возвращает
1366 Слово заема borrow.
1367 Аргументы
1369 b вычитаемое / разность
1370 a первый множитель
1371 n длина a, b в машинных словах
1372 w второй множитель
1373 word zzSubW (word b[], const word a[], size_t n, register word w)
1375 Определяется разность [n]b числа [n]a и слова w:
1376 b <- (a - w) \mod B^n, borrow <- (a < w).
1378 Предусловие
1381 Буфер b либо не пересекается, либо совпадает с буфером a.
1382 Возвращает
1384 Слово заема borrow.
1385 Аргументы
1387 b разность
1388 a уменьшаемое
1389 n длина a в машинных словах
1390 w вычитаемое
1391 word zzSubW2 (word a[], size_t n, register word w)
1393 Число [n]a уменьшается на слово w:
1394 a <- (a - w) \mod B^n, borrow <- (a < w).
1396 Возвращает
1399 Слово заема borrow.
1400 Аргументы
1402 a уменьшаемое / разность
1403 n длина a в машинных словах
1404 w вычитаемое
1405 void zzSubWMod (word b[], const word a[], register word w, const word
1407 mod[], size_t n)
1408 Определяется разность [n]b числа [n]a и слова w по модулю [n]mod:
1409 b <- (a - w) \mod mod.
1411 Предусловие
1414 a < mod && w < mod.
1415 Буфер b либо не пересекается, либо совпадает с буфером a.
1417 Буфер b не пересекается с буфером mod.
1419 Регулярность
1421 Имеется ускоренная нерегулярная редакция.
1422 Аргументы
1424 b разность
1425 a уменьшаемое
1426 w вычитаемое
1427 mod модуль
1428 n длина чисел в машинных словах
1429
1431 Автоматически создано Doxygen для Библиотека Bee2 из исходного текста.
1432Библиотека Bee2 Пт 23 Июн 2023 zz.h(3)