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

NAME

6       pri.h - Простые числа
7
8

SYNOPSIS

10       #include 'bee2/math/zz.h'
11
12
13   Функции
14       size_t priBaseSize ()
15           Размер факторной базы
16       word priBasePrime (size_t i)
17           Простое из факторной базы
18       void priBaseMod (word mods[], const word a[], size_t n, size_t count)
19           Остатки от деления на простые из факторной базы
20       bool_t priIsSieved (const word a[], size_t n, size_t base_count, void
21           *stack)
22           Просеянное?
23       bool_t priIsSmooth (const word a[], size_t n, size_t base_count, void
24           *stack)
25           Гладкое?
26       bool_t priIsPrimeW (register word a, void *stack)
27           Простое машинное слово?
28       bool_t priRMTest (const word a[], size_t n, size_t iter, void *stack)
29           Тест Рабина -- Миллера
30       bool_t priIsPrime (const word a[], size_t n, void *stack)
31           Простое?
32       bool_t priIsSGPrime (const word q[], size_t n, void *stack)
33           Простое Софи Жермен?
34       bool_t priNextPrimeW (word p[1], word a, void *stack)
35           Следующее малое простое
36       bool_t priNextPrime (word p[], const word a[], size_t n, size_t trials,
37           size_t base_count, size_t iter, void *stack)
38           Следующее простое
39       bool_t priExtendPrime (word p[], size_t l, const word q[], size_t n,
40           size_t trials, size_t base_count, gen_i rng, void *rng_state, void
41           *stack)
42           Расширение простого
43

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

45       Реализована проверка простоты натуральных чисел и построение больших
46       простых. Числа представляются по правилам zz.h.
47
48       Используется факторная база, составленная из первых нечетных простых.
49
50       Предусловие
51           Все входные указатели действительны.
52
53           Вспомогательный буфер stack не пересекается с другими буферами.
54
55       Регулярность
56           todo
57

Функции

59   void priBaseMod (word mods[], const word a[], size_t n, size_t count)
60       Определяются остатки [count]mods от деления числа [n]a на первые count
61       простых из факторной базы.
62
63       Предусловие
64           count <= priBaseSize().
65
66       Аргументы
67           mods остатки
68           a число
69           n длина a в машинных словах
70           count число остатков
71
72   word priBasePrime (size_t i)
73       Определяется i-й элемент факторной базы, т.е. (i + 1)-ое нечетное
74       простое число.
75
76       Предусловие
77           i < priBaseSize().
78
79       Возвращает
80           Элемент факторной базы.
81
82       Аргументы
83           i номер
84
85   size_t priBaseSize ()
86       Возвращается число элементов факторной базы, т.е. число поддерживаемых
87       первых нечетных простых.
88
89       Возвращает
90           Размер факторной базы.
91
92   bool_t priExtendPrime (word p[], size_t l, const word q[], size_t n, size_t
93       trials, size_t base_count, gen_i rng, void * rng_state, void * stack)
94       По базовому нечетному простому [n]q определяется расширенное простое
95       [W_OF_B(l)]p битовой длины l, которое имеет вид 2 * q * r + 1. Число r
96       выбирается с помощью генератора rng с состоянием rng_state. Простота
97       построенного числа p проверяется в два этапа. Сначала проверяется, что
98       p не делится на base_count простых из факторной базы. Затем проверяется
99       условие теоремы Демитко. Если число p не подходит, то оно увеличивается
100       на 2 и проверка повторяется. Если при увеличении p его битовая длина
101       становится больше l, то генерируется новое r, затем p пересчитывается.
102       Всего используется не более trials кандидатов p. При trials == SIZE_MAX
103       ограничений на число кандидатов нет.
104
105       Предусловие
106           Буфер p не пересекается с буфером q.
107
108           q -- нечетное && q >= 3.
109
110           wwBitSize(q, n) + 1 <= l && l <= 2 * wwBitSize(q, n).
111
112           base_count <= priBaseSize().
113
114       Ожидается
115           q -- простое.
116
117       Возвращает
118           TRUE, если искомое простое найдено, и FALSE в противном случае.
119
120       Прим.
121           При trials == SIZE_MAX проверяются все возможные кандидаты.
122
123           Для применения теоремы Демитко требуется выполнение условия 2 * r <
124           4 * q + 1. Ограничение l <= 2 * wwBitSize(q, n) гарантирует
125           выполнение этого условия.
126
127       Схема расчета глубины stack
128           priExtendPrime_deep(l, n, base_count).
129
130       Аргументы
131           p расширенное простое число
132           l длина p в битах
133           q базовое простое число
134           n длина q в машинных словах
135           trials число кандидатов
136           base_count число элементов факторной базы
137           rng генератор случайных чисел
138           rng_state состояние rng
139           stack вспомогательная память
140
141   bool_t priIsPrime (const word a[], size_t n, void * stack)
142       Проверяется, что число [n]a является простым. Используется тест Рабина
143       -- Миллера с числом итераций B_PER_IMPOSSIBLE / 2.
144
145       Возвращает
146           Признак простоты.
147
148       Прим.
149           Вероятность ошибки не превосходит 1 / 2^B_PER_IMPOSSIBLE.
150
151       Схема расчета глубины stack
152           priIsPrime_deep(n).
153
154       Аргументы
155           a проверяемое число
156           n длина a в машинных словах
157           stack вспомогательная память
158
159   bool_t priIsPrimeW (register word a, void * stack)
160       Проверяется что число a, которое укладывается в машинное слово,
161       является простым.
162
163       Возвращает
164           Признак простоты.
165
166       Прим.
167           Реализован детерминированный тест (без ошибок).
168
169       Схема расчета глубины stack
170           priIsPrimeW_deep().
171
172       Аргументы
173           a проверяемое число
174           stack вспомогательная память
175
176   bool_t priIsSGPrime (const word q[], size_t n, void * stack)
177       Проверяется, что нечетное простое число [n]q является простым Софи
178       Жермен, т.е. что 2q + 1 также простое.
179
180       Предусловие
181           q -- нечетное && q > 1.
182
183       Ожидается
184           q -- простое.
185
186       Возвращает
187           Признак успеха.
188
189       Прим.
190           Реализован детерминированный тест (без ошибок).
191
192       Схема расчета глубины stack
193           priIsSGPrime_deep(n).
194
195       Аргументы
196           q проверяемое простое число
197           n длина q в машинных словах
198           stack вспомогательная память
199
200   bool_t priIsSieved (const word a[], size_t n, size_t base_count, void *
201       stack)
202       Проверяется что число [n]a является просеянным: a -- нечетное и не
203       делится на base_count первых простых из факторной базы.
204
205       Предусловие
206           base_count <= priBaseSize().
207
208       Возвращает
209           Признак успеха.
210
211       Прим.
212           Число a не считается просеянным, если совпадает с элементом
213           факторной базы. Число a = 1 считается просеянным.
214
215       Схема расчета глубины stack
216           priIsSieved_deep(n).
217
218       Регулярность
219           Функция нерегулярна.
220
221       Аргументы
222           a проверяемое число
223           n длина a в машинных словах
224           base_count число элементов факторной базы
225           stack вспомогательная память
226
227   bool_t priIsSmooth (const word a[], size_t n, size_t base_count, void *
228       stack)
229       Проверяется что число [n]a является гладким: a делится только на 2 и на
230       base_count первых простых из факторной базы.
231
232       Предусловие
233           base_count <= priBaseSize().
234
235       Возвращает
236           Признак успеха.
237
238       Прим.
239           Число a не считается , если совпадает с элементом факторной базы.
240           Число a = 1 считается просеянным.
241
242       Схема расчета глубины stack
243           priIsSieved_deep(n).
244
245       Аргументы
246           a проверяемое число
247           n длина a в машинных словах
248           base_count число элементов факторной базы
249           stack вспомогательная память
250
251   bool_t priNextPrime (word p[], const word a[], size_t n, size_t trials,
252       size_t base_count, size_t iter, void * stack)
253       Определяется минимальное нечетное простое [n]p из интервала [[n]a,
254       2^l), где l -- битовая длина a. Проверяются на простоту trials первых
255       чисел-кандидатов (или все возможные кандидаты при trials == SIZE_MAX).
256       Сначала проверяется, что кандидат не делится на base_count простых из
257       факторной базы. Затем применяется тест Рабина -- Миллера с iter
258       итерациями.
259
260       Предусловие
261           Буфер p либо не пересекается с буфером a, либо указатели a и p
262           совпадают.
263
264           base_count <= priBaseSize().
265
266       Возвращает
267           TRUE, если искомое простое найдено, и FALSE в противном случае.
268
269       Схема расчета глубины stack
270           priNextPrime_deep(n, base_count).
271
272       Аргументы
273           p простое число
274           a начальное значение
275           n длина a и p в машинных словах
276           trials число кандидатов
277           base_count число элементов факторной базы
278           iter число итераций теста Рабина -- Миллера
279           stack вспомогательная память
280
281   bool_t priNextPrimeW (word p[1], word a, void * stack)
282       Определяется минимальное нечетное простое p из интервала [a, 2^l), где
283       l -- битовая длина a.
284
285       Возвращает
286           Признак успеха.
287
288       Аргументы
289           p простое число
290           a начальное значение
291           stack вспомогательная память
292
293   bool_t priRMTest (const word a[], size_t n, size_t iter, void * stack)
294       С помощью теста Рабина -- Миллера проверяется, что число [n]a является
295       простым. Выполняется iter итераций теста.
296
297       Возвращает
298           Признак простоты.
299
300       Прим.
301           Тест является вероятностным и возможны ошибки. Вероятность
302           признания простым составного числа не превосходит 1 / 4^iter.
303           Простое может быть признано составным, если за большое число
304           попыток не удается построить случайное число из множества {1, 2,..,
305           a - 1} без двух элементов. Вероятность последнего события не
306           превосходит 1 / 2^B_PER_IMPOSSIBLE.
307
308           При iter == 0 простым будет признано всякое нечетное число, большее
309           7.
310
311       Схема расчета глубины stack
312           priRMTest_deep(n).
313
314       Аргументы
315           a проверяемое число
316           n длина a в машинных словах
317           iter число итераций
318           stack вспомогательная память
319

Автор

321       Автоматически создано Doxygen для Библиотека Bee2 из исходного текста.
322
323
324
325Библиотека Bee2                 Пт 23 Июн 2023                        pri.h(3)