- PVSM.RU - https://www.pvsm.ru -

Алгоритмы поиска простых чисел

Алгоритмы поиска простых чисел - 1«Самое большое простое число 232582657-1. И я с гордостью утверждаю, что запомнил все его цифры… в двоичной форме».
Карл Померанс [1]

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

Решето Эратосфена

Решето Эратосфена [2] — алгоритм, предложенный древнегреческим математиком Эратосфеном. Этот метод позволяет найти все простые числа меньше заданного числа n. Суть метода заключается в следующем. Возьмем набор чисел от 2 до n. Вычеркнем из набора (отсеим) все числа делящиеся на 2, кроме 2. Перейдем к следующему «не отсеянному» числу — 3, снова вычеркиваем все что делится на 3. Переходим к следующему оставшемуся числу — 5 и так далее до тех пор пока мы не дойдем до n. После выполнения вышеописанных действий, в изначальном списке останутся только простые числа.

Алгоритм можно несколько оптимизировать. Так как один из делителей составного числа n обязательно $leqslant sqrt{n}$, алгоритм можно останавливать, после вычеркивания чисел делящихся на $sqrt{n}$.

Иллюстрация работы алгоритма из Википедии:

image

Сложность алгоритма составляет $O(n loglog n)$, при этом, для хранения информации о том, какие числа были вычеркнуты требуется $O(n)$ памяти.

Существует ряд оптимизаций, позволяющих снизить эти показатели. Прием под названием wheel factorization [3] состоит в том, чтобы включать в изначальный список только числа взаимно простые [4] с несколькими первыми простыми числами (например меньше 30). В теории предлагается брать первые простые примерно до $sqrt{log n}$. Это позволяет снизить сложность алгоритма в $loglog n$ раз. Помимо этого для уменьшения потребляемой памяти используется так называемое сегментирование. Изначальный набор чисел делится на сегменты размером $leqslant sqrt{n}$ и для каждого сегмента решето Эратосфена применяется по отдельности. Потребление памяти снижается до $O(sqrt{n})$.

Решето Аткина

Более совершенный алгоритм отсеивания составных чисел был предложен Аткином и Берштайном и получил название Решето Аткина [5]. Этот способ основан на следующих трех свойствах простых чисел.

Свойство 1

Если n — положительное число, не кратное квадрату простого числа и такое, что $n equiv 1(mod 4)$. То n — простое, тогда и только тогда, когда число корней уравнения $4x^2+y^2=n$ нечетно.

Свойство 2

Если n — положительное число, не кратное квадрату простого числа и такое, что $n equiv 1(mod 6)$. То n — простое, тогда и только тогда, когда число корней уравнения $3x^2+y^2=n$ нечетно.

Свойство 3

Если n — положительное число, не кратное квадрату простого числа и такое, что $n equiv 11(mod 12)$. То n — простое, тогда и только тогда, когда число корней уравнения $3x^2-y^2=n$ нечетно.

Доказательства этих свойств приводятся в этой статье [6].

На начальном этапе алгоритма решето Аткина представляет собой массив A размером n, заполненный нулями. Для определения простых чисел перебираются все $x, y < sqrt n$. Для каждой такой пары вычисляется $4x^2+y^2$, $3x^2+y^2$, $3x^2-y^2$ и значение элементов массива $A[4x^2+y^2]$, $A[3x^2+y^2]$, $A[3x^2-y^2]$ увеличивается на единицу. В конце работы алгоритма индексы всех элементов массива, которые имеют нечетные значения либо простые числа, либо квадраты простого числа. На последнем шаге алгоритма производится вычеркивание квадратов оставшихся в наборе чисел.

Из описания алгоритма следует, что вычислительная сложность решета Аткина и потребление памяти составляют $O(n)$. При использовании wheel factorization и сегментирования оценка сложности алгоритма снижается до $O(n / loglog n)$, а потребление памяти до $O(sqrt{n})$.

Числа Мерсенна и тест Люка-Лемера

Конечно при таких показателях сложности, даже оптимизированное решето Аткина невозможно использовать для поиска по-настоящему больших простых чисел. К счастью, существуют быстрые тесты, позволяющие проверить является ли заданное число простым. В отличие от алгоритмов решета, такие тесты не предназначены для поиска всех простых чисел, они лишь способны сказать с некоторой вероятностью, является ли определенное число простым.

Один из таких методов проверки — тест Люка-Лемера [7]. Это детерминированный и безусловный тест простоты. Это означает, что прохождение теста гарантирует простоту числа. К сожалению, тест предназначен только для чисел особого вида $2^p-1$, где p — натуральное число. Такие числа называются числами Мерсенна.

Тест Люка-Лемера утверждает, что число Мерсенна $M_p=2^p-1$ простое тогда и только тогда, когда p — простое и $M_p$ делит нацело $(p-1)$-й член последовательности $S_k$ задаваемой рекуррентно: $S_1=4, S_k=S_{k-1}^2-2$ для $k > 1$.

Для числа $M_p$ длиной p бит вычислительная сложность алгоритма составляет ${displaystyle O(p^{3})}$.

Благодаря простоте и детерминированности теста, самые большие известные простые числа — числа Мерсенна. Самое большое известное простое число на сегодня — $2^{82,589,933}-1$, его десятичная запись состоит из 24,862,048 цифр. Полюбоваться на эту красоту можно здесь [8].

Теорема Ферма и тест Миллера-Рабина

Простых чисел Мерсенна известно не очень много, поэтому для криптографии с открытым ключом необходим другой способ поиска простых чисел. Одним из таким способов является тест простоты Ферма [9]. Он основан на малой теореме Ферма, которая гласит, что если n — простое число, то для любого a, которое не делится на n, выполняется равенство $a^{n-1}equiv 1{pmod {n}}$. Доказательство теоремы можно найти на Википедии [10].

Тест простоты Ферма — вероятностный тест, который заключается в переборе нескольких значений a, если хотя бы для одного из них выполняется неравенство $a^{n-1} notequiv 1 pmod n$, то число n — составное. В противном случае, n — вероятно простое. Чем больше значений a использовано в тесте, тем выше вероятность того, что n — простое.

К сожалению, существуют такие составные числа n, для которых сравнение $a^{n-1}equiv 1{pmod {n}}$ выполняется для всех a взаимно простых с n. Такие числа называются числам Кармайкла [11]. Составные числа, которые успешно проходят тест Ферма, называются псевдопростыми Ферма. Количество псевдопростых Ферма бесконечно, поэтому тест Ферма — не самый надежный способ определения простых чисел.

Тест Миллера-Рабина

Более надежных результатов можно добиться комбинируя малую теорему Ферма и тот факт, что для простого числа p не существует других корней уравнения $x^2 equiv 1 pmod p$, кроме 1 и -1. Тест Миллера-Рабина перебирает несколько значений a и проверяет выполнение следующих условий.

Пусть p — простое число и $p-1=2^sd$, тогда для любого a справедливо хотя бы одно из условий:

  1. $a^{d}equiv pm1{pmod {p}}$
  2. Существует целое число r < s такое, что $a^{2^{r}d}equiv -1{pmod {p}}$

По теореме Ферма $a^{p-1}equiv1pmod p$, а так как $p-1=2^sd$ из свойства о корнях уравнения $x^2 equiv 1 pmod p$ следует что если мы найдем такое a, для которого одно из условий не выполняется, значит p — составное число. Если одно из условий выполняется, число a называют свидетелем простоты числа n по Миллеру, а само число n — вероятно простым.

Чем больше свидетелей простоты найдено, тем выше вероятность того, что n — простое. Согласно теореме Рабина вероятность того, что случайно выбранное число a окажется свидетелем простоты составного числа составляет приблизительно $1/4$.

Следовательно, если проверить k случайных чисел a, то вероятность принять составное число за простое $approx(1/4)^k$.

Сложность работы алгоритма $O(klog^3p)$, где k — количество проверок.

Благодаря быстроте и высокой точности тест Миллера-Рабина широко используется при поиске простых чисел. Многие современные криптографические библиотеки при проверке больших чисел на простоту используют только этот тест и, как показал Мартин Альбрехт в своей работе [12], этого не всегда оказывается достаточно.

Он смог сгенерировать такие составные числа, которые успершно прошли тест на простоту в библиотеках OpenSSL, CryptLib, JavaScript Big Number и многих других.

Тест Люка и Тест Baillie–PSW

Чтобы избежать уязвимости, связанные с ситуациями, когда сгенерированное злоумышленником составное число, выдается за простое, Мартин Альбрехт предлагает использовать тест Baillie–PSW [13]. Несмотря на то, что тест Baillie–PSW является вероятностным, на сегодняшний день не найдено ни одно составное число, которое успешно проходит этот тест. За нахождение подобного числа в 1980 году авторы алгоритма пообещали вознаграждение в размере $30. Приз пока так и не был востребован.

Ряд исследователей проверили [14]все числа до $2^{64}$ и не обнаружили ни одного составного числа, прошедшего тест Baillie–PSW. Поэтому, для чисел меньше $2^{64}$ тест считается детерминированным.

Суть теста сводится к последовательной проверке числа на простоу двумя различными методами. Один из этих методов уже описанный выше тест Миллера-Рабина. Второй — тест Люка на сильную псевдопростоту [15].

Тест Люка на сильную псевдопростоту

Последовательности Люка [16] — пары рекуррентных последовательностей ${U_{n}(P,Q)}, {V_{n}(P,Q)}$, описываемые выражениями:

${displaystyle U_{0}(P,Q)=0,quad U_{1}(P,Q)=1,quad U_{n+2}(P,Q)=Pcdot U_{n+1}(P,Q)-Qcdot U_{n}(P,Q),,ngeq 0}$

${displaystyle V_{0}(P,Q)=2,quad V_{1}(P,Q)=P,quad V_{n+2}(P,Q)=Pcdot V_{n+1}(P,Q)-Qcdot V_{n}(P,Q),,ngeq 0}$

Пусть $U_n(P,Q)$ и $V_n(P,Q)$ — последовательности Люка, где целые числа P и Q удовлетворяют условию ${displaystyle D=P^{2}-4Qneq 0}$

Вычислим символ Якоби [17]: $left({frac {D}{p}}right)=varepsilon$.

Найдем такие r, s для которых выполняется равенство $n-ε=2^rs$

Для простого числа n выполняется одно из следующих условий:

  1. n делит $U_s$
  2. n делит $V_{2^js}$ для некоторого j < r

В противном случае n — составное.

Вероятность того, что составное число n успешно пройдет тест Люка для заданной пары параметров P, Q не превышает 4/15. Следовательно, после применения теста k раз, эта вероятность составляет $(4/15)^k$.

Тесты Миллера-Рабина и Люка производят не пересекающиеся множества псевдопростых чисел, соответственно если число p прошло оба теста, оно простое. Именно на этом свойстве основывается тест Baillie–PSW.

Заключение

В зависимости от поставленной задачи, могут использоваться различные методы поиска простых чисел. К примеру, при поиске больших простых чисел Мерсенна, сперва, при помощи решета Эратосфена или Аткина определяется список простых чисел до некоторой границы, предположим, до $10^8$. Затем для каждого числа p из списка, с помощью теста Люка-Лемера, на простоту проверяется $M_p=2^p-1$.

Чтобы сгенерировать большое простое число в криптографических целях, выбирается случайное число a и проверяется тестом Миллера-Рабина или более надежным Baillie–PSW. Согласно теореме о распределении простых чисел [18], у случайно выбранного числа от 1 до n шанс оказаться простым примерно равен ${frac {1}{ln n}}$. Следовательно, чтобы найти простое число размером 1024 бита, достаточно перебрать около тысячи вариантов.

P.S. Исходники

Реализацию всех описанных алгоритмов на Go можно посмотреть на GitHub [19].

Автор: Алексей

Источник [20]


Сайт-источник PVSM.RU: https://www.pvsm.ru

Путь до страницы источника: https://www.pvsm.ru/algoritmy/331630

Ссылки в тексте:

[1] Карл Померанс: https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%BC%D0%B5%D1%80%D0%B0%D0%BD%D1%81,_%D0%9A%D0%B0%D1%80%D0%BB

[2] Решето Эратосфена: https://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D1%88%D0%B5%D1%82%D0%BE_%D0%AD%D1%80%D0%B0%D1%82%D0%BE%D1%81%D1%84%D0%B5%D0%BD%D0%B0

[3] wheel factorization: https://en.wikipedia.org/wiki/Wheel_factorization

[4] взаимно простые: https://ru.wikipedia.org/wiki/%D0%92%D0%B7%D0%B0%D0%B8%D0%BC%D0%BD%D0%BE_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D1%8B%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%B0

[5] Решето Аткина: https://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D1%88%D0%B5%D1%82%D0%BE_%D0%90%D1%82%D0%BA%D0%B8%D0%BD%D0%B0

[6] этой статье: http://cr.yp.to/papers/primesieves-19990826.pdf

[7] тест Люка-Лемера: https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D1%81%D1%82_%D0%9B%D1%8E%D0%BA%D0%B0_%E2%80%94_%D0%9B%D0%B5%D0%BC%D0%B5%D1%80%D0%B0

[8] здесь: https://www.mersenne.org/primes/

[9] тест простоты Ферма: https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D1%81%D1%82_%D0%A4%D0%B5%D1%80%D0%BC%D0%B0

[10] Википедии: https://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D0%BB%D0%B0%D1%8F_%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%A4%D0%B5%D1%80%D0%BC%D0%B0

[11] числам Кармайкла: https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%BE_%D0%9A%D0%B0%D1%80%D0%BC%D0%B0%D0%B9%D0%BA%D0%BB%D0%B0

[12] работе : https://eprint.iacr.org/2018/749.pdf

[13] Baillie–PSW: https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D1%81%D1%82_%D0%91%D0%B5%D0%B9%D0%BB%D0%B8_%E2%80%94_%D0%9F%D0%BE%D0%BC%D0%B5%D1%80%D0%B0%D0%BD%D1%86%D0%B0_%E2%80%94_%D0%A1%D0%B5%D0%BB%D1%84%D1%80%D0%B8%D0%B4%D0%B6%D0%B0_%E2%80%94_%D0%A3%D0%BE%D0%B3%D1%81%D1%82%D0%B0%D1%84%D1%84%D0%B0

[14] проверили : http://www.trnicely.net/misc/bpsw.html

[15] тест Люка на сильную псевдопростоту: https://ru.wikipedia.org/wiki/%D0%9F%D1%81%D0%B5%D0%B2%D0%B4%D0%BE%D0%BF%D1%80%D0%BE%D1%81%D1%82%D0%BE%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%BE_%D0%9B%D1%8E%D0%BA%D0%B0

[16] Последовательности Люка: https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D0%9B%D1%8E%D0%BA%D0%B0

[17] символ Якоби: https://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D0%BC%D0%B2%D0%BE%D0%BB_%D0%AF%D0%BA%D0%BE%D0%B1%D0%B8

[18] теореме о распределении простых чисел: https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%BE_%D1%80%D0%B0%D1%81%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D0%B8_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D1%8B%D1%85_%D1%87%D0%B8%D1%81%D0%B5%D0%BB

[19] GitHub: https://github.com/NeverWalkAloner/primes

[20] Источник: https://habr.com/ru/post/468833/?utm_source=habrahabr&utm_medium=rss&utm_campaign=468833