Ро-алгоритм Полларда: как факторизовать число до 10^18 за O(n^{1/4}) (обзор)?

Ро-Полларда ищет один нетривиальный делитель составного n за ожидаемое O(n^{1/4}). Идея — «парадокс дней рождения»: генерируем псевдослучайную последовательность x_{i+1} = (x_i^2 + c) mod n и считаем gcd(|x_i − x_j|, n). Если n имеет делитель p, то по модулю p последовательность зациклится примерно через O(sqrt p) ≈ O(n^{1/4}) шагов, и в этот момент gcd даст нетривиальный множитель.

using u64 = unsigned long long; using u128 = __uint128_t;
u64 mulmod(u64 a, u64 b, u64 m){ return (u128)a*b%m; }
u64 pollard(u64 n){
    if (n % 2 == 0) return 2;
    u64 x = rand() % n, y = x, c = rand() % n + 1, d = 1;
    while (d == 1) {
        x = (mulmod(x, x, n) + c) % n;
        y = (mulmod(y, y, n) + c) % n; y = (mulmod(y, y, n) + c) % n; // y идёт вдвое быстрее
        d = __gcd(x > y ? x - y : y - x, n);
    }
    return d == n ? pollard(n) : d; // неудача → перезапуск с новым c
}
void factor(u64 n, vector<u64>& f){
    if (n == 1) return;
    if (is_prime(n)) { f.push_back(n); return; }  // is_prime — Миллер-Рабин
    u64 d = pollard(n);
    factor(d, f); factor(n / d, f);
}

Схема рекурсивная: проверяем простоту тестом Миллера-Рабина; если простое — записываем; иначе находим делитель Поллардом и рекурсивно факторизуем обе части. Обязателен __uint128_t в mulmod. На практике для скорости часто накапливают произведение разностей и берут gcd пачками (Brent + батчинг), но базовая идея ровно такая.