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

NAME

6       qr.h - Кольца вычетов
7
8

SYNOPSIS

10       #include 'bee2/defs.h'
11       #include 'bee2/core/obj.h'
12
13
14   Классы
15       struct qr_o
16           Описание кольца вычетов
17
18   Определения типов
19       typedef bool_t(* qr_from_i) (word b[], const octet a[], const struct
20           qr_o *r, void *stack)
21           Импорт элемента кольца вычетов
22       typedef void(* qr_to_i) (octet b[], const word a[], const struct qr_o
23           *r, void *stack)
24           Экспорт элемента кольца вычетов
25       typedef void(* qr_add_i) (word c[], const word a[], const word b[],
26           const struct qr_o *r)
27           Сложение в кольце вычетов
28       typedef void(* qr_sub_i) (word c[], const word a[], const word b[],
29           const struct qr_o *r)
30           Вычитание в кольце вычетов
31       typedef void(* qr_neg_i) (word b[], const word a[], const struct qr_o
32           *r)
33           Аддитивное обращение в кольце вычетов
34       typedef void(* qr_mul_i) (word c[], const word a[], const word b[],
35           const struct qr_o *r, void *stack)
36           Умножение в кольце вычетов
37       typedef void(* qr_sqr_i) (word b[], const word a[], const struct qr_o
38           *r, void *stack)
39           Возведение в квадрат в кольце вычетов
40       typedef void(* qr_inv_i) (word b[], const word a[], const struct qr_o
41           *r, void *stack)
42           Мультипликативное обращение в кольце вычетов
43       typedef void(* qr_div_i) (word b[], const word divident[], const word
44           a[], const struct qr_o *r, void *stack)
45           Деление в кольце вычетов
46       typedef struct qr_o qr_o
47           Описание кольца вычетов
48
49   Функции
50       bool_t qrIsOperable (const qr_o *r)
51           Описание кольца вычетов работоспособно?
52       void qrPower (word c[], const word a[], const word b[], size_t m, const
53           qr_o *r, void *stack)
54           Возведение в степень в кольце вычетов
55

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

57       Пусть R -- кольцо, I -- его идеал. Кольцом вычетов называется кольцо R
58       / I, в котором сложение и умножение элементов выполняется по модулю I:
59       (a + I) + (b + I) = (a + b) + I, (a + I) * (b + I) = (a * b) + I.
60
61       В интересующих нас случаях кольцо R является коммутативным, а идеал I
62       -- главным, т.е. порожденным единственным элементом mod ∈ R: I = (mod)
63       = {mod * a: a ∈ R}. В этих случаях приведение по модулю I состоит в
64       редукции (определении вычета) по модулю mod.
65
66       Кольцо вычетов описывается структурой типа qr_o.
67
68       Структура qr_o проектировалась с прицелом на поддержку следующих колец:
69
70       • R = Z, mod = n --- произвольное натуральное [кольцо вычетов целых
71         чисел ZZ_n];
72
73       • R = Z, mod = p -- простое число [простое поле GF(p)];
74
75       • R = GF(2)[x], mod = f(x) --- неприводимый многочлен степени e [поле
76         GF(2^e)].
77
78       В этих кольцах может применяться умножение Монтгомери, умножение в
79       нормальном базисе и другие ускоренные мультипликативные операции.
80       Особенные операции требуют особенного описания кольца и особенного
81       представления его элементов. В связи с этим вводится структура qr_o,
82       которая задает:
83
84       • описание кольца вычетов;
85
86       • описание элементов кольца;
87
88       • интерфейсы арифметических операций в кольце.
89
90       Идеал I описывается модулем mod. Для ускорения редукции по модулю mod
91       могут использоваться параметры params. Параметры params могут
92       рассчитываться по mod при создании кольца, могут дублировать mod, или
93       заменять его. Параметры params имеют самостоятельное значение и могут
94       использоваться не только для редукции.
95
96       Элемент кольца представляется массивом из n машинных слов. Размерность
97       n определяется при построении кольца и сохраняется в его описании.
98
99       Нулевому элементу всегда соответствует нулевой массив.
100
101       Мультипликативные единицы могут отличаться. Мультипликативная единица
102       unity инициализируется при построении кольца.
103
104       Размерность модуля mod жестко не регламентируется. Эта размерность
105       определяется в функциях работы с элементами кольца по params и (или) n.
106       В кольцах чисел mod задается n словами. Если mod = 2^{B_PER_W * (n -
107       1)}, то последнее слово mod равняется 1, а последние слова элементов
108       поля всегда равняются 0. В кольцах многочленов mod задается n или n + 1
109       словом (в зависимости от выполнения равенства deg(mod) == B_PER_W * n).
110
111       Элементы кольца экспортируются в строки октетов и импортируются из этих
112       строк. Длина строки no определяется при построении кольца и сохраняется
113       в его описании. Для экспорта / импорта элементов кольца используются
114       функции типов qr_to_i, qr_from_i. Способ определения длины строки
115       указывается при описании колец конкретных типов. Нулевому элементу
116       обязательно соответствует нулевая строка.
117
118       Аддитивные операции в кольце, как правило, не меняются при различных
119       его описаниях. Тем не менее, в структуру qr_o включены функции
120       интерфейсов qr_add_i, qr_sub_i и qr_neg_i, которые определяют
121       аддитивные операции.
122
123       Мультипликативные операции в кольце задаются интерфейсами qr_mul_i и
124       qr_sqr_i.
125
126       Некоторые элементы кольца допускают мультипликативное обращение и,
127       следовательно, определенные пары элементов можно делить друг на друга.
128       Обращение и деление поддерживается интерфейсами qr_inv_i, qr_div_i.
129
130       Описание кольца организовано как объект, и можно применять функции,
131       описанные в заголовочном файле obj.h.
132
133       Кольцо должно создаваться специальной функцией qrCreate(), которая
134       является аналогом конструктора. В эту функцию должен передаваться
135       указатель r на структуру типа qr_o. По этому указателю будет
136       размещаться описание (состояние) кольца. По адресу r может быть
137       зарезервировано больше памяти, чем sizeof(qr_o). Дело в том, что
138       значения mod, unity, params могут размещаться в поле descr открытого
139       размера. Функция qrCreate() должна сопровождаться функцией
140       qrCreate_keep(), которая поддерживает расчет длины состояния (в
141       октетах).
142
143       Функция qrCreate_keep() должна оценивать длину состояния сверху. Оценка
144       может быть неточной. Точная длина состояния фиксируется при
145       непосредственном выполнении qrCreate() и сохраняется в поле keep
146       описания кольца.
147
148       В функцию qrCreate() должен передаваться указатель на память для стека.
149       Функция qrCreate() должна сопровождаться функцией qrCreate_deep(),
150       которая выполняет расчет глубины стека. При расчете глубины следует
151       предполагать, что в qrCreate() явно или неявно вызываются все функции
152       кольца. Получив результат работы qrCreate_deep(), внешние программы
153       могут определить, сколько вспомогательной памяти потребуется при
154       всевозможных способах работы с кольцом.
155
156       В описании qrCreate() должны быть даны оценки сверху для размерностей n
157       и no. Эти оценки могут использоваться высокоуровневыми функциями при
158       подготовке памяти для размещения элементов кольца.
159
160       Оценка глубины стека, определяемая функцией qrCreate_deep(), может быть
161       неточной. Точная глубина фиксируется при непосредственном выполнении
162       qrCreate() и сохраняется в поле deep описания кольца.
163
164       Предусловие
165           Все указатели действительны.
166
167           Буферы элементов кольца или их кодовых представлений не
168           пересекаются с буферами, поддерживающими описание кольца.
169
170       Предупреждения
171           В интерфейсах мультипликативных функций не предполагается, что
172           буфер результата либо не пересекается, либо совпадает с буферами
173           входных элементов.
174
175       Регулярность
176           todo
177

Типы

179   typedef void(* qr_add_i) (word c[], const word a[], const word b[], const
180       struct qr_o *r)
181       Определяется сумма [r->n]c элементов [r->n]a и [r->n]b кольца вычетов
182       r:
183
184       c <- a + b.
185
186
187       Предусловие
188           Описание кольца r работоспособно.
189
190           Буфер c либо не пересекается, либо совпадает с каждым из буферов a,
191           b.
192
193           Элементы a и b принадлежат r.
194
195       Ожидается
196           Описание кольца r корректно.
197
198       Аргументы
199           c сумма
200           a первое слагаемое
201           b второе слагаемое
202           r описание кольца
203
204   typedef void(* qr_div_i) (word b[], const word divident[], const word a[],
205       const struct qr_o *r, void *stack)
206       Определяется частное [r->n]b от деления элемента [r->n]divident на
207       элемент [r->n]a в кольце вычетов r:
208
209       b <- divident * a^{-1}.
210
211
212       Предусловие
213           Описание кольца r работоспособно.
214
215           Элементы divident и a принадлежат r.
216
217       Ожидается
218           Описание кольца r корректно.
219
220       Ожидается
221           Элемент a обратим. Если a не обратим, то b может быть любым.
222
223       Аргументы
224           b частное
225           divident делимое
226           a делитель
227           r описание кольца
228           stack вспомогательная память
229
230   typedef bool_t(* qr_from_i) (word b[], const octet a[], const struct qr_o
231       *r, void *stack)
232       По кодовому представлению [r->no]a строится элемент [r->n]b кольца
233       вычетов r.
234
235       Предусловие
236           Описание кольца r работоспособно.
237
238           Буферы a и b либо не пересекаются, либо указатели a и b совпадают.
239
240       Ожидается
241           Описание кольца r корректно.
242
243       Возвращает
244           TRUE, если кодовое представление корректно и импорт успешно
245           выполнен, и FALSE в противном случае.
246
247       Аргументы
248           b элемент кольца
249           a кодовое представление элемента кольца
250           r описание кольца
251           stack вспомогательная память
252
253   typedef void(* qr_inv_i) (word b[], const word a[], const struct qr_o *r,
254       void *stack)
255       Определяется элемент [r->n]b кольца r, мультипликативно обратный к
256       элементу [r->n]a:
257
258       b <- a^{-1}.
259
260
261       Предусловие
262           Описание кольца r работоспособно.
263
264           Элемент a принадлежит r.
265
266       Ожидается
267           Описание кольца r корректно.
268
269       Ожидается
270           Элемент a обратим. Если a не обратим, то b может быть любым.
271
272       Аргументы
273           b обратный элемент
274           a обращаемый элемент
275           r описание кольца
276           stack вспомогательная память
277
278   typedef void(* qr_mul_i) (word c[], const word a[], const word b[], const
279       struct qr_o *r, void *stack)
280       Определяется произведение [r->n]c элементов [r->n]a и [r->n]b кольца
281       вычетов r:
282
283       с <- a * b.
284
285
286       Предусловие
287           Описание кольца r работоспособно.
288
289           Элементы a и b принадлежат r.
290
291       Ожидается
292           Описание кольца r корректно.
293
294       Аргументы
295           c произведение
296           a первый множитель
297           b второй множитель
298           r описание кольца
299           stack вспомогательная память
300
301   typedef void(* qr_neg_i) (word b[], const word a[], const struct qr_o *r)
302       Определяется элемент [r->n]b кольца r, аддитивно обратный к [r->n]a:
303
304       b <- -a.
305
306
307       Предусловие
308           Описание кольца r работоспособно.
309
310           Буфер b либо не пересекается, либо совпадает с буфером a.
311
312           Элемент a принадлежит r.
313
314       Ожидается
315           Описание кольца r корректно.
316
317       Аргументы
318           b обратный элемент
319           a обращаемый элемент
320           r описание кольца
321
322   typedef struct qr_o qr_o
323       Описывается кольцо вычетов, правила представления его элементов и
324       функции, реализующие операции в кольце.
325
326       Прим.
327           В таблицу указателей описания кольца как объекта входят поля mod,
328           unity, params.
329
330   typedef void(* qr_sqr_i) (word b[], const word a[], const struct qr_o *r,
331       void *stack)
332       Определяется квадрат [r->n]b элемента [r->n]a кольца r:
333
334       с <- a * a.
335
336
337       Предусловие
338           Описание кольца r работоспособно.
339
340           Элемент a принадлежит r.
341
342       Ожидается
343           Описание кольца r корректно.
344
345       Аргументы
346           b квадрат
347           a множитель
348           r описание кольца
349           stack вспомогательная память
350
351   typedef void(* qr_sub_i) (word c[], const word a[], const word b[], const
352       struct qr_o *r)
353       Определяется разность [r->n]c элементов [r->n]a и [r->n]b кольца
354       вычетов r:
355
356       c <- a - b.
357
358
359       Предусловие
360           Описание кольца r работоспособно.
361
362           Буфер c либо не пересекается, либо совпадает с каждым из буферов a,
363           b.
364
365           Элементы a и b принадлежат r.
366
367       Ожидается
368           Описание кольца r корректно.
369
370       Аргументы
371           c разность
372           a уменьшаемое
373           b вычитаемое
374           r описание кольца
375
376   typedef void(* qr_to_i) (octet b[], const word a[], const struct qr_o *r,
377       void *stack)
378       Строится кодовое представление [r->no]b элемента [r->n]a кольца вычетов
379       r.
380
381       Предусловие
382           Описание кольца r работоспособно.
383
384           Буферы a и b либо не пересекаются, либо указатели a и b совпадают.
385
386       Ожидается
387           Описание кольца r корректно.
388
389       Аргументы
390           b кодовое представление элемента кольца
391           a элемент кольца
392           r описание кольца
393           stack вспомогательная память
394

Функции

396   bool_t qrIsOperable (const qr_o * r)
397       Проверяется работоспособность описания r кольца вычетов. Проверяются
398       следующие условия:
399
400       • объект r работоспособен;
401
402       • objKeep(r) >= sizeof(qr_o);
403
404       • objPCount(r) == 3 && objOCount(r) == 0;
405
406       • указатель r->unity корректен;
407
408       • r->n > 0 && r->no > 0;
409
410       • указатели r->from, r->to, ..., r->div корректны.
411
412       Возвращает
413           Признак работоспособности.
414
415       Аргументы
416           r описание кольца
417
418   void qrPower (word c[], const word a[], const word b[], size_t m, const
419       qr_o * r, void * stack)
420       В кольце вычетов r определяется элемент [r->n]c, который является
421       [m]b-ой степенью элемента [r->n]a:
422
423       c <- a^b.
424
425
426       Предусловие
427           Описание кольца r работоспособно.
428
429           Элемент a принадлежит r.
430
431       Ожидается
432           Описание кольца r корректно.
433
434       Прим.
435           При b == 0 возвращается r->unity.
436
437       Схема расчета глубины stack
438           qrPower_deep(r->n, m, r->deep).
439
440       Аргументы
441           c степень
442           a основание
443           b показатель
444           m длина b в машинных словах
445           r описание кольца
446           stack вспомогательная память
447

Автор

449       Автоматически создано Doxygen для Библиотека Bee2 из исходного текста.
450
451
452
453Библиотека Bee2                 Пт 23 Июн 2023                         qr.h(3)