Как математики ищут простые числа: решето Эратосфена и тесты Миллера — Рабина

Как устроено решето Эратосфена

Метод придумал древнегреческий математик Эратосфен Киренский, заведовавший в третьем веке до нашей эры Александрийской библиотекой. С тех пор схема почти не изменилась. Берётся список чисел от двух до нужного предела. Первое непомеченное число объявляется простым, а все его кратные вычёркиваются. Затем берётся следующее непомеченное число, снова объявляется простым, и вычёркиваются уже его кратные. Так продолжается до конца списка. Всё оставшееся невычеркнутым и составляет полный список простых чисел до заданного предела.

Пример на практике расставляет всё по местам. Запущенное в коде решето для чисел от двух до ста отдаёт такой список: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97. Двадцать пять простых чисел из девяноста девяти проверенных. Уже на этом небольшом отрезке видно главное свойство простых чисел — они встречаются всё реже по мере роста самих чисел, а между соседними простыми появляются всё более длинные промежутки из составных.

Почему хватает проверять делители только до корня

Наивный способ проверить одно число на простоту — перебрать все возможные делители от двух до самого числа без единицы. Для этого перебора такая полнота не нужна, и вот почему. Если число n составное, оно раскладывается на два множителя a и b, и хотя бы один из этих множителей не превышает квадратный корень из n — иначе произведение a на b получилось бы больше самого n. Значит, если среди чисел меньше корня из n не нашлось ни одного делителя, дальше проверять бессмысленно: делителя больше корня без делителя-пары меньше корня не бывает.

На конкретных числах это правило проверяется быстро. Для девяноста семи квадратный корень равен девяти с небольшим, целая часть — девять, поэтому достаточно перебрать делители от двух до девяти. Ни один из них не делит девяносто семь без остатка, значит число простое. Для девяноста одного та же самая проверка почти сразу находит делитель семь, и продолжать нет смысла — девяносто один составное, оно раскладывается на семь и тринадцать. Перебор до самого числа никакой дополнительной пользы не даёт. Перебор до корня даёт ровно столько проверок, сколько нужно для верного ответа.

Сколько работы делает решето при росте предела

Решето вычёркивает числа не по разу на каждое простое — большинство составных чисел получает несколько вычёркиваний подряд, потому что делится сразу на несколько уже найденных простых. Прямой подсчёт операций вычёркивания при разных пределах в коде показывает рост нагрузки: для предела сто их сто четыре, для тысячи — тысяча четыреста одиннадцать, для ста тысяч — почти двести тысяч, для миллиона — свыше двух миллионов. Количество самих найденных простых чисел при этом растёт заметно медленнее: до ста их двадцать пять, до тысячи — сто шестьдесят восемь, до ста тысяч — девять тысяч пятьсот девяносто два, до миллиона — семьдесят восемь тысяч четыреста девяносто восемь.

Формально сложность решета записывают как n, умноженное на логарифм от логарифма n, и это один из самых быстрых известных способов найти сразу все простые числа в диапазоне. Логарифм от логарифма растёт настолько медленно, что для практических целей его можно считать почти постоянным числом. Даже для предела в миллион он равен всего двум с половиной, а для предела в миллиард поднимается лишь до трёх. Эта особенность и делает решето Эратосфена таким эффективным для перебора целого диапазона.

Когда решето уже не подходит

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

Идея теста Миллера-Рабина

Для проверки отдельного большого числа математики применяют особые арифметические свойства простых чисел вместо перебора делителей — эти свойства проверяются заметно быстрее. В основе лежит малая теорема Ферма. Если число p простое, то для любого числа a, не делящегося на p, остаток от деления a в степени p минус один на p всегда равен единице. Проверку этого равенства для одного-двух оснований a называют тестом Ферма, и работает она быстро — но у неё есть слабое место. Находятся составные числа, которые обманывают этот тест сразу для многих оснований подряд.

Тест Миллера-Рабина устроен хитрее. Он проверяет то же равенство, но по ходу вычисления степени дополнительно смотрит на промежуточные значения корня из единицы по выбранному модулю. Если промежуточное значение ведёт себя не так, как обязано вести себя у простого числа, алгоритм сразу объявляет число составным, даже если сам финальный тест Ферма для этого основания оказался бы пройден. Такую найденную несостыковку называют свидетелем составности.

Живой пример на числе, которое обманывает более простой тест

Разница между обычным тестом Ферма и тестом Миллера-Рабина хорошо видна на числе пятьсот шестьдесят один. Оно раскладывается на три множителя — три, одиннадцать и семнадцать, то есть заведомо составное. Прямой запуск в коде показал: тест Ферма с основаниями два, пять и семь ошибается на этом числе во всех трёх случаях и отвечает «вероятно простое». Пятьсот шестьдесят один принадлежит к особому классу чисел Кармайкла, которые обманывают тест Ферма почти для любого основания. Тест Миллера-Рабина на тех же трёх основаниях в каждом случае находит свидетеля составности и правильно определяет число как составное.

Именно числа Кармайкла и делают тест Миллера-Рабина предпочтительным на практике. Проверка на двух тысячах случайных нечётных чисел в диапазоне от тысячи до миллиона с пятью основаниями подряд — два, три, пять, семь и одиннадцать — не дала ни одной ошибки: все составные числа распознаны как составные, все простые прошли проверку. Чем больше оснований используется, тем ниже шанс, что случайно выбранное составное число обманет тест сразу по всем из них. Поэтому тест называют вероятностным. Стопроцентной гарантии простоты он не даёт, зато снижает вероятность ошибки до пренебрежимо малой величины.

Зачем нужны такие большие простые числа

Большие простые числа лежат в основе алгоритма шифрования RSA и похожих на него схем защиты данных. Перемножить два больших простых числа для компьютера — задача лёгкая, счёт занимает доли секунды. Разложить обратно на множители готовое произведение двух неизвестных огромных простых чисел — задача, на которую даже мощным вычислительным кластерам нужны годы, а для чисел подходящей длины и столетия. Эта асимметрия защищает переписку, банковские операции и пароли пользователей. Чтобы создать ключ шифрования, компьютер сначала перебирает случайные числа нужной длины и проверяет каждое тестом вроде Миллера-Рабина, пока не найдёт то, которое действительно оказывается простым.

1. взять список чисел от двух до нужного предела
2. первое непомеченное число объявить простым
3. вычеркнуть все его кратные, начиная с квадрата этого числа
4. перейти к следующему непомеченному числу и повторить вычёркивание
5. остановиться, когда очередное непомеченное число превысило корень из предела — всё оставшееся уже гарантированно простое