1pri.h(3) Library Functions Manual pri.h(3)
2
3
4
6 pri.h - Простые числа
7
8
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 Ср 19 Июл 2023 00:00:00 pri.h(3)