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

История алгоритма Евклида

Алгоритм Евклида — самый древний алгоритм в истории, описанный Евклидом в книге VII «Начал» около 300 г. до н.э. Используется до сих пор в чистом виде и во многих расширениях.

Основной принцип: НОД(a, b) = НОД(b, a mod b). Повторяя эту замену, мы за O(log min(a,b)) шагов приходим к ситуации, когда одно из чисел становится 0 — тогда другое и есть НОД.

Как работает алгоритм

function gcd(a, b): while b != 0: a, b = b, a mod b return a

Пример: НОД(48, 18).

1. 48 mod 18 = 12 → НОД(18, 12).
2. 18 mod 12 = 6 → НОД(12, 6).
3. 12 mod 6 = 0 → НОД(6, 0) = 6. Готово.

За 3 шага. Для числа в миллиарды нужно ~30 шагов (log₂ 10⁹ ≈ 30).

Расширенный алгоритм

Расширенный находит не только НОД, но и коэффициенты Безу x, y такие, что:

a · x + b · y = НОД(a, b)

function extended_gcd(a, b): if b == 0: return a, 1, 0 g, x1, y1 = extended_gcd(b, a mod b) x = y1 y = x1 - (a // b) * y1 return g, x, y

Используется в криптографии RSA, решении линейных диофантовых уравнений, нахождении обратного по модулю.

Применение алгоритма

• RSA-криптография: нахождение секретного ключа d = e⁻¹ mod φ(n).
• Сокращение дробей: 48/18 = (48/НОД)/(18/НОД) = 8/3.
• Линейные диофантовы уравнения: ax + by = c имеет решения тогда и только тогда, когда c кратно НОД(a, b).
• Музыка и ритм: гармонические интервалы — отношения частот, упрощённых через НОД.
• Распределение задач: «когда два автобуса встретятся снова?» — НОК(12, 18) = 12·18/НОД = 216/6 = 36 мин.
• Компьютерные сети: распределение IP-адресов, маски подсетей.
• Эллиптическая криптография: операции в конечных полях.