Диофантовы уравнения
Диофантовы уравнения — уравнения с целыми коэффициентами, решения которых ищут в целых числах. Названы в честь Диофанта Александрийского (III век). Линейные диофантовы уравнения полностью решаются расширенным алгоритмом Евклида — тем же, которым в криптографии вычисляют обратные элементы и секретный ключ RSA.
Линейное уравнение ax + by = c
Пусть d = НОД(a, b). Уравнение ax + by = c разрешимо в целых числах тогда и только тогда, когда d | c. Если (x_0, y_0) — одно решение, то все решения имеют вид
Доказательство.
- Необходимость: d делит a и b, значит, делит ax + by = c.
- Достаточность: по соотношению Безу (ниже) есть s, t с as + bt = d. Умножив на c/d, получаем решение x_0 = s·c/d, y_0 = t·c/d.
- Все решения: если (x, y) — тоже решение, то a(x − x_0) = −b(y − y_0). Разделив на d, получим (a/d)(x − x_0) = −(b/d)(y − y_0), а так как a/d и b/d взаимно просты, (b/d) | (x − x_0).
Расширенный алгоритм Евклида
Для любых целых a, b, не равных нулю одновременно, существуют целые s, t, такие что as + bt = НОД(a, b).
Алгоритм Евклида заменяет пару (a, b) на (b, a mod b), пока остаток не станет нулём; последний ненулевой остаток — НОД. Расширенный вариант хранит для каждого остатка r_i представление r_i = s_i·a + t_i·b и пересчитывает коэффициенты по тому же правилу, что и остатки: s_i = s_(i−2) − q_i·s_(i−1).
| i | rᵢ | qᵢ | sᵢ | tᵢ | проверка |
|---|---|---|---|---|---|
| 0 | 240 | — | 1 | 0 | 240 = 1·240 + 0·46 |
| 1 | 46 | — | 0 | 1 | 46 = 0·240 + 1·46 |
| 2 | 10 | 5 | 1 | −5 | 240 − 5·46 |
| 3 | 6 | 4 | −4 | 21 | 46 − 4·10 |
| 4 | 4 | 1 | 5 | −26 | 10 − 6 |
| 5 | 2 | 1 | −9 | 47 | 6 − 4 |
| 6 | 0 | 2 | остаток 0 — стоп | ||
НОД(240, 46) = 2 = 240·(−9) + 46·47. Решим 240x + 46y = 10: 2 | 10, умножаем на 5: x_0 = −45, y_0 = 235. Все решения: x = −45 + 23t, y = 235 − 120t.
Число шагов алгоритма Евклида не больше примерно 5·(число десятичных цифр меньшего числа) (теорема Ламе); худший случай — соседние числа Фибоначчи. Поэтому алгоритм быстр и для чисел из тысяч бит.
Линейные сравнения и обратные элементы
Сравнение ax ≡ b (mod m) равносильно уравнению ax − my = b. Оно разрешимо тогда и только тогда, когда НОД(a, m) | b, и тогда имеет НОД(a, m) решений по модулю m. В частности, при НОД(a, m) = 1 существует обратный элемент a⁻¹ mod m — это коэффициент s из as + mt = 1.
7x ≡ 3 (mod 10): 7⁻¹ ≡ 3, так как 7·3 = 21 ≡ 1. Значит, x ≡ 3·3 = 9 (mod 10); проверка: 63 ≡ 3.
Применение: секретный ключ RSA
В RSA выбирают простые p, q, модуль n = pq, φ(n) = (p − 1)(q − 1) и открытую экспоненту e, взаимно простую с φ(n). Секретная экспонента d — решение сравнения ed ≡ 1 (mod φ(n)), то есть диофантова уравнения ed − φ(n)·k = 1.
p = 61, q = 53: n = 3233, φ = 3120, e = 17. Расширенный алгоритм Евклида даёт d = 2753 (17·2753 = 46801 = 15·3120 + 1). Сообщение M = 65 шифруется в C = 65^17 mod 3233 = 2790, и 2790^2753 mod 3233 = 65.
Другие классические задачи
Размен монет
Какие суммы можно набрать монетами номиналов a и b? Это уравнение ax + by = c с x, y ≥ 0. При взаимно простых a, b все суммы больше ab − a − b набираются, а сама она — нет (теорема Сильвестра). Например, монетами 3 и 5 нельзя набрать только 1, 2, 4 и 7.
Пифагоровы тройки
Все примитивные решения x² + y² = z² (с НОД(x, y, z) = 1) задаются формулами Евклида
где m > n > 0 взаимно просты и разной чётности. При m = 2, n = 1 получаем (3, 4, 5), при m = 3, n = 2 — (5, 12, 13).
Предел возможностей
Общего алгоритма для произвольных диофантовых уравнений не существует: это 10-я проблема Гильберта, отрицательно решённая Ю. В. Матиясевичем в 1970 году. А уравнение x^n + y^n = z^n при n > 2 не имеет решений в натуральных числах — Великая теорема Ферма, доказанная Эндрю Уайлсом в 1994 году.
Пять примеров: ax + by = c, линейное сравнение, ключ RSA, размен монет и пифагоровы тройки — с полной таблицей расширенного алгоритма Евклида. Открыть →
Вопросы для самопроверки
- Имеет ли решения уравнение 6x + 9y = 20?
Ответ
Нет: НОД(6, 9) = 3, а 20 на 3 не делится. - Найдите 11⁻¹ mod 26.
Ответ
26 = 2·11 + 4, 11 = 2·4 + 3, 4 = 3 + 1; обратно: 1 = 4 − 3 = 3·4 − 11 = 3·26 − 7·11, значит 11⁻¹ ≡ −7 ≡ 19 (11·19 = 209 = 8·26 + 1). - Какую наибольшую сумму нельзя набрать монетами 5 и 7?
Ответ
5·7 − 5 − 7 = 23.