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

Алгоритм Евклида: 300 год до н.э., и он прямо сейчас работает в OpenSSL при каждом TLS-рукопожатии. 2300 лет безупречной работы. Расширенная версия - основа генерации ключей RSA.

• OpenSSL, libsodium: RSA key generation использует extended gcd для нахождения d = e^(-1) mod phi(N)
• Python math.gcd: бинарный алгоритм Штейна - встроен в стандартную библиотеку
• Компьютерная алгебра (SymPy, Mathematica): gcd дробей - первый шаг каждой нормализации

Алгоритм Евклида: 2300 лет в строю

Алгоритм Евклида придуман около 300 года до н.э. и до сих пор работает в каждой криптобиблиотеке мира - OpenSSL, libsodium, Python's `math.gcd`. 2300 лет без единого патча.

**Наибольший общий делитель** gcd(a, b) - наибольшее число, делящее оба. Ключевое свойство, на котором стоит алгоритм:

Это позволяет заменять пару (a, b) на пару (b, a mod b) до тех пор, пока второй элемент не станет нулём. Последний ненулевой - gcd.

Алгоритм Евклида сходится за O(log min(a,b)) шагов - число шагов ограничено числами Фибоначчи (теорема Ламе, 1844). Число Фибоначчи f_n ~ phi^n / sqrt(5), поэтому log_phi(min(a,b)) шагов. На практике: gcd(10^18, 10^18 - 1) = 1 за ~90 шагов.

Расширенный Евклид и тождество Безу

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

Тождество Безу - ключ к структуре Z. Следствие: gcd(a,m) = 1 тогда и только тогда, когда a имеет обратный в Z/mZ. В RSA: нахождение d = e^(-1) mod phi(N) - это ровно одно применение расширенного алгоритма Евклида. Каждое установление TLS-соединения использует это.

Применения НОД: от дробей до криптографии

НОД встречается везде, где нужно приводить к общей мере или находить обратные элементы. Три главных применения в CS:

1. Сокращение дробей: a/b -> (a/g)/(b/g), g = gcd(a,b). В компьютерной алгебре (SymPy, Mathematica) - стандартный шаг нормализации.
2. Модульный обратный: d = e^(-1) mod phi(N) через расширенный Евклид - генерация ключей RSA.
3. Проверка разрешимости: ax ≡ c (mod m) разрешимо тогда и только тогда, когда gcd(a,m) | c.

math.gcd в Python использует бинарный алгоритм Штейна (быстрее классического Евклида на 20-40% из-за замены делений битовыми сдвигами). С Python 3.9: math.gcd принимает произвольное число аргументов: math.gcd(a, b, c) = gcd(gcd(a,b), c).

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

• gcd(a,b) = gcd(b, a mod b): Евклид сводит к меньшей паре за O(log min) шагов
• Тождество Безу: существуют x,y такие что ax + by = gcd(a,b)
• Расширенный Евклид находит x, y; если gcd=1, то x = a^(-1) mod b
• a^(-1) mod m существует <=> gcd(a,m) = 1
• ax ≡ c (mod m) разрешимо <=> gcd(a,m) | c; число решений = gcd(a,m) если разрешимо

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

НОД - фундамент теории делимости и криптографии:

• Разложение на множители — gcd через разложения: min степеней общих простых; Евклид быстрее
• НОК — lcm(a,b) = a*b / gcd(a,b) - все операции с НОК сводятся к НОД

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

• crypto-03-number-theory