Как проверить число на простоту: перебор и тест Ферма

Дано: число $n = 1729$. Найти: простое оно или составное.

Метод состоит из двух частей: перебор делителей до $\sqrt{n}$ по простым кандидатам из решета Эратосфена и контрольный тест Ферма по основанию 2. Ответ: 1729 составное, оно делится на 7, и перебор обрывается на четвёртой проверке. Тест Ферма при этом даёт остаток 1 и объявляет число вероятно простым, то есть ошибается. Калькулятор сверху проходит обе процедуры для любого числа до миллиарда.

Решение по шагам

Дано. $n = 1729$. Найти: вердикт «простое или составное» с обоснованием.

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

$$\sqrt{1729} \approx 41{,}58 \quad \Rightarrow \quad d \leqslant 41.$$

Шаг 2. Готовим список кандидатов. Составные делители проверять незачем: если бы 1729 делилось на 9, оно делилось бы и на 3. Поэтому в кандидаты идут только простые числа до 41:

$$2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29,\ 31,\ 37,\ 41.$$

Их 13 против 40 чисел подряд от 2 до 41 и против 863 при наивном переборе до половины числа. Откуда берётся такой список, разобрано ниже в разделе про решето.

Шаг 3. Перебираем кандидатов по порядку.

• 1729 нечётное, значит на 2 не делится.
• Сумма цифр $1 + 7 + 2 + 9 = 19$ на 3 не делится, значит и само число не делится.
• Последняя цифра 9, признак делимости на 5 не выполнен.
• $1729 : 7 = 247$ без остатка.

Шаг 4. Останавливаемся. Делитель найден на четвёртой проверке из тринадцати возможных. Продолжать перебор не нужно: одного нетривиального делителя достаточно, чтобы вердикт был вынесен. Полное разложение $1729 = 7 \cdot 13 \cdot 19$ получается, если довести деление до конца, но это уже другая задача, она разобрана в разборе разложения числа на простые множители.

Шаг 5. Проверяем тестом Ферма. Считаем $2^{1728} \bmod 1729$ и получаем 1, то есть тест признаёт число вероятно простым. Это прямое противоречие с шагом 3, и разбирается оно в предпоследнем разделе: тест Ферма умеет уверенно доказывать только составность, а обратный вывод у него ненадёжен.

Ответ: число 1729 составное, его наименьший простой делитель равен 7; перебор выносит вердикт за 4 проверки делимости, а тест Ферма по основанию 2 на этом числе ошибается.

Формула: почему хватает делителей до корня

Пусть $n$ составное, то есть $n = a \cdot b$, где оба множителя больше единицы. Предположим, что оба они больше корня: $a > \sqrt{n}$ и $b > \sqrt{n}$. Тогда

$$a \cdot b > \sqrt{n} \cdot \sqrt{n} = n,$$

что противоречит равенству $a \cdot b = n$. Значит, хотя бы один множитель не превосходит $\sqrt{n}$, и именно его находит перебор.

Отсюда рабочее правило: перебор кандидатов $d$ идёт, пока выполняется $d^2 \leqslant n$. Такая запись удобнее сравнения с корнем, потому что не требует вычисления корня и работает без округлений. Граница включает сам корень: у полного квадрата $1849 = 43^2$ единственный делитель до корня равен как раз 43, и если оборвать перебор на 42, число будет ошибочно объявлено простым.

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

Решето Эратосфена: откуда берётся список кандидатов

Кандидатов удобно получать не пробным делением каждого числа, а сразу списком. Решето Эратосфена работает так: выписываем числа от 2 до выбранной границы, берём первое невычеркнутое число, объявляем его простым и вычёркиваем все его кратные. Начинать вычёркивание можно с квадрата: меньшие кратные уже вычеркнуты предыдущими шагами.

Решето до 100 останавливается после семёрки: следующее простое 11 дало бы первое вычёркивание с числа $121 > 100$. Остаётся 25 простых чисел, и первые тринадцать из них как раз покрывают проверку числа 1729. Переключи график калькулятора на режим решета, чтобы увидеть, как быстро падает число кандидатов на первых шагах.

Решето выгодно, когда проверять надо не одно число, а много: список простых строится один раз и переиспользуется. Для чисел до миллиарда хватает решета до $\sqrt{10^9} \approx 31\,623$, в нём около 3400 простых, и такой массив спокойно помещается в память. Дальше решето перестаёт масштабироваться: для чисел из сотен цифр корень тоже астрономический, и перебор становится безнадёжным.

Тест Ферма и его псевдопростые

Малая теорема Ферма утверждает: если $p$ простое и $a$ не делится на $p$, то

$$a^{p-1} \equiv 1 \pmod{p}.$$

Тест использует обратное по контрапозиции: если для какого-то основания $a$ остаток отличается от единицы, число точно составное. Считать степень напрямую не нужно, работает быстрое возведение с последовательным возведением в квадрат, разобранное в задаче про степень по модулю. Показатель раскладывается по двоичной записи: $1728 = 1024 + 512 + 128 + 64$.

Перемножаем нужные остатки: $1563 \cdot 256 \equiv 729$, затем $729 \cdot 802 \equiv 256$ и $256 \cdot 1290 \equiv 1 \pmod{1729}$. Тест пройден, хотя число составное. Такие числа называют псевдопростыми по данному основанию, а 1729 хуже того: у него все 22 взаимно простых основания в диапазоне от 2 до 30 дают единицу. Числа с таким свойством называются числами Кармайкла, наименьшее из них 561, и увеличение числа проверяемых оснований против них не помогает.

Выдают такие числа только основания, имеющие с ними общий делитель: при $a = 7$ остаток равен 742. Но подбор такого основания равносилен угадыванию делителя, поэтому на практике берут более сильный тест Миллера и Рабина. Он смотрит не только конечный остаток, но и промежуточные квадраты: для 1729 цепочка даёт $2^{27} \equiv 645$, затем 1065, затем 1. Единица получена из 1065, а это нетривиальный квадратный корень из единицы, которого у простого модуля быть не может. Более того, наибольший общий делитель чисел 1064 и 1729 равен 133, то есть тест попутно выдаёт делитель. Существует и точный критерий простоты через факториал, теорема Вильсона, но считать $(n-1)!$ дороже, чем перебирать делители, поэтому в расчётах его не применяют.

Простота числа - это ещё и условие разрешимости многих уравнений в целых числах: НОД взаимно простых чисел равен единице, поэтому диофантово уравнение с такими коэффициентами разрешимо всегда - разбор см. в задаче про уравнение в целых числах.

Частые ошибки

• Перебор делителей до $n$ или до $n/2$. Для 1729 это 863 проверки вместо 13, а для чисел порядка миллиарда разница между $n/2$ и $\sqrt{n}$ превращает секунды в годы.
• Обрыв перебора строго до корня, без самого корня. У полных квадратов вроде $1849 = 43^2$ так теряется единственный делитель.
• Причисление единицы к простым числам. У единицы один делитель, а не два, поэтому она не простая и не составная. Число 2, наоборот, простое, и это единственное чётное простое.
• Вывод «прошёл тест Ферма, значит простое». Тест доказывает только составность; проход по одному основанию не доказывает ничего, что и показывает 1729.
• Проверка нескольких оснований теста Ферма как способ повысить надёжность. Для чисел Кармайкла бесполезны все взаимно простые основания сразу, нужен тест Миллера и Рабина.
• Смешивание задачи проверки на простоту с задачей разложения на множители. Для вердикта достаточно одного делителя, доводить разложение до канонического вида не требуется.

FAQ

До какого числа перебирать делители? До целой части $\sqrt{n}$ включительно, а на практике удобнее записать условие цикла как $d^2 \leqslant n$. Если ни один кандидат не подошёл, число простое, и это строгий вывод.

Обязательно ли брать в кандидаты только простые числа? Нет, перебор всех чисел подряд даёт тот же вердикт, просто медленнее. Обычно берут компромисс: проверяют 2, а дальше только нечётные, экономя половину проверок без построения решета.

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

Как проверяют числа в сотни цифр, например в RSA? Перебором это невозможно, поэтому используют тест Миллера и Рабина с несколькими случайными основаниями: вероятность ошибки после $k$ раундов не превосходит $4^{-k}$. Для доказательства простоты с сертификатом применяют более тяжёлые алгоритмы.

Коротко

1. Считаем границу перебора: $\sqrt{1729} \approx 41{,}58$, значит проверяем делители до 41 включительно.
2. Берём в кандидаты простые числа до этой границы, их 13; список даёт решето Эратосфена.
3. Перебираем по порядку: 2, 3, 5 не подходят, а $1729 : 7 = 247$ делится нацело, и перебор останавливается.
4. Вердикт: 1729 составное, наименьший простой делитель 7, понадобилось 4 проверки делимости.
5. Тест Ферма по основанию 2 даёт $2^{1728} \equiv 1 \pmod{1729}$ и ошибочно признаёт число простым: 1729 является числом Кармайкла, для надёжной проверки нужен тест Миллера и Рабина.