Sponsor:

Your company here — click to reach over 10,000 unique daily visitors

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 из исходного текста.

Info

Вт 23 Янв 2024 00:00:00 Библиотека Bee2