zm.h(3) - f38

1zm.h(3)                    Library Functions Manual                    zm.h(3)
2
3
4

NAME

6       zm.h - Кольца вычетов целых чисел
7
8

SYNOPSIS

10       #include 'bee2/math/qr.h'
11
12
13   Функции
14       void zmCreatePlain (qr_o *r, const octet mod[], size_t no, void *stack)
15           Создание описания кольца вычетов целых чисел с обычной редукцией
16       void zmCreateCrand (qr_o *r, const octet mod[], size_t no, void *stack)
17           Создание описания кольца вычетов целых чисел с редукцией Крэндалла
18       void zmCreateBarr (qr_o *r, const octet mod[], size_t no, void *stack)
19           Создание описания кольца вычетов целых чисел с редукцией Барретта
20       void zmCreateMont (qr_o *r, const octet mod[], size_t no, void *stack)
21           Создание описания кольца вычетов целых чисел с редукцией Монтгомери
22       void zmCreate (qr_o *r, const octet mod[], size_t no, void *stack)
23           Создание описания кольца вычетов целых чисел
24       void zmMontCreate (qr_o *r, const octet mod[], size_t no, size_t l,
25           void *stack)
26           Создание описания кольца Монтгомери
27       bool_t zmIsValid (const qr_o *r)
28           Описание кольца вычетов целых чисел корректно?
29

Подробное описание

31       Реализованы операции в кольце вычетов Zm = Z / (mod), где mod --
32       произвольное натуральное число.
33
34       Элементы кольца кодируются строками из no октетов и задаются массивами
35       из W_OF_O(no) машинных слов, где no -- длина mod в октетах. При
36       кодировании используются порядок 'от младших к старшим'. Перечисленные
37       соглашения можно учитывать при планировании работы с кольцом.
38
39       Для редукции по модулю mod используются функции, объявленные в zz.h:
40
41       • обычная редукция zzRed();
42
43       • редукция Крэндалла zzRedCrand();
44
45       • редукция Барретта zzRedBarr();
46
47       • редукция Монтгомери zzRedMont().
48
49       В кольце с редукцией Монтгомери вместо обычного умножения
50
51       c <- a * b \mod mod
52
53
54        используется специальное умножение
55
56       c <- a * b * R^{-1} \mod mod,
57
58
59        где R -- минимальное число вида B^n, большее mod.
60
61       Мультипликативной единицей в кольце Монтгомери является число R \mod
62       mod, мультипликативно обратный к a элемент: a^{-1} * R^2 \mod mod.
63
64       Число a из обычного кольца вычетов преобразуется в элемент a * R \mod
65       mod кольца Монтгомери. После вычислений в кольце выходной элемент b
66       преобразуется в число b * R^{-1} \mod mod.
67
68       Кольцо, которое создается с помощью функции zmMontCreate(), является
69       'чистым' кольцом Монтгомери. Элементы этого кольца представляются
70       числами 'как есть'. Чистые кольца Монтгомери используются в алгоритмах
71       СТБ 1176.2. В чистом кольце R = 2^l, причем l не обязательно кратно
72       B_PER_W, т.е. R не обязательно имеет вид B^n.
73
74       Прим.
75           Функции zzCreateMont() и zzMontCreate() создают разные кольца.
76
77       Предусловие
78           Все указатели действительны.
79
80       Регулярность
81           todo
82

Функции

84   void zmCreate (qr_o * r, const octet mod[], size_t no, void * stack)
85       По модулю [no]mod, представленному строкой октетов, создается описание
86       r кольца Z / (mod). Подбирается оптимальное (с точки зрения
87       эффективности вычислений) описание.
88
89       Предусловие
90           no > 0 && mod[no - 1] > 0.
91
92       Постусловие
93           r->no == no и r->n == W_OF_O(no).
94
95       Прим.
96           Оптимальное кольцо подбирается с учетом следующих результатов
97           экспериментов (2013.09.17):
98
99           • редукция Крэндалла примерно в 2 раза быстрее редукции Монтгомери;
100
101           • редукция Монтгомери примерно в 2 раза быстрее редукции Барретта;
102
103           • редукция Барретта несколько опережает обычную редукцию при r->n
104             >= 4.
105
106       Схема расчета размера состояния r
107           zmCreate_keep(no).
108
109       Схема расчета глубины stack
110           zmCreate_deep(no).
111
112       Аргументы
113           r описание кольца
114           mod модуль
115           no длина mod в октетах
116           stack вспомогательная память
117
118   void zmCreateBarr (qr_o * r, const octet mod[], size_t no, void * stack)
119       По модулю [no]mod, представленному строкой октетов, создается описание
120       r кольца Z / (mod). При вычислениях в кольце используется редукция
121       Барретта.
122
123       Предусловие
124           no > 0 && mod[no - 1] > 0.
125
126       Постусловие
127           r->no == no и r->n == W_OF_O(no).
128
129       Схема расчета размера состояния r
130           zmCreateBarr_keep(no).
131
132       Схема расчета глубины stack
133           zmCreateBarr_deep(no).
134
135       Аргументы
136           r описание кольца
137           mod модуль
138           no длина mod в октетах
139           stack вспомогательная память
140
141   void zmCreateCrand (qr_o * r, const octet mod[], size_t no, void * stack)
142       По модулю [no]mod, представленному строкой октетов, создается описание
143       r кольца Z / (mod). При вычислениях в кольце используется редукция
144       Крэндалла.
145
146       Предусловие
147           no > 0 && mod[no - 1] > 0.
148
149           mod == B^n - c, где n >= 2 && 0 < c < B.
150
151       Постусловие
152           r->no == no и r->n == W_OF_O(no).
153
154       Схема расчета размера состояния r
155           zmCreateCrand_keep(no).
156
157       Схема расчета глубины stack
158           zmCreateCrand_deep(no).
159
160       Аргументы
161           r описание кольца
162           mod модуль
163           no длина mod в октетах
164           stack вспомогательная память
165
166   void zmCreateMont (qr_o * r, const octet mod[], size_t no, void * stack)
167       По модулю [no]mod, представленному строкой октетов, создается описание
168       r кольца Z / (mod). При вычислениях в кольце используется редукция
169       Монтгомери.
170
171       Предусловие
172           no > 0 && mod[no - 1] > 0.
173
174           mod -- нечетное число.
175
176       Постусловие
177           r->no == no и r->n == W_OF_O(no).
178
179       Схема расчета размера состояния r
180           zmCreateMont_keep(no).
181
182       Схема расчета глубины stack
183           zmCreateMont_deep(no).
184
185       Аргументы
186           r описание кольца
187           mod модуль
188           no длина mod в октетах
189           stack вспомогательная память
190
191   void zmCreatePlain (qr_o * r, const octet mod[], size_t no, void * stack)
192       По модулю [no]mod, представленному строкой октетов, создается описание
193       r кольца Z / (mod). При вычислениях в кольце используется обычная
194       редукция.
195
196       Предусловие
197           no > 0 && mod[no - 1] > 0.
198
199       Постусловие
200           r->no == no и r->n == W_OF_O(no).
201
202       Схема расчета размера состояния r
203           zmCreatePlain_keep(no).
204
205       Схема расчета глубины stack
206           zmCreatePlain_deep(no).
207
208       Аргументы
209           r описание кольца
210           mod модуль
211           no длина mod в октетах
212           stack вспомогательная память
213
214   bool_t zmIsValid (const qr_o * r)
215       Проверяется корректность описания r кольца Z / (mod). Проверяются
216       следующие условия:
217
218       • qrIsOperable(r) == TRUE;
219
220       • указатель r->mod корректен;
221
222       • r->mod[r->n - 1] > 0.
223
224       Возвращает
225           Признак корректности.
226
227       Прим.
228           Работоспособность и корректность эквивалентны.
229
230       Аргументы
231           r описание кольца
232
233   void zmMontCreate (qr_o * r, const octet mod[], size_t no, size_t l, void *
234       stack)
235       По модулю [no]mod, представленному строкой октетов, создается описание
236       r кольца Монтгомери c параметром R = 2^l.
237
238       Предусловие
239           no > 0 && mod[no - 1] > 0.
240
241           mod -- нечетное число.
242
243           mod < R && B^n <= R (n -- число слов для размещения mod).
244
245       Прим.
246           Если кольцо построено, то r->no == no и r->n == W_OF_O(no).
247
248       Схема расчета размера состояния r
249           zmMontCreate_keep(no).
250
251       Схема расчета глубины stack
252           zmMontCreate_deep(no).
253
254       Аргументы
255           r описание кольца
256           mod модуль
257           no длина mod в октетах
258           l показатель в параметре R
259           stack вспомогательная память
260

Автор

262       Автоматически создано Doxygen для Библиотека Bee2 из исходного текста.
263
264
265
266Библиотека Bee2                 Пт 23 Июн 2023                         zm.h(3)