Алгоритм Евклида и НОД

2012 год. Команда криптографов просканировала 7 миллионов RSA-ключей из реального интернета. Нашли: примерно 27 000 серверов имели уязвимые ключи. Не потому что алгоритм RSA плохой. Потому что генераторы случайных чисел на этих серверах оказались слабыми, и два разных ключа иногда делили один и тот же простой множитель. Один запуск алгоритма Евклида - gcd(n1, n2) - и приватный ключ восстанавливался мгновенно. Алгоритм, описанный в «Началах» Евклида в 300 году до н.э., стал инструментом атаки на современное шифрование.

• **RSA-ключ**: закрытый ключ d вычисляется через расширенный алгоритм Евклида (e*d ≡ 1 mod phi(n)). Без Евклида - нет RSA, нет HTTPS
• **Атака через НОД**: в 2012 году 0.2% реальных RSA-ключей ломались одним вызовом gcd() из-за слабых генераторов случайных чисел на серверах
• **Размер батча в ML**: lcm размеров батча и числа аугментаций определяет, делится ли датасет без остатка - практическая задача при обучении нейросетей
• **Python math.gcd**: стандартная библиотека использует двоичный алгоритм НОД (быстрее на процессорах без деления), основанный на тех же принципах

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

• Делимость и простые числа

НОД и алгоритм Евклида

В 2012 году исследователи Надя Хенингер и соавторы прошлись по 7 миллионам RSA-ключей из HTTPS-серверов и нашли 0.2% с общим простым множителем. Один вызов алгоритма Евклида - и шифрование 27 000 серверов ломалось за миллисекунды. Не взломом, не брутфорсом. Просто НОД двух публичных ключей оказывался больше 1.

Наибольший общий делитель двух чисел - максимальное натуральное, на которое оба делятся без остатка. Наивный подход: разложить оба числа на простые, взять общие. Работает для маленьких чисел. Для 600-значных - нет: факторизация занимает дольше, чем существует Вселенная. Алгоритм Евклида обходит факторизацию полностью.

**Алгоритм Евклида:** gcd(a, b) = gcd(b, a mod b), база: gcd(a, 0) = a. Обоснование: a mod b = a - floor(a/b)*b. Любой общий делитель a и b делит и a mod b. Значит, множества общих делителей {a, b} и {b, a mod b} совпадают - gcd одинаков. **Сложность:** O(log(min(a, b))) - не более 5 x (число цифр меньшего числа) шагов (теорема Ламе, 1844).

Теорема Ламе (1844) - первый в истории анализ сложности алгоритма: число шагов Евклида для gcd(a, b) не превышает 5 * (количество десятичных цифр меньшего числа). Наихудший случай - пара последовательных чисел Фибоначчи: gcd(F_n, F_{n-1}) делает ровно n-2 деления, каждый раз остаток - предыдущее число Фибоначчи.

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

Обычный алгоритм Евклида отвечает на вопрос «чему равен НОД». Расширенный идёт дальше: он находит целые коэффициенты x и y такие, что ax + by = gcd(a, b). Зачем? В RSA для нахождения закрытого ключа d нужно решить уравнение e*d ≡ 1 (mod φ(n)). Это линейное сравнение - и расширенный Евклид решает его за O(log n).

**Расширенный алгоритм Евклида:** находит (g, x, y): ax + by = g = gcd(a, b). Идея: «раскручиваем» обычный Евклид назад, выражая каждый остаток через a и b. Та же сложность O(log n) - дополнительно хранятся только два коэффициента.

Функция mod_inverse выше - это буквально операция, которую вызывает OpenSSL при генерации RSA-ключа. Число e (обычно 65537) и phi(n) - два числа по 600+ цифр. Расширенный Евклид находит d за ~2000 шагов. Без него RSA не работал бы: нет эффективного алгоритма для модулярного обратного без тождества Безу.

Тождество Безу

Тождество Безу - теоретическое объяснение того, почему расширенный Евклид всегда находит решение. Для любых целых a и b (не оба нулевые) существуют целые x и y такие, что ax + by = gcd(a, b). Более того, gcd(a, b) - наименьшее положительное число, которое можно представить как ax + by при целых x, y.

**Тождество Безу:** для любых a, b in Z (не оба = 0): exists x, y in Z : ax + by = gcd(a, b) **Следствие 1:** a и b взаимно просты <=> exists x, y : ax + by = 1 **Следствие 2:** уравнение ax + by = c имеет целое решение <=> gcd(a, b) | c

Связь с RSA прямая. При генерации ключа выбирают e (обычно 65537) и вычисляют phi(n). Нужно найти d: e*d = 1 + k*phi(n), то есть e*d - phi(n)*k = 1. По следствию 1 тождества Безу, это разрешимо тогда и только тогда, когда gcd(e, phi(n)) = 1. Именно поэтому e выбирают простым - чтобы гарантировать взаимную простоту с phi(n).

НОК и связь с НОД

Наименьшее общее кратное (НОК, LCM) - минимальное натуральное, которое делится на оба числа. Связь с НОД: lcm(a, b) * gcd(a, b) = a * b. Это не случайность - НОД берёт минимум степеней простых, НОК берёт максимум; а сумма минимума и максимума равна сумме исходных степеней.

**НОК (LCM):** lcm(a, b) = наименьшее натуральное, кратное и a, и b. **Связь с НОД:** lcm(a, b) * gcd(a, b) = a * b Интуиция через факторизацию: 12 = 2^2 * 3^1, 18 = 2^1 * 3^2 gcd = 2^min(2,1) * 3^min(1,2) = 2^1 * 3^1 = 6 (берём минимумы) lcm = 2^max(2,1) * 3^max(1,2) = 2^2 * 3^2 = 36 (берём максимумы) gcd * lcm = 6 * 36 = 216 = 12 * 18 checkmark

В ML НОК появляется неожиданно: при подборе размера батча. Если датасет из 10080 примеров, а батч должен быть кратен и 32 (для тензорных ядер GPU), и 9 (для группы из 9 аугментаций) - нужен lcm(32, 9) = 288. Неправильный выбор оставляет «хвост» меньше батча, который либо выбрасывается, либо требует специальной обработки.

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

• **Алгоритм Евклида:** gcd(a, b) = gcd(b, a mod b), O(log n) - обходит факторизацию полностью
• **Расширенный Евклид:** находит целые x, y : ax + by = gcd(a, b) - основа для вычисления модулярного обратного
• **Тождество Безу:** ax + by = c разрешимо в целых <=> gcd(a, b) делит c - криптографический фундамент RSA
• **НОК через НОД:** lcm(a,b) = a*b / gcd(a,b); НОД берёт минимум степеней простых, НОК - максимум

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

НОД и тождество Безу - фундамент для:

• Делимость и простые числа — НОД через разложение: gcd = произведение общих простых в минимальных степенях
• Модулярная арифметика — Обратный элемент a^{-1} mod n существует <=> gcd(a,n) = 1 и находится через расширенный Евклид
• Малая теорема Ферма — Даёт альтернативный способ вычислить обратный элемент через быстрое возведение в степень

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

• Почему наихудший случай алгоритма Евклида - именно числа Фибоначчи? Что делает их «трудными» для Евклида?
• Алгоритм Евклида обобщается на полиномы: gcd(p(x), q(x)) находится аналогично делению полиномов с остатком. Что это даёт в компьютерной алгебре и символьных вычислениях?
• В атаке 2012 года слабость была не в RSA, а в генераторах случайных чисел. Какие требования к ГПСЧ вытекают из этой атаки, и почему криптографические ГПСЧ устроены иначе, чем обычные?

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

• nt-01 — Делимость - фундамент для понимания НОД
• nt-03 — Обратный элемент mod n строится через расширенный Евклид
• nt-04 — Малая теорема Ферма применяется вместе с алгоритмом Евклида в RSA
• alg-01-big-o — O(log n) Евклида - эталон логарифмической сложности
• alg-10-binary-search