Малая теорема Ферма и её применения
Изучаем теорему, которая лежит в основе быстрых вычислений по модулю и проверки чисел на простоту.
Малая теорема Ферма: если p — простое число и a не делится на p, то
a^(p−1) ≡ 1 (mod p).
Зачем нужна теорема Ферма
Это одна из самых полезных теорем прикладной математики. Она даёт быстрый способ находить обратные элементы по модулю (а значит, расшифровывать в криптографии), лежит в основе тестов на простоту (как проверить, простое ли 300-значное число, не перебирая делители?), и используется в самом RSA. Малая теорема Ферма — пример того, как чисто теоретический факт XVII века стал инструментом, защищающим сегодня каждую интернет-транзакцию.
Что утверждает теорема
Возьмём простое p и любое a, не кратное p. Тогда, сколько ни возводи a в степень p−1 и бери остаток по модулю p, всегда получится единица. Удивительно: для разных a результат один и тот же — 1. Проверим это для p = 7: возведём 1, 2, ..., 6 в шестую степень по модулю 7.
p = 7
results = [pow(a, p - 1, p) for a in range(1, p)] # a^(p-1) mod p
print(f"a^(p-1) mod {p} для a = 1..{p-1}:", results)
print("Все равны 1:", all(r == 1 for r in results))
# Проверим ещё для p = 13
p = 13
results = [pow(a, p - 1, p) for a in range(1, p)]
print(f"a^(p-1) mod {p} для a = 1..{p-1}:", results)Вывод:
a^(p-1) mod 7 для a = 1..6: [1, 1, 1, 1, 1, 1] Все равны 1: True a^(p-1) mod 13 для a = 1..12: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Действительно: для каждого a от 1 до 6 величина a^6 mod 7 равна единице, и то же для модуля 13. Это не совпадение, а строгий закон. Интуиция доказательства: умножение на a по модулю p просто переставляет ненулевые остатки {1, 2, ..., p−1} между собой (это биекция!). Перемножив все остатки до и после перестановки, получаем равенство, из которого и следует a^(p−1) ≡ 1. Снова биекция из раздела про функции работает на нас.
Применение 1: быстрое нахождение обратного элемента
В прошлом уроке мы искали обратный элемент перебором или расширенным Евклидом. Если модуль p простой, теорема Ферма даёт прямую формулу. Из a^(p−1) ≡ 1 следует a · a^(p−2) ≡ 1, то есть обратный элемент к a — это a^(p−2) mod p. Никакого перебора — одно возведение в степень.
p = 7
a = 3
inverse = pow(a, p - 2, p) # a^(p-2) mod p — обратный по Ферма
print(f"Обратный к {a} по модулю {p}: {inverse}")
print(f"Проверка: {a} * {inverse} mod {p} =", (a * inverse) % p)Вывод:
Обратный к 3 по модулю 7: 5 Проверка: 3 * 5 mod 7 = 1
Формула 3^(7−2) mod 7 = 3^5 mod 7 = 5 мгновенно дала обратный элемент — то же число 5, что мы раньше искали перебором. Это и есть способ «делить» по простому модулю в один вызов pow. Расшифровка в RSA устроена ровно так — через возведение в степень по модулю.
Применение 2: тест на простоту
Теорему можно «перевернуть» для проверки простоты. Если для какого-то a вдруг a^(n−1) mod n ≠ 1, то n точно составное (ведь для простого было бы 1). Это тест Ферма на простоту: берём несколько случайных a и проверяем условие.
Тонкость: обратное неверно в полную силу — есть редкие составные числа (числа Кармайкла), которые «притворяются» простыми, проходя тест для многих a. Поэтому тест Ферма — вероятностный: он может ошибиться в сторону «простое», но если сказал «составное» — это точно. На его идее построены практичные тесты (Миллера-Рабина), которыми проверяют огромные простые для криптографии. Посмотрим тест в действии.
def fermat_test(n, a):
# Если a^(n-1) mod n != 1, то n ТОЧНО составное
if n <= 1:
return False
return pow(a, n - 1, n) == 1
# 561 — число Кармайкла: составное (561 = 3·11·17), но обманывает тест
print("561 проходит тест для a=2?", fermat_test(561, 2))
print("561 проходит тест для a=5?", fermat_test(561, 5))
# a=3 разоблачает 561 (3 делит 561)
print("561 проходит тест для a=3?", fermat_test(561, 3))
# 13 — настоящее простое, проходит для всех a
print("13 проходит тест для a=2,5,7?",
all(fermat_test(13, a) for a in (2, 5, 7)))Вывод:
561 проходит тест для a=2? True 561 проходит тест для a=5? True 561 проходит тест для a=3? False 13 проходит тест для a=2,5,7? True
Число 561 (это 3·11·17, составное!) обмануло тест для a = 2 и a = 5 — оба раза условие выполнилось. Но a = 3 его разоблачило: 3^560 mod 561 ≠ 1. Это наглядно показывает, почему тест Ферма вероятностный: для надёжности нужно проверять несколько разных a. А настоящее простое 13 честно прошло все проверки. Так дискретная математика балансирует между «быстро» и «надёжно» в реальной криптографии.
Китайская теорема об остатках: собрать число по кусочкам
Один из самых полезных результатов модулярной арифметики — китайская теорема об остатках, известная ещё древнекитайским математикам. Она утверждает: если знать остатки числа по нескольким взаимно простым модулям, то само число (в пределах их произведения) восстанавливается однозначно. Скажем, число, дающее остаток 2 при делении на 3, остаток 3 при делении на 5 и остаток 2 при делении на 7, — это единственное число от 0 до 104 (тут 3·5·7 = 105), а именно 23.
Зачем это программисту? Теорема позволяет заменить вычисления с одним гигантским модулем на несколько вычислений с маленькими модулями, которые можно вести параллельно, а потом «склеить» ответ. На этом основаны быстрые алгоритмы умножения больших чисел, ускорение расшифровки в RSA, распределённые вычисления и системы остаточных классов в процессорах. Красота в том, что разные остатки несут независимую информацию о числе, и вместе они задают его целиком — ещё одно проявление того, как модулярная арифметика превращает большое в управляемо-маленькое.
Теорема Эйлера: обобщение Ферма на любой модуль
Малая теорема Ферма работает только для простого модуля. Её обобщил Леонард Эйлер — и именно теорема Эйлера лежит в основе RSA, где модуль составной. Для этого вводят функцию Эйлера φ(n) — количество чисел от 1 до n, взаимно простых с n. Например, φ(10) = 4 (это 1, 3, 7, 9). Для простого p, очевидно, φ(p) = p − 1 — все меньшие числа взаимно просты с простым.
Теорема Эйлера: если a и n взаимно просты, то a^φ(n) ≡ 1 (mod n). Подставьте сюда простое n = p, и φ(p) = p − 1 — получите ровно малую теорему Ферма. То есть Ферма — частный случай Эйлера. Эта теорема позволяет находить обратные элементы и «отматывать» возведение в степень по любому модулю, а не только по простому, — что и нужно RSA, где модуль n = p·q является произведением двух простых. Так теорема Ферма оказывается лишь первой ступенью к более общему и ещё более мощному инструменту.
Типичные ошибки
- Применять теорему при составном модуле. Малая теорема Ферма требует простого p. Для составного модуля есть обобщение — теорема Эйлера с функцией φ(n).
- Забывать условие «a не кратно p». Если a делится на p, то
a ≡ 0, иa^(p−1) ≡ 0, а не 1. - Считать тест Ферма безошибочным. Числа Кармайкла обманывают его. Тест вероятностный: «составное» — точно, «простое» — с высокой вероятностью.
Итог
- Малая теорема Ферма: для простого p и a, не кратного p, верно
a^(p−1) ≡ 1 (mod p). - Доказательство опирается на то, что умножение по модулю переставляет остатки (биекция).
- Применение: обратный элемент по простому модулю — это
a^(p−2) mod p. - Тест Ферма проверяет простоту, но вероятностно (числа Кармайкла обманывают его) — основа быстрых тестов для криптографии.
