bee2-rs 0.2.1

/*
*******************************************************************************
\file pri.h
\brief Primes
\project bee2 [cryptographic library]
\created 2012.08.13
\version 2025.04.25
\copyright The Bee2 authors
\license Licensed under the Apache License, Version 2.0 (see LICENSE.txt).
*******************************************************************************
*/

/*!
*******************************************************************************
\file pri.h
\brief Простые числа
*******************************************************************************
*/

#ifndef __BEE2_PRI_H
#define __BEE2_PRI_H

#include "bee2/defs.h"

#ifdef __cplusplus
extern "C" {
#endif

/*!
*******************************************************************************
\file pri.h

Реализована проверка простоты натуральных чисел и построение больших простых.
Числа представляются по правилам zz.h.

Используется факторная база, составленная из первых нечетных простых.

\pre Все входные указатели действительны.

\pre Вспомогательный буфер stack не пересекается с другими буферами.

\safe todo
*******************************************************************************
*/

/*
*******************************************************************************
Факторная база
*******************************************************************************
*/

/*!	\brief Размер факторной базы

	Возвращается число элементов факторной базы, т.е. число поддерживаемых
	первых нечетных простых.
	\return Размер факторной базы.
*/
size_t priBaseSize();

/*!	\brief Простое из факторной базы

	Определяется i-й элемент факторной базы, т.е. (i + 1)-ое нечетное 
	простое число.
	\pre i < priBaseSize().
	\return Элемент факторной базы.
*/
word priBasePrime(
	size_t i			/*!< [in] номер */
);

/*!	\brief Остатки от деления на простые из факторной базы

	Определяются остатки [count]mods от деления числа [n]a на первые count 
	простых из факторной базы.
	\pre count <= priBaseSize().
*/
void priBaseMod(
	word mods[],		/*!< [out] остатки */
	const word a[],		/*!< [in] число */
	size_t n,			/*!< [in] длина a в машинных словах */
	size_t count		/*!< [in] число остатков */
);

/*
*******************************************************************************
Использование факторной базы
*******************************************************************************
*/

/*!	\brief Просеянное?

	Проверяется что число [n]a является просеянным: a -- нечетное и не делится 
	на base_count первых простых из факторной базы.
	\pre base_count <= priBaseSize().
	\return Признак успеха.
	\remark Число a не считается просеянным, если совпадает с элементом 
	факторной базы. Число a = 1 считается просеянным. 
	\deep{stack} priIsSieved_deep(n).
	\safe Функция нерегулярна.
*/
bool_t priIsSieved(
	const word a[],		/*!< [in] проверяемое число */
	size_t n,			/*!< [in] длина a в машинных словах */
	size_t base_count,	/*!< [in] число элементов факторной базы */
	void* stack			/*!< [in] вспомогательная память */
);

size_t priIsSieved_deep(size_t base_count);

/*!	\brief Гладкое?

	Проверяется что число [n]a является гладким: a делится только на 2 
	и на base_count первых простых из факторной базы.
	\pre base_count <= priBaseSize().
	\return Признак успеха.
	\remark Число a не считается , если совпадает с элементом 
	факторной базы. Число a = 1 считается просеянным. 
	\deep{stack} priIsSmooth_deep(n).
*/
bool_t priIsSmooth(
	const word a[],		/*!< [in] проверяемое число */
	size_t n,			/*!< [in] длина a в машинных словах */
	size_t base_count,	/*!< [in] число элементов факторной базы */
	void* stack			/*!< [in] вспомогательная память */
);

size_t priIsSmooth_deep(size_t n);

/*
*******************************************************************************
Проверка простоты
*******************************************************************************
*/

/*!	\brief Простое машинное слово?

	Проверяется что число a, которое укладывается в машинное слово, является 
	простым.
	\return Признак простоты.
	\remark Реализован детерминированный тест (без ошибок).
	\deep{stack} priIsPrimeW_deep().
*/
bool_t priIsPrimeW(
	register word a,	/*!< [in] проверяемое число */
	void* stack			/*!< [in] вспомогательная память */
);

size_t priIsPrimeW_deep();

/*!	\brief Тест Рабина -- Миллера

	С помощью теста Рабина -- Миллера проверяется, что число [n]a
	является простым. Выполняется iter итераций теста. 
	\return Признак простоты.
	\remark Тест является вероятностным и возможны ошибки. Вероятность 
	признания простым составного числа не превосходит 1 / 4^iter.
	Простое может быть признано составным, если за большое число попыток 
	не удается построить случайное число из множества {1, 2,.., a - 1}
	без двух элементов. Вероятность последнего события не превосходит 
	1 / 2^B_PER_IMPOSSIBLE.
	\remark При iter == 0 простым будет признано всякое нечетное число,
	большее 7.
	\deep{stack} priRMTest_deep(n).
*/
bool_t priRMTest(
	const word a[],		/*!< [in] проверяемое число */
	size_t n,			/*!< [in] длина a в машинных словах */
	size_t iter,		/*!< [in] число итераций */
	void* stack			/*!< [in] вспомогательная память */
);

size_t priRMTest_deep(size_t n);

/*!	\brief Простое?

	Проверяется, что число [n]a является простым. Используется
	тест Рабина -- Миллера с числом итераций B_PER_IMPOSSIBLE / 2.
	\return Признак простоты.
	\remark Вероятность ошибки не превосходит 1 / 2^B_PER_IMPOSSIBLE.
	\deep{stack} priIsPrime_deep(n).
*/
bool_t priIsPrime(
	const word a[],		/*!< [in] проверяемое число */
	size_t n,			/*!< [in] длина a в машинных словах */
	void* stack			/*!< [in] вспомогательная память */
);

size_t priIsPrime_deep(size_t n);

/*!	\brief Простое Софи Жермен?

	Проверяется, что нечетное простое число [n]q является простым Софи Жермен, 
	т.е. что 2q + 1 также простое.
	\pre q -- нечетное && q > 1.
	\expect q -- простое.
	\return Признак успеха.
	\remark Реализован детерминированный тест (без ошибок).
	\deep{stack} priIsSGPrime_deep(n).
*/
bool_t priIsSGPrime(
	const word q[],		/*!< [in] проверяемое простое число */
	size_t n,			/*!< [in] длина q в машинных словах */
	void* stack			/*!< [in] вспомогательная память */
);

size_t priIsSGPrime_deep(size_t n);

/*
*******************************************************************************
Генерация простых
*******************************************************************************
*/

/*!	\brief Следующее малое простое

	Определяется минимальное нечетное простое p из интервала [a, 2^l),
	где l -- битовая длина a.
	\return Признак успеха.
*/
bool_t priNextPrimeW(
	word p[1],			/*!< [out] простое число */
	word a,				/*!< [in] начальное значение */
	void* stack			/*!< [in] вспомогательная память */
);

size_t priNextPrimeW_deep();

/*!	\brief Следующее простое

	Определяется минимальное нечетное простое [n]p из интервала [[n]a, 2^l), 
	где l -- битовая длина a. Проверяются на простоту trials первых 
	чисел-кандидатов (или все возможные кандидаты при trials == SIZE_MAX). 
	Сначала проверяется, что кандидат не делится на base_count простых из 
	факторной базы. Затем применяется тест Рабина -- Миллера с iter итерациями.
	\pre Буфер p либо не пересекается с буфером a, либо указатели a и p
	совпадают.
	\pre base_count <= priBaseSize().
	\return TRUE, если искомое простое найдено, и FALSE в противном случае.
	\deep{stack} priNextPrime_deep(n, base_count).
*/

bool_t priNextPrime(
	word p[],			/*!< [out] простое число */
	const word a[],		/*!< [in] начальное значение */
	size_t n,			/*!< [in] длина a и p в машинных словах */
	size_t trials,		/*!< [in] число кандидатов */
	size_t base_count,	/*!< [in] число элементов факторной базы */
	size_t iter,		/*!< [in] число итераций теста Рабина -- Миллера */
	void* stack			/*!< [in] вспомогательная память */
);

size_t priNextPrime_deep(size_t n, size_t base_count);

/*!	\brief Расширение простого

	По базовому нечетному простому [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.
	\pre Буфер p не пересекается с буфером q.
	\pre n > 0 && q[n - 1] != 0.
	\pre q -- нечетное && q >= 3.
	\pre wwBitSize(q, n) + 1 <= l && l <= 2 * wwBitSize(q, n).
	\pre base_count <= priBaseSize().
	\expect q -- простое.
	\return TRUE, если искомое простое найдено, и FALSE в противном случае.
	\remark При trials == SIZE_MAX проверяются все возможные кандидаты.
	\remark Для применения теоремы Демитко требуется выполнение условия 
	2 * r < 4 * q + 1. Ограничение l <= 2 * wwBitSize(q, n) гарантирует
	выполнение этого условия.
	\deep{stack} priExtendPrime_deep(l, n, base_count).
*/

bool_t priExtendPrime(
	word p[],			/*!< [out] расширенное простое число */
	size_t l,			/*!< [in] длина p в битах */
	const word q[],		/*!< [in] базовое простое число */
	size_t n,			/*!< [in] длина q в машинных словах */
	size_t trials,		/*!< [in] число кандидатов */
	size_t base_count,	/*!< [in] число элементов факторной базы */
	gen_i rng,			/*!< [in] генератор случайных чисел */
	void* rng_state,	/*!< [in] состояние rng */
	void* stack			/*!< [in] вспомогательная память */
);

size_t priExtendPrime_deep(size_t l, size_t n, size_t base_count);

/*!	\brief Расширение простого с условием делимости

	По базовому нечетному простому [n]q и неотрицательному [m]a строится
	расширенное простое [W_OF_B(l)]p битовой длины l, которое имеет вид
	2 * q * a * r + 1. Число r строится с помощью генератора rng с состоянием
	rng_state. Простота p проверяется так же, как в функции priExtendPrime().
	Используется base_count простых из факторной базы, используется не более 
	trials кандидатов p.
	\pre Буфер p не пересекается с буфером q.
	\pre n > 0 && q[n - 1] != 0 && m > 0 && a[m - 1] != 0.
	\pre q -- нечетное && q >= 3.
	\pre wwBitSize(q * a, n + m) + 1 <= l.
	\pre l <= 2 * wwBitSize(q, n).
	\pre base_count <= priBaseSize().
	\expect q -- простое.
	\return TRUE, если искомое простое найдено, и FALSE в противном случае.
	\remark При trials == SIZE_MAX проверяются все возможные кандидаты.
	\remark Для применения теоремы Демитко требуется выполнение условия 
	2 * a * r < 4 * q + 1. Ограничение l <= 2 * wwBitSize(q, n) гарантирует
	выполнение этого условия.
	\deep{stack} priExtendPrime2_deep(l, n, m, base_count).
*/

bool_t priExtendPrime2(
	word p[],			/*!< [out] расширенное простое число */
	size_t l,			/*!< [in] длина p в битах */
	const word q[],		/*!< [in] базовое простое число */
	size_t n,			/*!< [in] длина q в машинных словах */
	const word a[],		/*!< [in] делитель p - 1 */
	size_t m,			/*!< [in] длина m в машинных словах */
	size_t trials,		/*!< [in] число кандидатов */
	size_t base_count,	/*!< [in] число элементов факторной базы */
	gen_i rng,			/*!< [in] генератор случайных чисел */
	void* rng_state,	/*!< [in] состояние rng */
	void* stack			/*!< [in] вспомогательная память */
);

size_t priExtendPrime2_deep(size_t l, size_t n, size_t m, size_t base_count);

#ifdef __cplusplus
} /* extern "C" */
#endif

#endif /* __BEE2_PRI_H */