Кратко и по делу — два подхода и их сравнение.
1) Алгоритм Евклида (и его практичные варианты)
- Идея: итеративно заменяем пару $(a,b)$ на $(b,a\mathrm{mod}b)$ пока второй не станет нулём; результат — первый.
- Улучшения: бинарный GCD (Stein), Лехмер (Lehmer) — обрабатывает старшие цифры чтобы сократить стоимость делений, half‑GCD / divide‑and‑conquer для субквадратичной асимптотики, использование быстрого умножения.
- Теоретическая сложность (для двух чисел длины $n$ бит):
- пусть $M(n)$ — стоимость умножения/деления для $n$-бит; тогда сложность быстрого GCD с half‑GCD: $O(M(n)\log n)$.
- при наивном умножении $M(n)=O(n^2)$ это даёт примерно $O(n^2\log n)$ (практически часто оценивают как $\approx O(n^2)$ с малыми лог‑факторами).
- число шагов деления в худшем случае — $O(n)$ (последовательность Фибоначчи даёт худший пример).
- Практика: очень быстрый; для случайных 1024–4096‑бит чисел библиотеки вычисляют GCD за миллисекунды — секунды на обычном железе. Используются Lehmer/half‑GCD + быстрые умножения.
2) Подход через факторизацию
- Идея: полностью факторизовать $a$ и $b$, взять пересечение простых множителей и их минимальные степени.
- Теоретическая сложность: сложность факторизации доминирует. Для больших общих целых без специальных свойств лучший алгоритм — GNFS (General Number Field Sieve) с субэкспоненциальной сложностью
$$L_n[1/3,c]=\exp ((c+o(1))(\log n{)}^{1/3}(\log \log n{)}^{2/3}),$$ где $n$ — само число (или его значение), обычно выражают сложность в зависимости от величины числа; это существенно хуже полиномиальной в длине представления.
- На практике: факторизация больших (например, криптографических) чисел размером $1024$–$4096$ бит практически неосуществима; факторизация годами/сотнями машин требует только для специально выбранных рекордов. Если число имеет очень маленький простой множитель, то быстрые методы (Pollard‑Rho и т. п.) могут вернуть фактор быстро, но в общем случае дорого.
3) Сравнение (теория и практика)
- Асимптотика: Euclid (с half‑GCD и быстрым умножением) — полиномиальная/почти‑квазилинейная в битовой длине: $O(M(n)\log n)$. Факторизация — суб‑экспоненциальная (GNFS): $L[\frac{1}{3},c]$. Для больших $n$ факторизация асимптотически значительно медленнее.
- Практика: для любых больших случайных целых GCD через Евклид — тривиальная операция. Подход через факторизацию применим только если числа малы или имеют очень маленькие/специальные простые делители; в общем случае факторизация нерентабельна.
- Исключения/нюансы: если вы заранее знаете, что числа имеют специальную структуру (малые простые множители, гладкие и т.п.), факторизация может быть конкурентоспособна. Также в теории квантовые алгоритмы (Shor) факторизуют за полиномиальное время — тогда факторизация и GCD будут одинаково дешёвы на квантовых компьютерах; но это пока не практично.
Вывод: для нахождения НОД больших целых используйте алгоритм Евклида (в современных реализациях — Lehmer/half‑GCD с быстрым умножением). Факторизация как метод вычисления НОД теоретически и практически существенно хуже для общих больших чисел.