pri.h - Man Page
Простые числа
Synopsis
#include 'bee2/math/zz.h'
Функции
size_t priBaseSize ()
Размер факторной базы
word priBasePrime (size_t i)
Простое из факторной базы
void priBaseMod (word mods[], const word a[], size_t n, size_t count)
Остатки от деления на простые из факторной базы
bool_t priIsSieved (const word a[], size_t n, size_t base_count, void *stack)
Просеянное?
bool_t priIsSmooth (const word a[], size_t n, size_t base_count, void *stack)
Гладкое?
bool_t priIsPrimeW (register word a, void *stack)
Простое машинное слово?
bool_t priRMTest (const word a[], size_t n, size_t iter, void *stack)
Тест Рабина -- Миллера
bool_t priIsPrime (const word a[], size_t n, void *stack)
Простое?
bool_t priIsSGPrime (const word q[], size_t n, void *stack)
Простое Софи Жермен?
bool_t priNextPrimeW (word p[1], word a, void *stack)
Следующее малое простое
bool_t priNextPrime (word p[], const word a[], size_t n, size_t trials, size_t base_count, size_t iter, void *stack)
Следующее простое
bool_t priExtendPrime (word p[], size_t l, const word q[], size_t n, size_t trials, size_t base_count, gen_i rng, void *rng_state, void *stack)
Расширение простого
Подробное описание
Реализована проверка простоты натуральных чисел и построение больших простых. Числа представляются по правилам zz.h.
Используется факторная база, составленная из первых нечетных простых.
Предусловие
Все входные указатели действительны.
Вспомогательный буфер stack не пересекается с другими буферами.
- Регулярность
todo
Функции
void priBaseMod (word mods[], const word a[], size_t n, size_t count)
Определяются остатки [count]mods от деления числа [n]a на первые count простых из факторной базы.
- Предусловие
count <= priBaseSize().
- Аргументы
mods остатки
a число
n длина a в машинных словах
count число остатков
word priBasePrime (size_t i)
Определяется i-й элемент факторной базы, т.е. (i + 1)-ое нечетное простое число.
- Предусловие
i < priBaseSize().
Возвращает
Элемент факторной базы.
- Аргументы
i номер
size_t priBaseSize ()
Возвращается число элементов факторной базы, т.е. число поддерживаемых первых нечетных простых.
Возвращает
Размер факторной базы.
bool_t priExtendPrime (word p[], size_t l, const word q[], size_t n, size_t trials, size_t base_count, gen_i rng, void * rng_state, void * stack)
По базовому нечетному простому [n]q определяется расширенное простое [W_OF_B(l)]p битовой длины l, которое имеет вид 2 * q * r + 1. Число r выбирается с помощью генератора rng с состоянием rng_state. Простота построенного числа p проверяется в два этапа. Сначала проверяется, что p не делится на base_count простых из факторной базы. Затем проверяется условие теоремы Демитко. Если число p не подходит, то оно увеличивается на 2 и проверка повторяется. Если при увеличении p его битовая длина становится больше l, то генерируется новое r, затем p пересчитывается. Всего используется не более trials кандидатов p. При trials == SIZE_MAX ограничений на число кандидатов нет.
Предусловие
Буфер p не пересекается с буфером q.
q -- нечетное && q >= 3.
wwBitSize(q, n) + 1 <= l && l <= 2 * wwBitSize(q, n).
base_count <= priBaseSize().
- Ожидается
q -- простое.
- Возвращает
TRUE, если искомое простое найдено, и FALSE в противном случае.
Прим.
При trials == SIZE_MAX проверяются все возможные кандидаты.
Для применения теоремы Демитко требуется выполнение условия 2 * r < 4 * q + 1. Ограничение l <= 2 * wwBitSize(q, n) гарантирует выполнение этого условия.
- Схема расчета глубины stack
priExtendPrime_deep(l, n, base_count).
- Аргументы
p расширенное простое число
l длина p в битах
q базовое простое число
n длина q в машинных словах
trials число кандидатов
base_count число элементов факторной базы
rng генератор случайных чисел
rng_state состояние rng
stack вспомогательная память
bool_t priIsPrime (const word a[], size_t n, void * stack)
Проверяется, что число [n]a является простым. Используется тест Рабина -- Миллера с числом итераций B_PER_IMPOSSIBLE / 2.
Возвращает
Признак простоты.
Прим.
Вероятность ошибки не превосходит 1 / 2^B_PER_IMPOSSIBLE.
- Схема расчета глубины stack
priIsPrime_deep(n).
- Аргументы
a проверяемое число
n длина a в машинных словах
stack вспомогательная память
bool_t priIsPrimeW (register word a, void * stack)
Проверяется что число a, которое укладывается в машинное слово, является простым.
Возвращает
Признак простоты.
Прим.
Реализован детерминированный тест (без ошибок).
- Схема расчета глубины stack
priIsPrimeW_deep().
- Аргументы
a проверяемое число
stack вспомогательная память
bool_t priIsSGPrime (const word q[], size_t n, void * stack)
Проверяется, что нечетное простое число [n]q является простым Софи Жермен, т.е. что 2q + 1 также простое.
- Предусловие
q -- нечетное && q > 1.
- Ожидается
q -- простое.
Возвращает
Признак успеха.
Прим.
Реализован детерминированный тест (без ошибок).
- Схема расчета глубины stack
priIsSGPrime_deep(n).
- Аргументы
q проверяемое простое число
n длина q в машинных словах
stack вспомогательная память
bool_t priIsSieved (const word a[], size_t n, size_t base_count, void * stack)
Проверяется что число [n]a является просеянным: a -- нечетное и не делится на base_count первых простых из факторной базы.
- Предусловие
base_count <= priBaseSize().
Возвращает
Признак успеха.
Прим.
Число a не считается просеянным, если совпадает с элементом факторной базы. Число a = 1 считается просеянным.
Схема расчета глубины stack
priIsSieved_deep(n).
Регулярность
Функция нерегулярна.
- Аргументы
a проверяемое число
n длина a в машинных словах
base_count число элементов факторной базы
stack вспомогательная память
bool_t priIsSmooth (const word a[], size_t n, size_t base_count, void * stack)
Проверяется что число [n]a является гладким: a делится только на 2 и на base_count первых простых из факторной базы.
- Предусловие
base_count <= priBaseSize().
Возвращает
Признак успеха.
Прим.
Число a не считается , если совпадает с элементом факторной базы. Число a = 1 считается просеянным.
- Схема расчета глубины stack
priIsSieved_deep(n).
- Аргументы
a проверяемое число
n длина a в машинных словах
base_count число элементов факторной базы
stack вспомогательная память
bool_t priNextPrime (word p[], const word a[], size_t n, size_t trials, size_t base_count, size_t iter, void * stack)
Определяется минимальное нечетное простое [n]p из интервала [[n]a, 2^l), где l -- битовая длина a. Проверяются на простоту trials первых чисел-кандидатов (или все возможные кандидаты при trials == SIZE_MAX). Сначала проверяется, что кандидат не делится на base_count простых из факторной базы. Затем применяется тест Рабина -- Миллера с iter итерациями.
Предусловие
Буфер p либо не пересекается с буфером a, либо указатели a и p совпадают.
base_count <= priBaseSize().
- Возвращает
TRUE, если искомое простое найдено, и FALSE в противном случае.
- Схема расчета глубины stack
priNextPrime_deep(n, base_count).
- Аргументы
p простое число
a начальное значение
n длина a и p в машинных словах
trials число кандидатов
base_count число элементов факторной базы
iter число итераций теста Рабина -- Миллера
stack вспомогательная память
bool_t priNextPrimeW (word p[1], word a, void * stack)
Определяется минимальное нечетное простое p из интервала [a, 2^l), где l -- битовая длина a.
Возвращает
Признак успеха.
- Аргументы
p простое число
a начальное значение
stack вспомогательная память
bool_t priRMTest (const word a[], size_t n, size_t iter, void * stack)
С помощью теста Рабина -- Миллера проверяется, что число [n]a является простым. Выполняется iter итераций теста.
Возвращает
Признак простоты.
Прим.
Тест является вероятностным и возможны ошибки. Вероятность признания простым составного числа не превосходит 1 / 4^iter. Простое может быть признано составным, если за большое число попыток не удается построить случайное число из множества {1, 2,.., a - 1} без двух элементов. Вероятность последнего события не превосходит 1 / 2^B_PER_IMPOSSIBLE.
При iter == 0 простым будет признано всякое нечетное число, большее 7.
- Схема расчета глубины stack
priRMTest_deep(n).
- Аргументы
a проверяемое число
n длина a в машинных словах
iter число итераций
stack вспомогательная память
Автор
Автоматически создано Doxygen для Библиотека Bee2 из исходного текста.