Диофантовы уравнения

Задача Ферма: сумму двух кубов нельзя представить как куб. Задача RSA: найти d такой, что e·d ≡ 1 (mod φ(n)). Обе задачи сводятся к поиску целочисленных решений уравнений. Расширенный алгоритм Евклида решает вторую за O(log n) - именно так OpenSSL вычисляет закрытый ключ RSA в вашем браузере.

• **RSA закрытый ключ:** d = e⁻¹ mod φ(n) вычисляется расширенным Евклидом; именно это делает OpenSSL
• **Атака Винера:** если d < n^(1/4), d находится через непрерывные дроби - то же ядро, что в решении Пелля
• **Задача о монетах:** максимальная сумма, недостижимая монетами a,b (gcd=1): ab−a−b (формула Фробениуса)

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

• Primality Tests

Линейные диофантовы уравнения

Диофант Александрийский в III веке искал целочисленные решения уравнений. Простейший случай - линейное диофантово уравнение ax + by = c. Оно растворимо в целых числах тогда и только тогда, когда gcd(a, b) | c.

**Линейное диофантово уравнение ax + by = c:** **Критерий разрешимости:** решение существует ⟺ gcd(a,b) | c. **Если g = gcd(a,b) | c:** частное решение (x₀, y₀) даёт расширенный Евклид. Общее решение: x = x₀ + (b/g)·t, y = y₀ − (a/g)·t, t ∈ ℤ. **Пример:** 6x + 10y = 14. gcd(6,10) = 2, 2|14 → разрешимо. 3x + 5y = 7 → частное: x₀=4, y₀=−1. Общее: x = 4+5t, y = −1−3t.

Практический контекст: задача о монетах (задача Фробениуса/Нагеля). Если монеты достоинством a и b, то какие суммы нельзя набрать? Для gcd(a,b)=1 максимальная «неразменная» сумма = ab − a − b (формула Сильвестра-Фробениуса). Например, для монет 3 и 5: 15−3−5 = 7. Число 7 нельзя набрать монетами по 3 и 5.

Расширенный алгоритм Евклида

Расширенный алгоритм Евклида - рабочая лошадка всей криптографии. Он не только вычисляет НОД, но и находит коэффициенты Безу: ax + by = gcd(a,b). Это прямой путь к модульному обратному.

**Расширенный алгоритм Евклида:** Для любых a, b существуют целые x, y (коэффициенты Безу): a·x + b·y = gcd(a, b) **Приложение - модульный обратный:** Если gcd(a, n) = 1, то из ax + ny = 1 следует ax ≡ 1 (mod n), значит a⁻¹ ≡ x (mod n). **Приложение в RSA:** вычисление d = e⁻¹ mod φ(n). **Сложность:** O(log min(a,b)) - логарифмическая.

В Python 3.8+ встроен pow(a, -1, n) для модульного обратного - он использует расширенный Евклид внутри. Для понимания RSA важно уметь вычислять вручную: e·d ≡ 1 (mod φ(n)) → d = extended_gcd(e, φ(n))[1] % φ(n).

Пифагоровы тройки

Пифагоровы тройки (a, b, c): a² + b² = c². Древние египтяне знали (3, 4, 5). Все примитивные тройки (без общих множителей) параметризуются парами натуральных чисел m > n > 0.

**Параметрическая формула примитивных пифагоровых троек:** Для m > n > 0, gcd(m,n) = 1, m и n разной чётности: a = m² − n² b = 2mn c = m² + n² **Примеры:** - m=2, n=1: a=3, b=4, c=5 - m=3, n=2: a=5, b=12, c=13 - m=4, n=1: a=15, b=8, c=17 - m=4, n=3: a=7, b=24, c=25 **Все** пифагоровы тройки получаются из примитивных умножением на k.

Связь с гауссовыми целыми: если записать z = m + ni ∈ ℤ[i], то z² = (m²−n²) + 2mni. Реальная часть - a, мнимая - b, |z²| = |z|² = m²+n² = c. Пифагорова тройка - это «квадрат гауссова целого». Это первый намёк на алгебраическую теорию чисел.

Уравнение Пелля

Уравнение Пелля x² − Dy² = 1 - знаменитое диофантово уравнение, изученное индийскими математиками в VII веке. Его решения - бесконечная последовательность, генерируемая фундаментальным решением через непрерывные дроби.

**Уравнение Пелля:** x² − D·y² = 1, где D - не полный квадрат. **Факты:** - Всегда имеет бесконечно много решений (если D - не квадрат) - Фундаментальное решение (x₁, y₁) - наименьшее при x,y > 0 - Остальные: xₙ + yₙ√D = (x₁ + y₁√D)ⁿ **Примеры (D=2):** x² − 2y² = 1 - (3,2): 9−8=1 ✓ - (17,12): 289−288=1 ✓ - (99,70): 9801−9800=1 ✓ **Нахождение фундаментального решения:** разложение √D в непрерывную дробь.

Уравнение Пелля появляется в атаках на RSA: метод Видемана (Wiener's attack) использует то, что d < n^(1/4) позволяет найти d через аппроксимации непрерывными дробями. Это то же математическое ядро - фундаментальное решение Пелля. Именно поэтому d должен быть достаточно большим.

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

• **Линейное ax+by=c:** разрешимо ⟺ gcd(a,b)|c; расширенный Евклид даёт частное решение; общее - параметрическое
• **Расширенный Евклид:** a·x + b·y = gcd(a,b) за O(log n); прямой путь к модульному обратному
• **Пифагоровы тройки:** параметризация a=m²−n², b=2mn, c=m²+n²; связь с гауссовыми целыми
• **Уравнение Пелля:** x²−Dy²=1; бесконечно много решений; фундаментальное - через непрерывные дроби

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

Диофантовы уравнения - мост между элементарной и алгебраической теорией чисел:

• Алгоритм Евклида и НОД — Расширенный Евклид - ключевой инструмент решения линейных диофантовых уравнений
• Алгебраическая теория чисел — Пифагоровы тройки и уравнение Пелля - введение в кольца гауссовых целых и квадратурные поля
• Числа в криптографии — Атака Винера на RSA использует теорию непрерывных дробей из решения уравнения Пелля

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

• Задача Фробениуса: монеты достоинством 6 и 9 рублей. Можно ли набрать все суммы ≥ 12? Почему условие gcd = 1 критично?
• Пифагорова тройка (3,4,5) связана с гауссовым целым 2+i. Что за тройка получится из 3+2i?
• Атака Винера использует теорию непрерывных дробей для нахождения малого d в RSA. Почему требование d > n^(1/4) защищает от этой атаки?

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

• aa-04-rings