16.6. Псевдопростые числа

16.6.1. Оценка числа простых чисел

Функция $\pi(n)$ определяется как количество простых чисел из диапазона $[2, n]$. Существует предел [27, 44]

$$ \lim\limits_{n \rightarrow \infty}\frac{ \pi(n)}{ \frac{n}{\ln n}}=1. $$

Для $n \geq 17$ верно неравенство $\pi(n) > \frac{n}{\ln n}$.

Идея поиска(генерации) простых чисел состоит в случайном выборе числа и тестировании его на простоту.

Вероятность $P_k$ того, что случайное $k$-битовое число $n$ будет простым, равна

$$ \lim\limits_{k \rightarrow \infty} P_k = \frac{1}{\ln n} = \frac{1}{k \ln 2}. $$

Пример. Вероятность того, что случайное 500-битное число, включая чётные числа, будет простым, примерно равна $\frac{1}{347}$, вероятность простоты случайного 2000-битного числа примерно равна $\frac{1}{1386}$.

Для дальнейшего рассмотрения интересен также вопрос об оценке вероятности того, что число $n$ будет простым, если оно априори взаимно простое с первыми $L$ простыми числами.

Пусть

$$ \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. $$

Вероятность того, что случайное нечётное число не будет иметь общих делителей с первыми $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~ \operatorname{exp}\left(-\sum\limits_{3 \leq p \leq p_L} \frac{1}{p}\right) = \operatorname{exp}\left(\frac{1}{2} - \sum\limits_{p \leq p_L} \frac{1}{p}\right). $$

Существует предел

$$ \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)}. $$

16.6.2. Генерирование псевдопростых чисел

Значительная часть криптосистем на открытых ключах основывается на использовании больших простых чисел. Однако получение таких чисел не является тривиальной операцией.

Генерировать большие простые числа заранее и сохранять их в некоторой таблице, например, для их последующего использования в качестве множителей модуля $n$ в криптосистеме RSA, небезопасно. Криптоаналитику для факторизации $n$ вместо перебора всех простых чисел в качестве кандидатов делителей $n$ будет достаточно перебрать заранее сохранённую таблицу возможных кандидатов. Однако и эффективной процедуры генерации больших простых чисел, пригодных для использования в криптографии, неизвестно. Поэтому под генерацией больших простых чисел обычно используют и подразумевают процедуру поиска больших простых чисел, описанную ниже.

  1. Выбрать большое (псевдо)случайное нечётное число нужной битовой длины.
  2. Проверить, является ли число простым.
  3. Если не является, то вернуться к п. 1. Иначе вернуть число как результат процедуры.

Дополнительной проблемой является тот факт, что быстрые и качественные алгоритмы проверки на простоту также неизвестны. Все существующие алгоритмы можно классифицировать следующим образом.

Идеальный алгоритм проверки чисел на простоту должен быть доказанным, детерминированным и полиномиальным. Кроме ограниченного роста количества операций («полиномиального») алгоритм должен обладать высокой скоростью работы для тех чисел, которые используются уже сейчас (2000 бит и выше) на современных персональных компьютерах. К сожалению, такие алгоритмы неизвестны.

В настоящий момент для проверки числа на простоту используют комбинацию «наивного» алгоритма и теста Миллера — Рабина.

  1. Выбрать параметр «уверенности» (англ. certainty), который вместе с требуемой битовой длиной числа будет являться входом алгоритма.
  2. Выбрать большое (псевдо)случайное нечётное число $n$ нужной битовой длины.
  3. Проверить, является ли число $n$ простым по «наивному» тесту до некоторого числа $m \ll n$ (часто – константа алгоритма).
  4. Проверить, является ли число $n$ простым по тесту Миллера — Рабина с числом раундов, которое зависит от значения параметра «уверенности».
  5. Если число $n$ прошло все тесты, то оно является выходом алгоритма. Иначе возвращаемся к п. 2.

Числа, полученные с помощью подобного алгоритма (или любого другого, если для проверки на простоту используются вероятностные алгоритмы), называются псевдопростыми.

Согласно формулам из предыдущего раздела, в среднем за $\ln n$ попыток встретится простое число. Если выбирать только нечётные числа, то среднее число попыток $\frac{\ln n}{2}$. Однако если выбирать такие числа, которые гарантированно не имеют малых делителей («просеивание чисел»), то значительно повышаются шансы, что это число окажется простым. Например, для $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 $$

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). $$

16.6.3. «Наивный» тест

«Наивный» тест состоит в проверке того, что число $n$ не делится на числа от $2$ до $\sqrt{n}$. Из определения простоты числа следует, что алгоритм будет являться корректным. Также очевидно, что алгоритм будет являться неполиномиальным относительно битовой длины числа $n$. Однако на нём можно удачно проиллюстрировать определение «свидетеля простоты», которое будет использоваться в алгоритмах в дальнейшем.

Будем называть число $a$ свидетелем простоты числа $n$ по наивному алгоритму, если выполняется условие

$$ n / a \notin {\mathbb{Z}}. $$

Теперь детерминированный «наивный» алгоритм можно сформулировать следующим образом: если все числа $a$ от 2 до $\sqrt{n}$ являются свидетелями простоты числа $n$ по наивному алгоритму, то число $n$ является простым. Иначе – составным.

Детерминированный «наивный» тест можно превратить в вероятностный.

  1. Выберем случайным образом $k$ различных $a_1, a_2, \dots, a_k$ от 2 до $\sqrt{n}$.
  2. Проверим, являются ли они все свидетелями простоты числа $n$ по наивному алгоритму.
  3. Если являются, то будем утверждать, что число $n$ является псевдопростым с вероятностью ошибки $\epsilon < \left( 1 - 1 / \sqrt{n} \right)^k$, иначе – составнымВероятность ошибки получена из вероятности «наткнуться» на несвидетеля простоты числа $n$ по наивному алгоритму, которая для чисел от 2 до $\sqrt{n}$ не менее $1 / \sqrt{n}$ (минимальная вероятность для случая, когда $n = p \times q$, $p < \sqrt{n} < q$)..

Так как проверку каждого «свидетеля» можно сделать за одну операцию деления (полиномиальное число операций относительно длины числа $n$), то для заданного числа проверок $k$ данный вариант алгоритма будет являться доказанным, полиномиальным, но вероятностным. Кроме того, вероятность ошибки $\epsilon$ слишком велика. Для того чтобы вероятность ошибки составляла менее 99, число проверок $k$ должно быть сравнимо по величине с $\sqrt{n}$.

16.6.4. Тест Ферма

Многие тесты на простоту основаны на малой теореме Ферма [113]: если $n$ – простое число и $a$ – целое число, не делящееся на $n$, то

equation a^n-1 1 n.

Можно сформулировать следующую «обратную» теорему. Если для некоторого $a: 1 < a < n$ не выполняется утверждение [eq:prime-check-ferma], то число $n$ не является простым. На этой теореме основан следующий алгоритм, который и называется тестом Ферма.

Будем называть число $a$ свидетелем простоты числа $n$ по Ферма, если для него выполняется [eq:prime-check-ferma].

Тест Ферма для числа $n$ состоит в том, чтобы проверить, что все числа от $2$ до $n$ являются свидетелями простоты числа $n$ по Ферма. С точки зрения производительности, тест Ферма хуже «наивного» теста.

Вероятность встретить «свидетеля непростоты» аналогична «наивному» тесту в худшем случае (для чисел $n$, являющихся числами Кармайкла), а скорость проверки одного свидетеля много меньше, чем у «наивного» теста.

16.6.5. Тест Миллера

Улучшение теста Ферма основано на следующем утверждении: для простого $p$ из сравнений

$$ a^2 \equiv 1 \mod p, $$
$$ (a-1)(a+1) \equiv 0 \mod p $$

следует одно из двух утверждений:

$$ \left[ \begin{array}{l} a \equiv 1 \mod p, \\ a \equiv -1 \mod p. \\ \end{array} \right. $$

Для того чтобы использовать это утверждение, представим чётное число $n - 1$ в виде произведения:

$$ n-1 = 2^s r, $$

где $s$ является натуральным числом, а $r$ – нечётным. Возьмём некоторое $a$, $1 < a < n$, и рассмотрим последовательность чисел (все вычисления делаются по модулю $n$)

equation a^r, a^2r, a^2^2 r, a^2^3 r, , a^2^s-1 r, a^2^s r = a^n-1 n.

Если число $n$ простое, то данная последовательность [eq:prime-check-miller-sequence] будет заканчиваться единицей. Причём в ряду [eq:prime-check-miller-sequence] перед единицей, если число $n$ простое, должно идти либо число $1$, либо $-1 \equiv n-1 \mod n$. Основываясь на этом свойстве, можно сформулировать определение свидетеля простоты.

Будем говорить, что число $a, 1 < a < n$, является свидетелем простоты числа $n$ по Миллеру, если ряд [eq:prime-check-miller-sequence] либо начинается с единицы, либо содержит число $n-1$ и заканчивается единицей.

Пример. Рассмотрим $n=4033$. Значение $s$ для $n$ равно $6$, то есть $n - 1 = 4032 = 63 \cdot 2^6$. То есть степени, в которые нужно будет возводить потенциальные свидетели простоты, равны:

$$ 63 \cdot 2^0, 63 \cdot 2^1, 63 \cdot 2^2, 63 \cdot 2^3, 63 \cdot 2^4, 63 \cdot 2^5, 63 \cdot 2^6= $$
$$ 63, 126, 252, 504, 1008, 2016, 4032. $$

Вычисление ряда [eq:prime-check-miller-sequence] делается не дольше, чем вычисление элемента $a^{n-1}$. Сначала вычисляем $a^{r}$, а все остальные элементы ряда получаем, возводя предыдущий элемент в квадрат.

В 1975 году Миллер (англ. Gary L. Miller, [74, 75]) показал, что если число $n$ является составным, и если верна расширенная гипотеза Римана

Гипотеза о распределении нулей дзета-функции Римана на комплексной плоскости.

, то между 2 и $O \left( \log^2 n \right)$ существует хотя бы одно число, не являющееся свидетелем простоты $n$. В 1985 году Эрик Бах (англ. Eric Bach, [7]) уменьшил границу до $2 \ln^2 n$. Что в результате приводит нас к тесту Миллера.

  1. Возьмём все целые (можно простые) числа от $2$ до $2 \ln^2 n$ и проверим, являются ли они свидетелями простоты числа $n$ по Миллеру.
  2. Если являются, то число $n$ является простым, иначе – составным.

Данный тест является недоказанным (основывается на недоказанной гипотезе Римана), детерминированным и полиномиальным, так как и проверка одного свидетеля, и общее число требуемых свидетелей являются полиномиальными функциями от длины $n$. Тем не менее, число проверок в тесте остаётся достаточно большим (для чисел размером в 2048 бит это составляет более 250 тыс. проверок).

16.6.6. Тест Миллера — Рабина

В 1980 году Рабин (англ. Michael O. Rabin, [86]) обратил внимание на то, что у нечётного составного числа $n$ количество свидетелей простоты $1 < a < n$ по Миллеру не превышает $n/4$. Это означает, что если число $1 < a < n$ является свидетелем простоты числа $n$ по Миллеру, то число $n$ является простым с вероятностью ошибки не более чем $1/4$. Что приводит нас к вероятностному тесту Миллера — Рабина.

Тест Миллера — Рабина состоит в проверке $t$ случайно выбранных чисел $1 < a < n$. Если для всех $t$ чисел $a$ тест пройден, то $n$ называется псевдопростым, и вероятность того, что число $n$ не простое, имеет оценку:

$$ P_{error} < \left( \frac{1}{4} \right)^t. $$

Если для какого-то числа $a$ тест не пройден, то число $n$ точно составное.

Описание теста приведено в алгоритме [miller-rabin].

algorithmht Вероятностный тест Миллера — Рабина проверки числа на простоту algorithmic Вход: нечётное $n>1$ для проверки на простоту и $t$ – параметр надёжности. Выход: Составное или Псевдопростое. $n - 1 = 2^s r, ~ r$ – нечётное. $j = 1$ to $t$ Выбрать случайное число $a \in [2, n-2]$. $(a_0 = a^r ~\neq~ \pm 1 \mod n)$ and $(\forall i \in [1, s-1] \rightarrow a_i = a_0^{2^i} ~\neq~ -1 \mod n)$ return Составное. return Псевдопростое с вероятностью ошибки $P_{error} < \left( \frac{1}{4} \right)^t$.

Сложность алгоритма Миллера — Рабина для $k$-битового числа $n$ имеет порядок

$$ O(t k^3) $$

двоичных операций, где $t$ – количество раундов.

Пример. Пример выполнения теста Миллера — Рабина для $n = 169, ~ n-1 = 21 \cdot 2^3$.

Выберем следующие числа в качестве возможных кандидатов в свидетели простоты числа $n$: 2, 19, 22, 23.

Степени, в которые нужно возводить $a$: 21, 42, 84, 168.

Согласно определению выше, числа 19, 22 и 23 являются свидетелями простоты числа $n=169$ по Миллеру. Если бы мы рассматривали только эти числа в качестве кандидатов в свидетели, то результатом работы алгоритма Миллера — Рабина был бы вывод, что число $n=169$ является псевдопростым с вероятностью ошибки $e = 1 / 4^3 = 0{,}015625 \approx 1{,}6$. Однако так как в результате проверки числа $a = 2$ было обнаружено, что оно не является свидетелем простоты, то результатом работы алгоритма является вывод, что число $n=169$ составное.

Тест Миллера — Рабина не основан на гипотезе Римана или других недоказанных утверждениях. Он является доказанным, полиномиальным, но вероятностным тестом простоты. Также он является наиболее используемым тестом простоты на сегодняшний день.

16.6.7. Тест AKS

Первый корректный, детерминированный и полиномиальный алгоритм проверки числа на простоту предложили Агравал, Каял и Саксена (англ. Manindra Agrawal, Neeraj Kayal, Nitin Saxena) в 2002 году [2]. Тест получил название AKS по фамилиям авторов. Сложность алгоритма для проверки $k$-битового числа равна

$$ O(k^{6}). $$

К сожалению, несмотря на полиномиальность сложности теста, алгоритм очень медленный и не может быть применён для чисел с большой битовой длиной (в сотни, тысячи бит).

Основой теста является аналог малой теоремы Ферма для многочленов. Пусть числа $a$ и $p>1$ взаимно простые. В этом случае $p$ – простое число тогда и только тогда, когда

equation (x - a)^p = x^p - a p.

Действительно, если $p$ – простое, то биномиальные коэффициенты $\binom{p}{i},\ i = 1, \dots, p-1$ в разложении левой части делятся на $p$, то есть $\binom{p}{i} = 0 \mod p$, а для последнего члена разложения $a^p$ выполняется $a^p = a \mod p$ по малой теореме Ферма. Следовательно, равенство верно.

Пусть число $p$ составное. Представим его в виде $p = A q^r$ с взаимно простыми $A$ и $q$ для некоторого простого $q$. Тогда коэффициент $\binom{p}{q}$ равен

$$\begin{eqnarray} \binom{p}{q} = \frac{(A q^r) (A q^r - 1)(A q^r - 2) \dots (A q^r - q + 1)}{q (q-1)(q-2) \cdots 1} = \\ = \frac{A q^r}{q} \cdot \frac{A q^r - 1}{q-1} \cdot \frac{A q^r - 2}{q-2} \cdot ~\cdots~ \cdot \frac{A q^r - q + 1}{1}. \end{eqnarray}$$

Первый множитель $A q^r$ в числителе делится на $q$, далее идут

$q-1$

последовательно убывающих чисел, которые не делятся на $q$. Значит, $\binom{p}{q}$ не делится на $A q^r$, $\binom{p}{q} \neq 0 \mod p$. Следовательно,

$$ (x - a)^p \neq x^p - a \mod p. $$

Непосредственная проверка равенства

eq:AKS1

является трудоёмкой из-за необходимости проверить все коэффициенты. Рассмотрим следующую модификацию теста, которая тоже имеет полиномиальную сложность. Пусть для некоторого числа $r \nmid n$ ($r$ не делит $n$) выполняется равенство

equation (x - a)^p = x^p - a (x^r-1, p).

Другими словами, пусть

$$ (x - a)^p - (x^p - a) = (x^r-1) \cdot f(x) + p \cdot g(x) $$

для некоторых многочленов $f(x)$ и $g(x)$. Тогда, либо $p$ – простое, либо $p^2 = 1 \mod r$.

Описание теста AKS приведено в алгоритме [alg:aks].

algorithm!ht Детерминированный полиномиальный тест AKS algorithmic Вход: число $n>1$ для проверки на простоту. Выход: Составное или Простое. $n = a^b, ~a, b \in {\mathbb{N}}, ~ b > 1$, для некоторых $a, b$ return Составное. Найти наименьшее $r \in {\mathbb{N}}$ с порядком $\ord_n(r) > \log_2^2 n$. Порядок числа $r$ по модулю $n$ определяется как минимальное число $ord_n(r) \in {\mathbb{N}}$: $r^{\ord_n(r)} = 1 \mod n$. $\gcd(a,n) \neq 1$ для некоторого $a \in {\mathbb{N}}, ~a < r$ return Составное. $a = 1$ to $2 \sqrt{r} \log_2 n$ $(x - a)^n ~\neq~ x^n - a \mod (x^r - 1, n)$ return Составное. return Простое