algorithmica-org/algorithmica

factorization: incomplete args for gcd function in Pollard-Rho algorithm

Namchee opened this issue · 0 comments

Overview

The Pollard-Rho algorithm in the Integer Factorization section is written as such

u64 f(u64 x, u64 mod) {
    return ((u128) x * x + 1) % mod;
}

u64 diff(u64 a, u64 b) {
    // a and b are unsigned and so is their difference, so we can't just call abs(a - b)
    return a > b ? a - b : b - a;
}

const u64 SEED = 42;

u64 find_factor(u64 n) {
    u64 x = SEED, y = SEED, g = 1;
    while (g == 1) {
        x = f(f(x, n), n); // advance x twice
        y = f(y, n);       // advance y once
        g = gcd(diff(x, y)); /* FOCUS ON THIS LINE */
    }
    return g;
}

It seems like in the line I've marked, the gcd is missing n that isn't the case in Pollard-Brent section