- PVSM.RU - https://www.pvsm.ru -
«Самое большое простое число 232582657-1. И я с гордостью утверждаю, что запомнил все его цифры… в двоичной форме».
Карл Померанс [1]
Число называется простым, если оно имеет только два различных делителя: единицу и само себя. Задача поиска простых чисел не дает покоя математикам уже очень давно. Долгое время прямого практического применения эта проблема не имела, но все изменилось с появлением криптографии с открытым ключом. В этой заметке рассматривается несколько способов поиска простых чисел, как представляющих исключительно академический интерес, так и применяемых сегодня в криптографии.
Решето Эратосфена [2] — алгоритм, предложенный древнегреческим математиком Эратосфеном. Этот метод позволяет найти все простые числа меньше заданного числа n. Суть метода заключается в следующем. Возьмем набор чисел от 2 до n. Вычеркнем из набора (отсеим) все числа делящиеся на 2, кроме 2. Перейдем к следующему «не отсеянному» числу — 3, снова вычеркиваем все что делится на 3. Переходим к следующему оставшемуся числу — 5 и так далее до тех пор пока мы не дойдем до n. После выполнения вышеописанных действий, в изначальном списке останутся только простые числа.
Алгоритм можно несколько оптимизировать. Так как один из делителей составного числа n обязательно , алгоритм можно останавливать, после вычеркивания чисел делящихся на .
Иллюстрация работы алгоритма из Википедии:
Сложность алгоритма составляет , при этом, для хранения информации о том, какие числа были вычеркнуты требуется памяти.
Существует ряд оптимизаций, позволяющих снизить эти показатели. Прием под названием wheel factorization [3] состоит в том, чтобы включать в изначальный список только числа взаимно простые [4] с несколькими первыми простыми числами (например меньше 30). В теории предлагается брать первые простые примерно до . Это позволяет снизить сложность алгоритма в раз. Помимо этого для уменьшения потребляемой памяти используется так называемое сегментирование. Изначальный набор чисел делится на сегменты размером и для каждого сегмента решето Эратосфена применяется по отдельности. Потребление памяти снижается до .
Более совершенный алгоритм отсеивания составных чисел был предложен Аткином и Берштайном и получил название Решето Аткина [5]. Этот способ основан на следующих трех свойствах простых чисел.
Свойство 1
Если n — положительное число, не кратное квадрату простого числа и такое, что . То n — простое, тогда и только тогда, когда число корней уравнения нечетно.
Свойство 2
Если n — положительное число, не кратное квадрату простого числа и такое, что . То n — простое, тогда и только тогда, когда число корней уравнения нечетно.
Свойство 3
Если n — положительное число, не кратное квадрату простого числа и такое, что . То n — простое, тогда и только тогда, когда число корней уравнения нечетно.
Доказательства этих свойств приводятся в этой статье [6].
На начальном этапе алгоритма решето Аткина представляет собой массив A размером n, заполненный нулями. Для определения простых чисел перебираются все . Для каждой такой пары вычисляется , , и значение элементов массива , , увеличивается на единицу. В конце работы алгоритма индексы всех элементов массива, которые имеют нечетные значения либо простые числа, либо квадраты простого числа. На последнем шаге алгоритма производится вычеркивание квадратов оставшихся в наборе чисел.
Из описания алгоритма следует, что вычислительная сложность решета Аткина и потребление памяти составляют . При использовании wheel factorization и сегментирования оценка сложности алгоритма снижается до , а потребление памяти до .
Конечно при таких показателях сложности, даже оптимизированное решето Аткина невозможно использовать для поиска по-настоящему больших простых чисел. К счастью, существуют быстрые тесты, позволяющие проверить является ли заданное число простым. В отличие от алгоритмов решета, такие тесты не предназначены для поиска всех простых чисел, они лишь способны сказать с некоторой вероятностью, является ли определенное число простым.
Один из таких методов проверки — тест Люка-Лемера [7]. Это детерминированный и безусловный тест простоты. Это означает, что прохождение теста гарантирует простоту числа. К сожалению, тест предназначен только для чисел особого вида , где p — натуральное число. Такие числа называются числами Мерсенна.
Тест Люка-Лемера утверждает, что число Мерсенна простое тогда и только тогда, когда p — простое и делит нацело -й член последовательности задаваемой рекуррентно: для .
Для числа длиной p бит вычислительная сложность алгоритма составляет .
Благодаря простоте и детерминированности теста, самые большие известные простые числа — числа Мерсенна. Самое большое известное простое число на сегодня — , его десятичная запись состоит из 24,862,048 цифр. Полюбоваться на эту красоту можно здесь [8].
Простых чисел Мерсенна известно не очень много, поэтому для криптографии с открытым ключом необходим другой способ поиска простых чисел. Одним из таким способов является тест простоты Ферма [9]. Он основан на малой теореме Ферма, которая гласит, что если n — простое число, то для любого a, которое не делится на n, выполняется равенство . Доказательство теоремы можно найти на Википедии [10].
Тест простоты Ферма — вероятностный тест, который заключается в переборе нескольких значений a, если хотя бы для одного из них выполняется неравенство , то число n — составное. В противном случае, n — вероятно простое. Чем больше значений a использовано в тесте, тем выше вероятность того, что n — простое.
К сожалению, существуют такие составные числа n, для которых сравнение выполняется для всех a взаимно простых с n. Такие числа называются числам Кармайкла [11]. Составные числа, которые успешно проходят тест Ферма, называются псевдопростыми Ферма. Количество псевдопростых Ферма бесконечно, поэтому тест Ферма — не самый надежный способ определения простых чисел.
Тест Миллера-Рабина
Более надежных результатов можно добиться комбинируя малую теорему Ферма и тот факт, что для простого числа p не существует других корней уравнения , кроме 1 и -1. Тест Миллера-Рабина перебирает несколько значений a и проверяет выполнение следующих условий.
Пусть p — простое число и , тогда для любого a справедливо хотя бы одно из условий:
По теореме Ферма , а так как из свойства о корнях уравнения следует что если мы найдем такое a, для которого одно из условий не выполняется, значит p — составное число. Если одно из условий выполняется, число a называют свидетелем простоты числа n по Миллеру, а само число n — вероятно простым.
Чем больше свидетелей простоты найдено, тем выше вероятность того, что n — простое. Согласно теореме Рабина вероятность того, что случайно выбранное число a окажется свидетелем простоты составного числа составляет приблизительно .
Следовательно, если проверить k случайных чисел a, то вероятность принять составное число за простое .
Сложность работы алгоритма , где k — количество проверок.
Благодаря быстроте и высокой точности тест Миллера-Рабина широко используется при поиске простых чисел. Многие современные криптографические библиотеки при проверке больших чисел на простоту используют только этот тест и, как показал Мартин Альбрехт в своей работе [12], этого не всегда оказывается достаточно.
Он смог сгенерировать такие составные числа, которые успершно прошли тест на простоту в библиотеках OpenSSL, CryptLib, JavaScript Big Number и многих других.
Чтобы избежать уязвимости, связанные с ситуациями, когда сгенерированное злоумышленником составное число, выдается за простое, Мартин Альбрехт предлагает использовать тест Baillie–PSW [13]. Несмотря на то, что тест Baillie–PSW является вероятностным, на сегодняшний день не найдено ни одно составное число, которое успешно проходит этот тест. За нахождение подобного числа в 1980 году авторы алгоритма пообещали вознаграждение в размере $30. Приз пока так и не был востребован.
Ряд исследователей проверили [14]все числа до и не обнаружили ни одного составного числа, прошедшего тест Baillie–PSW. Поэтому, для чисел меньше тест считается детерминированным.
Суть теста сводится к последовательной проверке числа на простоу двумя различными методами. Один из этих методов уже описанный выше тест Миллера-Рабина. Второй — тест Люка на сильную псевдопростоту [15].
Тест Люка на сильную псевдопростоту
Последовательности Люка [16] — пары рекуррентных последовательностей , описываемые выражениями:
Пусть и — последовательности Люка, где целые числа P и Q удовлетворяют условию
Вычислим символ Якоби [17]: .
Найдем такие r, s для которых выполняется равенство
Для простого числа n выполняется одно из следующих условий:
В противном случае n — составное.
Вероятность того, что составное число n успешно пройдет тест Люка для заданной пары параметров P, Q не превышает 4/15. Следовательно, после применения теста k раз, эта вероятность составляет .
Тесты Миллера-Рабина и Люка производят не пересекающиеся множества псевдопростых чисел, соответственно если число p прошло оба теста, оно простое. Именно на этом свойстве основывается тест Baillie–PSW.
В зависимости от поставленной задачи, могут использоваться различные методы поиска простых чисел. К примеру, при поиске больших простых чисел Мерсенна, сперва, при помощи решета Эратосфена или Аткина определяется список простых чисел до некоторой границы, предположим, до . Затем для каждого числа p из списка, с помощью теста Люка-Лемера, на простоту проверяется .
Чтобы сгенерировать большое простое число в криптографических целях, выбирается случайное число a и проверяется тестом Миллера-Рабина или более надежным Baillie–PSW. Согласно теореме о распределении простых чисел [18], у случайно выбранного числа от 1 до n шанс оказаться простым примерно равен . Следовательно, чтобы найти простое число размером 1024 бита, достаточно перебрать около тысячи вариантов.
Реализацию всех описанных алгоритмов на 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
Нажмите здесь для печати.