pseudo-primes_generation.tex

\subsection{Генерирование псевдопростых чисел}
\selectlanguage{russian}

Идея генерирования псевдопростого числа проста -- выбираем случайное число $n$ заданной битовой длины и проверяем его тестом на простоту. В среднем за $\ln n$ попыток встретится простое число. Если выбирать только нечетные числа, то среднее число попыток $\frac{\ln n}{2}$. На практике для проверки простоты числа обычно применяется тест Миллера--Рабина.

Пусть
    \[ \Delta_L = 2 \cdot 3 \cdot 5 \cdot ~\cdots~ \cdot p_L = \prod \limits_{p \leq p_L} p \]
произведение первых $L$ простых чисел. Из теоремы о распределении простых чисел следует
    \[ L \approx \frac{p_L}{\ln p_L}, ~~ p_L \approx L \ln L. \]
%TODO Что то из Чебышева
Для проверки на простоту случайное число $n_0$ нужной битовой длины выбирается взаимно простым с малыми простыми числами:
    \[ \gcd(n_0, \Delta_L) = 1. \]
Если $n_0$ не проходит тест Миллера--Рабина, то переходим к числу $n_1 = n_0 + \Delta_L$, которое также взаимно простое с $\Delta_L$. И так далее, до тех пор, пока тест не будет пройден  для некоторого
    \[ n_i = n_i + i \cdot \Delta_L. \]

Вероятность того, что случайное \textit{нечетное} число не будет иметь общих делителей с первыми $L$ простыми числами, равна
    \[ P(L) = \prod \limits_{3 \leq p \leq p_L} \left( 1 - \frac{1}{p} \right). \]
Используя приближение $1-x \leq e^{-x}$, получаем
    \[ P(L) ~\lesssim~ e^{-\sum\limits_{3 \leq p \leq p_L} \frac{1}{p}} = e^{\frac{1}{2} ~ - \sum\limits_{p \leq p_L} \frac{1}{p}}. \]
Существует предел
    \[ \lim \limits_{n \rightarrow \infty} \left( \sum \limits_{p \leq n} \frac{1}{p} - \ln \ln n \right) = M, \]
называемый константой Мейсселя--Мертенса
    \[ M \approx 0.261497. \]
Упрощая уравнение, получаем
    \[ P(L) \approx e^{\frac{1}{2} - \ln \ln p_L - M} = \frac{e^{\frac{1}{2} - M}}{\ln(L \ln L)}. \]

Выбор числа, гарантированно не имеющего малых делителей (просеивание чисел), повышает шансы на то, что это число окажется простым. Например, для $L = 10^4$ вероятность, что 1024-битовое нечетное число
    \[ n \approx 2^{1024} \]
окажется простым, повышается в
    \[ \frac{1}{P(10^4)} \approx 10 \]
раз. В среднем каждое
    \[ \frac{\ln n}{2} \cdot P(L) \approx \frac{710}{2} \frac{1}{10} \approx 36 \]
нечетное число может быть простым вместо каждого $\frac{\ln n}{2} \approx 355$ числа (без просеивания), если нечетные числа выбирать без ограничений.

Средняя сложность генерирования $k$-битового псевдопростого числа имеет порядок
    \[ O \left( \frac{\ln n}{2} \cdot \frac{1}{P(L)} \cdot \left( t k^3 \right) \right) = O(t k^4). \]