Теоремы Ферма и Эйлера

1994 год. Принстон. Эндрю Уайлс объявляет доказательство Великой теоремы Ферма - той самой, которую Ферма написал на полях книги в 1637: "у меня есть чудесное доказательство, но поля слишком малы". 7 лет в тайне. 129 страниц. Первая версия содержит ошибку. Ещё год на исправление. А малая теорема того же Ферма - куда скромнее по виду, но куда мощнее по влиянию: RSA-2048, которым защищён каждый HTTPS-запрос, держится именно на $a^{p-1} \equiv 1 \pmod{p}$. Квантовый компьютер с алгоритмом Шора сломает это за часы. NIST это знает - потому и принял постквантовые стандарты в 2024.

• **RSA-2048:** генерация ключей использует $\varphi(n) = (p-1)(q-1)$; каждый вызов шифрования/дешифрования - быстрое возведение в степень по модулю n. Каждый HTTPS-запрос в браузере.
• **Miller-Rabin:** вероятностный тест простоты на основе малой теоремы Ферма - используется в Python `sympy.isprime`, OpenSSL, Java `BigInteger.isProbablePrime`. k=40 раундов дают вероятность ошибки менее $4^{-40}$.
• **Постквантовая криптография:** RSA уязвим к алгоритму Шора. NIST 2024 стандартизировал CRYSTALS-Kyber (решеточная криптография) - именно потому, что малая теорема Ферма перестанет быть защитой при достаточно мощных квантовых компьютерах.

Предварительные знания

• Модулярная арифметика

Малая теорема Ферма

1640 год. Пьер де Ферма пишет письмо и роняет мимоходом: если p - простое и p не делит a, то $a^{p-1} \equiv 1 \pmod{p}$. Никакого доказательства. Просто факт. Эйлер докажет это через сто лет. А через четыре века на этом факте будет держаться весь HTTPS-трафик планеты.

**Малая теорема Ферма:** Если p - простое и gcd(a, p) = 1, то: $a^{p-1} \equiv 1 \pmod{p}$ Эквивалентная форма (для любого a): $a^p \equiv a \pmod{p}$ **Следствие:** $a^{-1} \equiv a^{p-2} \pmod{p}$ - мгновенный модульный обратный при простом модуле.

Доказательство - маленький шедевр. Рассмотрим множество $\{a, 2a, 3a, \ldots, (p-1)a\}$ по модулю p. Все остатки различны (иначе $ia \equiv ja \Rightarrow i \equiv j$, ведь gcd(a,p)=1) и не равны нулю - значит, это перестановка $\{1, 2, \ldots, p-1\}$. Перемножаем: $a^{p-1} \cdot (p-1)! \equiv (p-1)! \pmod{p}$, откуда $a^{p-1} \equiv 1$. Python использует ровно это в `pow(a, p-1, p)` - триллионы раз в день для OpenSSL.

Обратное неверно: если $a^{n-1} \equiv 1 \pmod{n}$, это НЕ означает, что n - простое. Существуют числа Кармайкла (561, 1105, 1729...) - составные числа, которые притворяются простыми для теста Ферма. Miller-Rabin из следующего урока (nt-07) закрывает эту дыру.

Функция Эйлера и теорема Эйлера

Ферма работал только с простыми модулями. Эйлер спросил: а что если модуль составной? Ключ - посчитать, сколько чисел от 1 до n вообще имеют обратный элемент по модулю n. Это и есть $\varphi(n)$ - размер мультипликативной группы $\mathbb{Z}_n^*$. RSA полностью зависит от того, что вычислить $\varphi(n) = (p-1)(q-1)$ без знания p и q - практически невозможно.

**Функция Эйлера $\varphi(n)$:** количество целых $a \in \{1, \ldots, n\}$ с $\gcd(a, n) = 1$. **Формулы:** - $\varphi(p) = p - 1$ (p - простое) - $\varphi(p^k) = p^{k-1}(p - 1)$ - $\varphi(mn) = \varphi(m)\cdot\varphi(n)$ при $\gcd(m,n) = 1$ (мультипликативность) - $\varphi(n) = n \cdot \prod_{p \mid n}\left(1 - \frac{1}{p}\right)$ **Теорема Эйлера:** если $\gcd(a, n) = 1$, то $a^{\varphi(n)} \equiv 1 \pmod{n}$ **Частный случай:** для простого p, $\varphi(p) = p-1$ - малая теорема Ферма.

Быстрое возведение в степень

RSA-2048 оперирует числами в 617 десятичных цифр. Нужно вычислить $a^e \bmod n$, где e порядка $2^{1024}$. Наивный цикл потребует больше операций, чем атомов в наблюдаемой Вселенной. Алгоритм square-and-multiply делает это за O(log e) - около 2048 умножений.

**Быстрое возведение в степень (binary exponentiation):** Идея: разложить показатель в двоичном виде. $a^{13} = a^8 \cdot a^4 \cdot a^1$ (13 = 1101₂) Алгоритм: 1. result = 1, base = a 2. Идти по битам e справа налево 3. Если бит = 1: result *= base 4. base = base² (всегда) Сложность: O(log e) умножений - вместо O(e).

В Python `pow(base, exp, mod)` - это не просто удобство. Это C-реализация Montgomery multiplication с оптимизациями под конкретную архитектуру. OpenSSL генерирует ключи RSA именно через неё - сотни миллиардов вызовов в день по всему интернету. Для модульного обратного: `pow(a, mod-2, mod)` при простом mod, или `pow(a, -1, mod)` в Python 3.8+.

RSA: теорема Эйлера в действии

RSA - это не просто "возведение в степень по модулю". Это прямое следствие теоремы Эйлера: если $ed \equiv 1 \pmod{\varphi(n)}$, то $(m^e)^d = m^{ed} = m^{k\varphi(n)+1} \equiv m \cdot 1^k = m \pmod{n}$. Шифрование отменяется дешифрованием потому, что Эйлер доказал $a^{\varphi(n)} \equiv 1$. Вся современная PKI-инфраструктура держится на этом тождестве.

**RSA - генерация ключей:** 1. Выбрать два больших простых p, q 2. $n = p \cdot q$ (открытый модуль) 3. $\varphi(n) = (p-1)(q-1)$ 4. Выбрать e: $1 < e < \varphi(n)$, $\gcd(e, \varphi(n)) = 1$ (обычно e = 65537) 5. Найти d: $e\cdot d \equiv 1 \pmod{\varphi(n)}$ - расширенный Евклид 6. Открытый ключ: (n, e). Закрытый ключ: (n, d) **Шифрование:** $c = m^e \bmod n$ **Дешифрование:** $m = c^d \bmod n$ **Корректность:** $c^d = m^{ed} = m^{1+k\varphi(n)} = m \cdot (m^{\varphi(n)})^k \equiv m \cdot 1 = m \pmod{n}$

Безопасность RSA держится не на теореме Эйлера - она опирается на вычислительную сложность факторизации: зная n = p·q, вычислить $\varphi(n) = (p-1)(q-1)$ без знания p и q - задача, эквивалентная факторизации. Лучший классический алгоритм (решето числового поля, NFS) работает за субэкспоненциальное время. Алгоритм Шора на квантовом компьютере - за полиномиальное. Именно поэтому NIST в 2024 году стандартизировал CRYSTALS-Kyber: постквантовая замена RSA, пока квантовые компьютеры не выросли до угрожающих размеров.

Ключевые идеи

• **Ферма:** $a^{p-1} \equiv 1 \pmod{p}$ для простого p и $\gcd(a,p)=1$; следствие: $a^{-1} \equiv a^{p-2} \pmod{p}$
• **$\varphi(n)$:** количество чисел от 1 до n, взаимно простых с n; $\varphi(p) = p-1$; $\varphi(pq) = (p-1)(q-1)$ - секрет RSA
• **Эйлер:** $a^{\varphi(n)} \equiv 1 \pmod{n}$ при $\gcd(a,n)=1$ - обобщение Ферма на составные модули
• **RSA:** корректность дешифрования $c^d \equiv m \pmod{n}$ следует из $ed \equiv 1 \pmod{\varphi(n)}$ и теоремы Эйлера
• **Угроза:** алгоритм Шора на квантовом компьютере факторизует n за полиномиальное время - RSA перестаёт работать

Связанные темы

Теоремы Ферма и Эйлера - центральные теоремы, связывающие всю теорию чисел с криптографией:

• Модулярная арифметика — Мультипликативная группа $\mathbb{Z}_n^*$ - основа обеих теорем
• Тесты простоты — Тест Ферма и Miller-Rabin строятся напрямую на малой теореме Ферма
• Числа в криптографии — RSA от начала до конца - прямое применение теоремы Эйлера

Вопросы для размышления

• Почему в реальном RSA используют e = 65537 (= 2¹⁶ + 1), а не e = 3? Что могло бы пойти не так с маленьким e?
• Если злоумышленник узнает $\varphi(n)$, что он может вычислить? Почему это полностью ломает RSA?
• Теорема Эйлера требует $\gcd(a, n) = 1$. Что произойдёт, если зашифровать сообщение m, которое делится на p или q?
• Алгоритм Шора факторизует n за $O(\log^3 n)$ операций на квантовом компьютере. Какой размер ключа RSA потребуется, чтобы это занимало больше времени жизни Вселенной?

Связанные уроки

• nt-03 — Мультипликативная группа ℤₙ* - основа обеих теорем
• nt-07 — Miller-Rabin строится прямо на малой теореме Ферма
• nt-11 — RSA от генерации ключей до взлома - прямое следствие теоремы Эйлера
• prob-03-conditional — Та же структура: условие gcd=1 как условная независимость
• crypto-24-rsa-math
• crypto-26-ecc-math