Коротко: для вычисления НОД двух больших целых чисел почти всегда принципиально выгоднее использовать алгоритм Евклида (и его улучшения). Метод через факторизацию оправдан лишь в узких случаях (малые числа, заранее известные/малые простые множители, необходимость самих факторов), иначе факторизация гораздо дороже и нестабильна по времени.
Пояснения и сравнение.
1) Сложность (битовая, пусть $n$ — число битов входного числа, $M(n)$ — сложность умножения):
- Алгоритм Евклида (с улучшениями: Левмер, бинарный ГЦД, быстрые деления) реализуется за время примерно $O(M(n)\log n)$. При классическом умножении $M(n)=O(n^2)$ даёт ориентировочно $O(n^2\log n)$. Алгоритм прост, детерминирован, в худшем случае число шагов линейно по числу цифр, но каждая итерация работает на больших словах и может быть ускорена.
- Через факторизацию: общая задача факторизации имеет субэкспоненциальную сложность; для общего числа $N$ лучшая классическая схема — GNFS — даёт время
$$L_N[1/3,c]=\exp ((c+o(1))(\log N{)}^{1/3}(\log \log N{)}^{2/3}),$$ где $c=(64/9{)}^{1/3}$. В битах $n={\log }_{2}N$ это экспоненциально хуже, чем полиномиальные/квазиполиномиальные оценки для Евклида. Другие методы: перебор делителей $O(\sqrt{N})$, Pollard‑rho ~$O(N^{1/4})$ в среднем, ECM хорош для нахождения небольших простых множителей, но общий факторизационный ответ остаётся дорогостоящим и сильно зависит от структуры числа.
2) Практическая устойчивость к большим входным данным:
- Евклид: очень хорошо масштабируется — легко работает с числами в несколько тысяч бит; требует мало памяти; время предсказуемо и невелико даже для криптографических размеров ($1024$-$4096$ бит). Есть эффективные реализации (Левмер для уменьшения дорогих делений, алгоритмы с быстрым делением).
- Факторизация: крайне неустойчива — время может варьировать от быстрого (если есть маленький фактор) до практически бесконечного при больших простых множителях; для RSA‑размеров ($2048$ бит и выше) факторизация невыполнима в разумное время на классическом оборудовании.
3) Когда выбирать факторизацию:
- Нужны сами простые множители (не только НОД).
- Числа малы ($<64$ бит) или сильно «гладкие» (много маленьких простых делителей).
- Есть массированная параллельная инфраструктура и задача факторизовать много чисел (возможна распараллеливаемая обработка, но всё равно дорого).
- Спецструктуры чисел (напр., числа вида $a^k\pm b^k$) допускают специализированные быстрые методы.
4) Практические замечания:
- Для вычисления НОД большого количества чисел используют дерево НОД или последовательный Евклид; это быстрее и проще, чем факторизация каждого.
- Если подозреваете общий маленький простой множитель — сначала пробные деления по малым простым, затем Евклид; для обнаружения среднего размера фактора можно применить ECM, но это уже факторизация частичного характера.
- На практике: НОД двух случайных больших чисел вычисляется Евклидом за миллисекунды—секунды; факторизация тех же чисел может быть невозможна.
Вывод: алгоритм Евклида (и его оптимизации) — универсально лучший выбор для НОД больших целых. Метод факторизации выгоден только при дополнительных требованиях (нужны факторы) или при специальной структуре/малых размерах входа.