Степень по модулю и малая теорема Ферма

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

Как думаешь, можно ли посчитать это в уме

Нужен остаток от деления 3 в степени триллион на 1 000 003. Умножать тройку триллион раз не выйдет. Быстрая степень из раздела про рекуррентности справится за сорок кругов - но это полсотни умножений шестизначных чисел, без бумаги не сделать.

Прежде чем читать дальше, попробуй угадать: существует ли способ получить ответ в уме, зная про модуль только то, что 1 000 003 - простое число? Ответ - 81.

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

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

Остатки степеней тройки по модулю 7 - такая фишка: 3, 2, 6, 4, 5, 1 и снова 3. Круг из шести шагов. Чтобы узнать, где фишка окажется после миллиона ходов, не нужно делать миллион ходов - достаточно знать длину круга и остаток от деления миллиона на неё.

Механизм: биты показателя и длина круга

Быстрая степень. Показатель записывается в двоичном виде, и степень собирается из квадратов:

n = 13 = 1101₂ = 8 + 4 + 1          a¹³ = a⁸ · a⁴ · a¹

бит (с младшего)    1      0      1      1
квадраты            a¹     a²     a⁴     a⁸        каждый - квадрат предыдущего
в ответ             да     нет    да     да

На каждый бит - одно возведение в квадрат и, если бит единичный, одно домножение. Битов в числе n около log₂ n, умножений не больше двух на бит. Остаток берётся после каждого умножения, поэтому все числа меньше m и каждое умножение стоит одинаково. В прошлой главе тот же приём без модуля выиграл всего вдвое, потому что числа росли; здесь расти нечему.

Длина круга. Возьмём простое p и число a, не кратное p. Из урока про остатки: строка таблицы умножения по простому модулю - перестановка. Причина - в прошлом уроке: у a есть обратный, поэтому из a · x ≡ a · y следует x ≡ y, и разные числа переходят в разные. То есть числа a · 1, a · 2, …, a · (p − 1) по модулю p - это те же 1, 2, …, p − 1, только в другом порядке. Перемножим всё слева и всё справа:

(a · 1) · (a · 2) · … · (a · (p − 1))  ≡  1 · 2 · … · (p − 1)      (mod p)
a^(p−1) · (p − 1)!                     ≡  (p − 1)!                 (mod p)
a^(p−1)                                ≡  1                        (mod p)

Последний переход - сокращение на (p − 1)!. Оно законно: ни один множитель факториала не кратен p, значит у каждого есть обратный. Получилось, что через p − 1 шаг фишка обязательно стоит на единице. Настоящий круг может быть короче, но его длина всегда делит p − 1: иначе через p − 1 шаг фишка стояла бы посреди круга, а не на единице.

Для составного модуля m строка таблицы - перестановка только среди остатков, взаимно простых с m. Их число обозначают φ(m). Функция Эйлера φ(m) - сколько чисел от 1 до m взаимно просты с m. Для простого φ(p) = p − 1. Для произведения двух разных простых φ(p · q) = (p − 1) · (q − 1): из p · q чисел выбрасываются q кратных p и p кратных q, а само p · q при этом посчитано дважды. То же рассуждение даёт a^φ(m) ≡ 1 (mod m) для a, взаимно простого с m.

Правило

aⁿ mod m считается за ⌊log₂ n⌋ + 1 кругов, в каждом одно или два умножения по модулю. Малая теорема Ферма: если p простое и a не делится на p, то a^(p−1) ≡ 1 (mod p). Теорема Эйлера: если НОД(a, m) = 1, то a^φ(m) ≡ 1 (mod m). Следствия: показатель степени можно заменить его остатком по модулю p − 1 (или φ(m)); обратный к a по простому модулю равен a^(p−2).

Скобки ⌊ ⌋ - округление вниз.

Разбор: программа и число кругов

def stepen(a, n, m):
    r = 1
    a = a % m
    krugov = 0
    while n > 0:
        if n % 2 == 1:
            r = r * a % m
        a = a * a % m
        n = n // 2
        krugov = krugov + 1
    return [r, krugov]

n % 2 - младший бит показателя, n // 2 сдвигает к следующему. Основание 3, модуль 1 000 003:

показатель n        ответ      кругов    шагов
10³                 73 216       10         62
10⁶                222 223       20        113
10⁹                347 529       30        169
10¹²                    81       40        219
10¹⁵               400 755       50        276

Показатель вырос в тысячу раз - прибавилось десять кругов: 2¹⁰ = 1024. Цикл, который умножает на тройку миллион раз, тратит на вторую строку 3 000 004 шага вместо 113.

Разбор: теорема Ферма в деле и её граница

В таблице есть странная строка: при показателе 10¹² ответ - 81, то есть 3⁴. Это не совпадение. Модуль p = 1 000 003 простой, значит 3^(p−1) = 3^1 000 002 ≡ 1. Триллион при делении на 1 000 002 даёт остаток 4: 10⁶ = 1 000 002 − 2, поэтому 10⁶ ≡ −2, а 10¹² ≡ (−2)² = 4. Полные круги по 1 000 002 шага возвращают фишку на единицу, остаются четыре шага: 3⁴ = 81. Вот способ из начала урока.

Второе следствие - обратный элемент. a^(p−1) = a · a^(p−2) ≡ 1, значит a^(p−2) и есть обратный. stepen(123456, 1000001, 1000003) возвращает [414894, 20] - то же число 414 894, что расширенный Евклид в прошлом уроке. Цена почти одинакова: 114 шагов у степени, 120 у Евклида.

Теперь граница. Возьмём составной модуль 91 = 7 · 13 и применим теорему как к простому:

2⁹⁰ mod 91 = 64        не единица: 91 не простое, теорема Ферма к нему не относится
3⁹⁰ mod 91 = 1         единица, хотя 91 составное

Первая строка показывает, что с составным модулем показатель m − 1 не работает. Правильный показатель - φ(91) = 6 · 12 = 72, и 2⁷² mod 91 = 1. Вторая строка - предупреждение на будущее: единица в ответе не доказывает простоту модуля. Основание 3 «лжёт» про число 91, и на этом наблюдении построена следующая глава.

Тот же обратный через Эйлера по составному модулю: φ(40) = 16 (взаимно простые с 40 - нечётные числа, не кратные пяти; их шестнадцать), 7¹⁶ mod 40 = 1, и 7¹⁵ mod 40 = 23 - обратный к 7 по модулю 40 из прошлого урока.

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

Первое: показатель по модулю p. Хочется написать a^(n mod p). Круг имеет длину p − 1, а не p: 2¹⁰ mod 7 = 2, а 2^(10 mod 7) = 2³ = 8 ≡ 1. Основание берут по модулю p, показатель - по модулю p − 1.

Второе: основание, кратное модулю. Теорема требует, чтобы a не делилось на p. Иначе a ≡ 0, все степени нулевые, и «обратный» a^(p−2) равен нулю.

Третье: произведение не помещается в тип. a * a % m при m больше 94 906 265 выходит за точность тренажёра раньше, чем возьмётся остаток; в C то же происходит при m больше 2³². Встроенная pow(a, n, m) считает точно при любом модуле.

Четвёртое: время выдаёт показатель. Домножение выполняется только на единичных битах, значит время работы зависит от того, сколько в показателе единиц. Если показатель - секретный ключ, по времени ответа сервера его можно восстановить. Криптографические библиотеки считают степень так, чтобы на каждом бите делалось одно и то же.

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

В Python это одна встроенная функция: pow(a, n, m). Писать a ** n % m нельзя - сначала будет вычислено всё длинное число.

Шифрование RSA, о котором глава «RSA и обмен ключами», - одна степень по модулю, расшифровка - другая. Обмен ключами Диффи-Хеллмана - по две степени с каждой стороны. Проверка простоты в следующей главе - степень и несколько квадратов. Вся криптография с открытым ключом до последнего времени - это цикл из разбора выше над числами в тысячи бит.

Длина круга - это период. Генератор случайных чисел вида «умножь на константу по модулю» повторяется через длину круга, и константу подбирают так, чтобы круг был самым длинным. Последние цифры огромной степени - та же задача по модулю 10 или 100.

Теперь сам

1. Показатель 22. Запиши его в двоичном виде. Сколько кругов сделает цикл и сколько из них с домножением?
2. Найди 2¹⁰⁰ mod 7 в уме.
3. Найди обратный к 3 по модулю 7 через теорему Ферма.
4. Последняя цифра числа 7²⁰²⁶. Остатки степеней семёрки по модулю 10 идут так: 7, 9, 3, 1, 7, …