factorization: incomplete args for gcd function in Pollard-Rho algorithm
Namchee opened this issue · 0 comments
Namchee commented
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