Тест Ферма: доказать, что число составное, не найдя делителя

Коротко

Малая теорема Ферма говорит: для простого n степень aⁿ⁻¹ даёт по модулю n единицу. Перевернём: если aⁿ⁻¹ mod n - не единица, то n составное, и доказано это одной степенью, без единого делителя. Число a в таком случае называют свидетелем. Если единица получилась, вывода нет: 3⁹⁰ mod 91 = 1, хотя 91 = 7 · 13. У числа 91 лгут 36 оснований из 72 взаимно простых с ним, и повторение теста с разными основаниями быстро это вскрывает. Но есть числа Кармайкла, у которых лгут все такие основания: у 561 = 3 · 11 · 17 - все 320. Тест Ферма нельзя сделать надёжным повторением, и следующий урок это чинит.

Если ты объяснишь, что доказывает и чего не доказывает результат теста Ферма, почему у обычного составного числа лжёт не больше половины оснований и чем особенны числа Кармайкла, - листай до «Теперь сам».

Как думаешь, можно ли доказать составность без делителя

Число 91 составное: 91 = 7 · 13. Обычное доказательство составности - предъявить делитель. Для числа из шестисот цифр делитель перебором не найти: первая глава раздела показала, что √N шагов - экспонента.

Прежде чем читать дальше, ответь себе: можно ли убедиться, что число составное, так и не узнав ни одного его делителя? Что вообще может служить доказательством, кроме делителя?

На что это похоже

Представь банкноту и ультрафиолетовую лампу. У настоящей банкноты под лампой светится защитная полоса. Если полосы нет - банкнота фальшивая, и это доказано: не нужно знать, кто и как её печатал. Если полоса есть - это ещё ничего не значит: хорошая подделка тоже светится.

Проверка работает в одну сторону. Отсутствие признака, обязательного для настоящих, - доказательство подделки. Наличие - только отсутствие улик.

Механизм: теорема, прочитанная наоборот

Малая теорема Ферма из прошлой главы: если n простое и a не делится на n, то aⁿ⁻¹ ≡ 1 (mod n). Это признак, обязательный для всех простых. Читаем наоборот: если нашлось a от 2 до n − 2, для которого aⁿ⁻¹ mod n ≠ 1, то n не простое.

n = 91:     2⁹⁰ mod 91 = 64      не единица  →  91 составное. Делители не понадобились.
            3⁹⁰ mod 91 = 1       единица     →  вывода нет

n = 97:     aⁿ⁻¹ mod 97 = 1 при любом a от 1 до 96     97 простое, по теореме иначе и быть не может

Основание a, которое разоблачает составное n, называют свидетелем. Основание, при котором составное n даёт единицу, - лжецом. Число 2 - свидетель для 91, число 3 - лжец.

Сколько бывает лжецов. Пусть у составного n есть хотя бы один свидетель w, взаимно простой с n. Возьмём любого лжеца b и умножим: (w · b)ⁿ⁻¹ = wⁿ⁻¹ · bⁿ⁻¹ ≡ wⁿ⁻¹ · 1 ≠ 1. Произведение w · b - тоже свидетель. Разные лжецы дают разные произведения: у w есть обратный, и из w · b₁ ≡ w · b₂ следовало бы b₁ ≡ b₂. Значит каждому лжецу соответствует свой свидетель, и свидетелей не меньше, чем лжецов. Лжецов - не больше половины оснований, взаимно простых с n.

Вся оговорка - в словах «есть хотя бы один свидетель, взаимно простой с n». Бывает, что нет.

Правило

Тест Ферма по основанию a: вычислить aⁿ⁻¹ mod n. Не единица - n точно составное. Единица - n «вероятно простое». Если у составного n есть хотя бы один свидетель, взаимно простой с n, то лжёт не больше половины оснований, и k тестов со случайными основаниями ошибаются с вероятностью не больше 1/2ᵏ. У чисел Кармайкла таких свидетелей нет вовсе: для них тест Ферма ошибается почти при любом основании, сколько его ни повторяй.

Разбор: программа и число 91

def test_ferma(a, n):
    return pow(a, n - 1, n) == 1

Встроенная pow с тремя аргументами - степень по модулю из прошлой главы. Цена теста - одна такая степень: число кругов равно числу битов n.

Переберём все основания для n = 91:

оснований от 1 до 90                      90
взаимно простых с 91                      72
из них дают единицу (лжецы)               36
из них дают не единицу (свидетели)        36

В счёт вошли и основания 1 и 90: они дают единицу для любого нечётного числа и в тесте не используются. Без них лжецов 34 из 70.

Ровно половина - предел из правила достигнут. Случайное основание разоблачает 91 с вероятностью не меньше половины; два основания - три четверти; десять - 1023 из 1024. Для числа 341 = 11 · 31 лжецов 100 из 300: основание 2 лжёт, основание 3 - свидетель.

Ответ на вопрос из начала урока: да. 2⁹⁰ mod 91 = 64 - доказательство составности, в котором нет ни семёрки, ни тринадцати. Оно ничего не говорит о делителях и ничего не стоит: одна степень по модулю.

Разбор: число, у которого лгут все

n = 561 = 3 · 11 · 17

взаимно простых с 561                    320
из них дают единицу (лжецы)              320
из них свидетели                           0

Число 561 проходит тест Ферма по любому основанию, взаимно простому с ним. Такие числа называют числами Кармайкла. Условие «есть хотя бы один взаимно простой свидетель» для них не выполнено, и оценка «не больше половины» к ним не относится.

Устроены они так. Для каждого простого делителя p числа 561 число p − 1 делит 560: 2, 10 и 16 - все делят 560. По теореме Ферма a^(p−1) ≡ 1 (mod p), а 560 - кратное p − 1, значит a⁵⁶⁰ ≡ 1 по каждому из трёх модулей. По китайской теореме - и по их произведению.

Разоблачить 561 тестом Ферма могут только основания, имеющие с ним общий делитель, - кратные 3, 11 или 17; их 240 из 560. У маленького числа это много. Но у числа Кармайкла из трёх простых по сто цифр доля таких оснований - около 10⁻¹⁰⁰, и попасть в них значит случайно угадать делитель.

Чисел Кармайкла мало - до ста тысяч их шестнадцать: 561, 1105, 1729, 2465, 2821 и дальше, - но в 1994 году доказано, что их бесконечно много. Мало - не значит безопасно: если число на проверку присылает кто-то чужой, он пришлёт именно такое.

Что ломается без этого

Первое: «единица - значит простое». Тест отвечает «составное» или «не знаю». Программа, которая печатает «простое» после одного прохода, ошибается на 341 по основанию 2.

Второе: основания 1 и n − 1. Единица в любой степени - единица. А n − 1 ≡ −1, и для нечётного n показатель n − 1 чётный: (−1) в чётной степени - тоже единица. Оба основания «лгут» для любого нечётного числа, поэтому основания берут от 2 до n − 2.

Третье: одно фиксированное основание. Составных нечётных чисел до ста тысяч, которые проходят тест по основанию 2, - 78. Немного, но каждое из них программа с одним основанием назовёт простым всегда, при каждом запуске.

Четвёртое: a ** (n - 1) % n вместо pow. Сначала будет вычислено число из миллионов цифр. Тест существует только потому, что степень считается по модулю.

Зачем это в работе

Сама идея важнее теста. Доказательство, которое не предъявляет объект, а показывает, что без него не сходятся концы, - свидетель - встретится ещё много раз: в проверке простоты, в вероятностных алгоритмах, в теории сложности, где класс задач определяют через то, что за свидетель у них бывает.

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

А для чужих данных - нет. Библиотека, которая проверяет присланный ей «простой» модуль тестом Ферма, принимает число Кармайкла. Поэтому в криптографии им не пользуются, а пользуются его усилением.

Теперь сам

2¹⁴ mod 15 = 4. Что это доказывает про 15?
4¹⁴ mod 15 = 1. Что это доказывает про 15? Как называется основание 4?
Составное число - не Кармайкла. Тест повторили с пятью случайными основаниями, все дали единицу. Какова самое большее вероятность такого исхода?
1105 = 5 · 13 · 17. Проверь по делителям, что оно устроено как число Кармайкла.

Ответ. 1. Что 15 составное: у простого числа было бы 1. Основание 2 - свидетель.

Ничего. Основание 4 - лжец: 4² = 16 ≡ 1, поэтому 4¹⁴ = (4²)⁷ ≡ 1.
1/2⁵ = 1/32: каждое основание лжёт с вероятностью не больше половины.
1104 делится на 5 − 1 = 4 (276 · 4), на 13 − 1 = 12 (92 · 12) и на 17 − 1 = 16 (69 · 16). Значит a¹¹⁰⁴ ≡ 1 по каждому из трёх модулей и по их произведению.

Главное

Тест Ферма - первое доказательство составности без делителей: число не обладает свойством, обязательным для простых. Доказательство работает в одну сторону - «составное» он говорит наверняка, «простое» не говорит никогда. У обычных составных чисел не меньше половины оснований - свидетели, и повторение теста сводит ошибку к нулю. Но числа Кармайкла лгут при всех разумных основаниях, и чинить это приходится не числом повторов, а более зорким тестом.