pri.h(3)

📦
version 2.2.0 · 2 versions
, in fedora 44

pri.h(3) — Library Functions Manual 🎀 okay bestie, welcome to the prime-number corner of the library ✨

💖 NAME 💖

pri.h — Простые числа (prime numbers) 👑

✨ SYNOPSIS ✨

#include 'bee2/defs.h'

🧚 Функции

  • size_t priBaseSize () — Размер факторной базы (size of the factor base) 💅
  • word priBasePrime (size_t i) — Простое из факторной базы (a prime from the factor base) ✨
  • void priBaseMod (word mods[], const word a[], size_t n, size_t count) — Остатки от деления на простые из факторной базы (remainders from division by the primes in the factor base) 🍓
  • bool_t priIsSieved (const word a[], size_t n, size_t base_count, void *stack) — Просеянное? (sieved?) 🧐
  • bool_t priIsSmooth (const word a[], size_t n, size_t base_count, void *stack) — Гладкое? (smooth?) 🌸
  • bool_t priIsPrimeW (register word a, void *stack) — Простое машинное слово? (prime machine word?) 💀
  • bool_t priRMTest (const word a[], size_t n, size_t iter, void *stack) — Тест Рабина -- Миллера (Rabin--Miller test) 🔥
  • bool_t priIsPrime (const word a[], size_t n, void *stack) — Простое? (prime?) 👑
  • bool_t priIsSGPrime (const word q[], size_t n, void *stack) — Простое Софи Жермен? (Sophie Germain prime?) 🎀
  • bool_t priNextPrimeW (word p[1], word a, void *stack) — Следующее малое простое (next small prime) ⭐
  • bool_t priNextPrime (word p[], const word a[], size_t n, size_t trials, size_t base_count, size_t iter, void *stack) — Следующее простое (next prime) 🌈
  • 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) — Расширение простого (prime extension) 🦋
  • bool_t priExtendPrime2 (word p[], size_t l, const word q[], size_t n, const word a[], size_t m, size_t trials, size_t base_count, gen_i rng, void *rng_state, void *stack) — Расширение простого с условием делимости (prime extension with divisibility condition) 💜

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

okay so basically this library does primality checking for natural numbers and builds big primes. Numbers are represented following the rules of zz.h. 💅

It uses a factor base made of the first odd primes. 🧚

Предусловие

  • All input pointers are valid. ✅
  • The auxiliary buffer stack does not overlap with other buffers. 🚫

Регулярность

todo 💀

🧚 Функции 🧚

void priBaseMod (word mods[], const word a[], size_t n, size_t count)

Defines the remainders [count]mods from dividing the number [n]a by the first count primes from the factor base. 🍓

Предусловие

  • count <= priBaseSize(). ✅

Аргументы

  • mods — остатки (remainders) ✨
  • a — число (number) 💅
  • n — длина a в машинных словах (length of a in machine words) 🧚
  • count — число остатков (number of remainders) 🎀

word priBasePrime (size_t i)

Returns the i-th element of the factor base, i.e. the (i + 1)-th odd prime number. 👑

Предусловие

  • i < priBaseSize(). ✅

Возвращает

  • Элемент факторной базы (the factor base element). 💖

Аргументы

  • i — номер (number/index) 🔢

size_t priBaseSize ()

Returns the number of elements in the factor base, i.e. the number of supported first odd primes. 🌈

Возвращает

  • Размер факторной базы (size of the factor base). 💅

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)

From a base odd prime [n]q, it builds an extended prime [W_OF_B(l)]p of bit length l, which has the form 2 * q * r + 1. The number r is built using the generator rng with state rng_state. The primality of the constructed number p is checked in two stages. First, it checks that p is not divisible by base_count primes from the factor base. Then it checks the condition of Demitko's theorem. If the number p doesn't fit, it is increased by 2 and the check repeats. If while increasing p its bit length becomes greater than l, then a new r is generated, then p is recalculated. In total, no more than trials candidates p are used. 🔥

Предусловие

  • Буфер p не пересекается с буфером q (buffer p does not overlap with buffer q). 🚫
  • n > 0 && q[n - 1] != 0. ✅
  • q -- нечетное && q >= 3 (q is odd && q >= 3). 💅
  • wwBitSize(q, n) + 1 <= l && l <= 2 * wwBitSize(q, n). ✅
  • base_count <= priBaseSize(). ✅

Ожидается

  • q -- простое (q is prime). 👑

Возвращает

  • TRUE, если искомое простое найдено, и FALSE в противном случае (TRUE if the sought prime is found, and FALSE otherwise). ✨

Прим.

  • При trials == SIZE_MAX проверяются все возможные кандидаты (when trials == SIZE_MAX, all possible candidates are checked). 💀
  • Для применения теоремы Демитко требуется выполнение условия 2 * r < 4 * q + 1. Ограничение l <= 2 * wwBitSize(q, n) гарантирует выполнение этого условия (to apply Demitko's theorem, the condition 2 * r < 4 * q + 1 must hold. The restriction l <= 2 * wwBitSize(q, n) guarantees this condition). 🧐

Схема расчета глубины stack

priExtendPrime_deep(l, n, base_count).

Аргументы

  • p — расширенное простое число (extended prime number) 💖
  • l — длина p в битах (length of p in bits) 📏
  • q — базовое простое число (base prime number) 🔢
  • n — длина q в машинных словах (length of q in machine words) 🧚
  • trials — число кандидатов (number of candidates) 🎯
  • base_count — число элементов факторной базы (number of factor base elements) 🍓
  • rng — генератор случайных чисел (random number generator) 🎲
  • rng_state — состояние rng (state of rng) 🌸
  • stack — вспомогательная память (auxiliary memory) 📦

bool_t priExtendPrime2 (word p[], size_t l, const word q[], size_t n, const word a[], size_t m, size_t trials, size_t base_count, gen_i rng, void * rng_state, void * stack)

From a base odd prime [n]q and a non-negative [m]a, it builds an extended prime [W_OF_B(l)]p of bit length l, which has the form 2 * q * a * r + 1. The number r is built using the generator rng with state rng_state. The primality of p is checked the same way as in priExtendPrime(). It uses base_count primes from the factor base, and no more than trials candidates p. 🔥

Предусловие

  • Буфер p не пересекается с буфером q (buffer p does not overlap with buffer q). 🚫
  • n > 0 && q[n - 1] != 0 && m > 0 && a[m - 1] != 0. ✅
  • q -- нечетное && q >= 3 (q is odd && q >= 3). 💅
  • wwBitSize(q * a, n + m) + 1 <= l. ✅
  • l <= 2 * wwBitSize(q, n). ✅
  • base_count <= priBaseSize(). ✅

Ожидается

  • q -- простое (q is prime). 👑

Возвращает

  • TRUE, если искомое простое найдено, и FALSE в противном случае (TRUE if the sought prime is found, and FALSE otherwise). ✨

Прим.

  • При trials == SIZE_MAX проверяются все возможные кандидаты (when trials == SIZE_MAX, all possible candidates are checked). 💀
  • Для применения теоремы Демитко требуется выполнение условия 2 * a * r < 4 * q + 1. Ограничение l <= 2 * wwBitSize(q, n) гарантирует выполнение этого условия (to apply Demitko's theorem, the condition 2 * a * r < 4 * q + 1 must hold. The restriction l <= 2 * wwBitSize(q, n) guarantees this condition). 🧐

Схема расчета глубины stack

priExtendPrime2_deep(l, n, m, base_count).

Аргументы

  • p — расширенное простое число (extended prime number) 💖
  • l — длина p в битах (length of p in bits) 📏
  • q — базовое простое число (base prime number) 🔢
  • n — длина q в машинных словах (length of q in machine words) 🧚
  • a — делитель p - 1 (divisor of p - 1) ➗
  • m — длина m в машинных словах (length of m in machine words) 🙈
  • trials — число кандидатов (number of candidates) 🎯
  • base_count — число элементов факторной базы (number of factor base elements) 🍓
  • rng — генератор случайных чисел (random number generator) 🎲
  • rng_state — состояние rng (state of rng) 🌸
  • stack — вспомогательная память (auxiliary memory) 📦

bool_t priIsPrime (const word a[], size_t n, void * stack)

Checks that the number [n]a is prime. Uses the Rabin--Miller test with number of iterations B_PER_IMPOSSIBLE / 2. 🔥

Возвращает

  • Признак простоты (primality flag). ✅

Прим.

  • Вероятность ошибки не превосходит 1 / 2^B_PER_IMPOSSIBLE (probability of error does not exceed 1 / 2^B_PER_IMPOSSIBLE). 🎲

Схема расчета глубины stack

priIsPrime_deep(n).

Аргументы

  • a — проверяемое число (number to check) 🔍
  • n — длина a в машинных словах (length of a in machine words) 🧚
  • stack — вспомогательная память (auxiliary memory) 📦

bool_t priIsPrimeW (register word a, void * stack)

Checks that the number a, which fits into a machine word, is prime. 💅

Возвращает

  • Признак простоты (primality flag). ✅

Прим.

  • Реализован детерминированный тест (без ошибок) (a deterministic test is implemented, no errors). 👑

Схема расчета глубины stack

priIsPrimeW_deep().

Аргументы

  • a — проверяемое число (number to check) 🔍
  • stack — вспомогательная память (auxiliary memory) 📦

bool_t priIsSGPrime (const word q[], size_t n, void * stack)

Checks that the odd prime number [n]q is a Sophie Germain prime, i.e. that 2q + 1 is also prime. 🎀

Предусловие

  • q -- нечетное && q > 1 (q is odd && q > 1). 💅

Ожидается

  • q -- простое (q is prime). 👑

Возвращает

  • Признак успеха (success flag). ✅

Прим.

  • Реализован детерминированный тест (без ошибок) (a deterministic test is implemented, no errors). 👑

Схема расчета глубины stack

priIsSGPrime_deep(n).

Аргументы

  • q — проверяемое простое число (prime number to check) 🔍
  • n — длина q в машинных словах (length of q in machine words) 🧚
  • stack — вспомогательная память (auxiliary memory) 📦

bool_t priIsSieved (const word a[], size_t n, size_t base_count, void * stack)

Checks that the number [n]a is sieved: a is odd and is not divisible by the first base_count primes from the factor base. 🧐

Предусловие

  • base_count <= priBaseSize(). ✅
  • Возвращает — Признак успеха ✨ (то есть да или нет, третьего не дано, периодt).
  • Прим. — Число a не считается просеянным, если оно совпадает с элементом факторной базы. А вот число a = 1 считается просеянным 🫶 (да, единичка сразу проходит, не спрашивай).
  • Схема расчета глубины stack — priIsSieved_deep(n).
  • Регулярность — Функция нерегулярна 🙈 (она такая, сюрприз-сюрприз, живём).
  • Аргументы
    • a — проверяемое число
    • n — длина a в машинных словах
    • base_count — число элементов факторной базы
    • stack — вспомогательная память

🦋 bool_t priIsSmooth — а число-то гладкое? 🦋

bool_t priIsSmooth (const word a[], size_t n, size_t base_count, void *
       stack)

Проверяется, что число [n]a является гладким: a делится только на 2 и на base_count первых простых из факторной базы. Как будто число прошло жёсткий vibe check на «а ты вообще из наших простых?» 💅

Предусловие

base_count <= priBaseSize(). Не забывай, окей, иначе всё сломается и будет грустно 😭

Возвращает

Признак успеха ✅

Прим.

Число a не считается , если совпадает с элементом факторной базы. Число a = 1 считается просеянным. (Да, тут так и написано, я ничего не трогала, fr fr.)

Схема расчета глубины stack

priIsSmooth_deep(n).

Аргументы

  • a — проверяемое число
  • n — длина a в машинных словах
  • base_count — число элементов факторной базы
  • stack — вспомогательная память

👑 bool_t priNextPrime — следующее простое, подъём 👑✨

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 — да, прям все, main character energy).

Сначала проверяется, что кандидат не делится на base_count простых из факторной базы. Затем применяется тест Рабина -- Миллера с iter итерациями. Двойная проверка, потому что мы серьёзные 🎀

Предусловие

Буфер p либо не пересекается с буфером a, либо указатели a и p совпадают. (Пожалуйста, не делай ничего между этими двумя вариантами, это буквально запрещено 🙈)

base_count <= priBaseSize().

Возвращает

TRUE, если искомое простое найдено, и FALSE в противном случае. Всё просто, no cap.

Схема расчета глубины stack

priNextPrime_deep(n, base_count).

Аргументы

  • p — простое число
  • a — начальное значение
  • n — длина a и p в машинных словах
  • trials — число кандидатов
  • base_count — число элементов факторной базы
  • iter — число итераций теста Рабина -- Миллера
  • stack — вспомогательная память

🌸 bool_t priNextPrimeW — маленькая, но удаленькая 🌸

bool_t priNextPrimeW (word p[1], word a, void * stack)

Определяется минимальное нечетное простое p из интервала [a, 2^l), где l — битовая длина a. Это как priNextPrime, только компактная версия, она ate и не поморщилась 💅

Возвращает

Признак успеха ✅

Аргументы

  • p — простое число
  • a — начальное значение
  • stack — вспомогательная память

🔥 bool_t priRMTest — Рабин -- Миллер заходит в чат 🔥

bool_t priRMTest (const word a[], size_t n, size_t iter, void * stack)

С помощью теста Рабина -- Миллера проверяется, что число [n]a является простым. Выполняется iter итераций теста. Чем больше итераций, тем спокойнее спится, iykyk.

Возвращает

Признак простоты.

Прим.

Тест является вероятностным и возможны ошибки. Это не баг, это фича, bestie, но давай честно: вероятность признания простым составного числа не превосходит 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 из исходного текста. (Да, это Doxygen нас всех породил, уважаем процесс 🫶)

И на этой ноте — всё, страница закрыта, ты официально знаешь pri.h 🌈

Эта красотка живёт в Библиотеке Bee2, датирована Вс 25 Янв 2026 00:00:00 и зовётся просто pri.h(3) 💖 Спасибо, что дочитала до конца, ты легенда, go slay ✨

📦 where this page comes from