Тесты на простоту

Введение и базовые понятия

Тема проверки простоты числа важна и в теории чисел, и в прикладных задачах, таких как криптография или факторизация. Прежде чем говорить о самих тестах, напомним ключевые определения и свойства, которые лежат в основе методов проверки.

Простое число - натуральное число, больше единицы, которое имеет ровно два различных положительных делителя: 1 и само себя.

Составное число - натуральное число, которое имеет больше двух положительных делителей; другими словами, может быть представлено как произведение меньших натуральных чис.

Метод простого перебора (деление до корня)

Самый простой и интуитивный способ проверить простоту числа — попробовать поделить его на все натуральные делители до квадратного корня. Достаточно проверять делимость на числа не больше $\sqrt{n}$, потому что если у числа есть нетривиальный делитель, то найдётся пара делителей, и меньший из них не превосходит корня.

На практике перебор ведут не по всем целым числам, а только по простым делителям — это ускоряет процесс, но в худшем случае сложность остаётся порядка $O(\sqrt{n})$. Для небольших чисел и учебных задач такой метод абсолютно оправдан.

Тест Ферма и понятие псевдопростых чисел

Тест Ферма - проверка на основе малой теоремы Ферма, которая утверждает, что для простого числа p и любого целого a число удовлетворяет соотношению $a^{p-1}\equiv 1\pmod p$.

Используя эту теорему, можно сформулировать простой тест: выбрать базу a и проверить, выполняется ли $a^{n-1}\equiv 1\pmod n$. Если нет — число точно составное. Если да — число называется вероятно простым относительно основания a. Однако существуют составные числа, для которых это соотношение верно для многих оснований a; такие числа называются псевдопростыми по основанию a.

Псевдопростое число - составное число, которое проходит определённый тест простоты (например, тест Ферма) для данного основания a, т.е. не обнаруживает свою составность по этому критерию.

Числа Кармайкла и ограничения теста Ферма

Число Кармайкла - составное число, которое удовлетворяет равенству $a^{n-1}\equiv 1\pmod n$ для всех a, взаимно простых с этим числом. Такие числа маскируют свою составность для теста Ферма по всем основаниям, не делящим число.

Наличие чисел Кармайкла показывает, что тест Ферма нельзя считать надёжным в общем виде. Для практики тест Ферма полезен как быстрый фильтр: он может быстро отсеять многие составные числа, но не даёт абсолютной гарантии.

Тест Миллера—Рабина: идея и алгоритм

Тест Миллера—Рабина - вероятностный тест, улучшающий критерий Ферма за счёт проверки так называемого «сильного вероятного простого» состояния. Сначала представляют $n-1 = d\cdot 2^{s},\quad d\ \text{нечётное}$, где d нечётно и s — неотрицательно.

Затем для выбранного основания a вычисляют $a^{d}\bmod n$ и последовательность квадратичных поднятий $a^{d2^{r}}\bmod n$. Число считается «сильнопсевдопростым» по основанию a, если выполняется условие $a^{d}\equiv 1\pmod n\ \text{или}\ \exists r\ (0\le r<s):\ a^{d2^{r}}\equiv -1\pmod n$. Если условие не выполняется — число точно составное.

Миллера—Рабина гораздо реже ошибается, чем простая проверка по Ферму: вероятность того, что составное число пройдёт один раунд теста Миллера—Рабина, не превосходит $\le 1/4$, а если провести t независимых раундов, итоговая вероятность ошибки не превосходит $\le 4^{-t}$. Время работы теста при k раундах оценивается как примерно $O(k\log^{3} n)$ (где в оценках учтены операции быстрой модульной экспоненции).

Детерминированные варианты и современные методы

Хотя Миллер—Рабин вероятностен, для чисел в ограничённом диапазоне существуют конечные наборы оснований, которые делают его детерминированным. Для практических применений это означает, что для чисел до некоторого предела достаточно проверить фиксированный набор оснований, например $\{2,3,5,7,11\}$, чтобы получить точный ответ (пределы и наборы зависят от теорем и исследований).

Существуют и полностью детерминированные алгоритмы полиномиального времени, в частности алгоритм AKS, который доказал, что проверка простоты лежит в классе P: время работы выражается как полиномиальная функция от логарифма числа, символически это можно записать как $(\log n)^{O(1)}$. На практике алгоритмы, основанные на эллиптических кривых (ECPP) или улучшенные версии AKS и APR-CL, используются для доказательства простоты больших чисел.

Практические рекомендации и заключение

Какой тест выбрать в конкретной задаче? Для быстрых проверок и генерации кандидатов разумно комбинировать: сначала простые фильтры по кратным малым простым, затем несколько раундов Миллера—Рабина. Для критически важных приложений, где требуется доказательство корректности, используют детерминированные алгоритмы или ECPP.

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

В учебных задачах рекомендуется сначала освоить идею простого деления и теста Ферма, а затем перейти к тщательному разбору алгоритма Миллера—Рабина: его корректность, анализ ошибок и примеры работы. Это даст устойчивое понимание как теории, так и практики тестов на простоту.