Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Open
Namchee opened this issue Dec 1, 2023 · 0 comments · May be fixed by #257
Open

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

Namchee opened this issue Dec 1, 2023 · 0 comments · May be fixed by #257

Comments

@Namchee
Copy link

Namchee commented Dec 1, 2023

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

@Namchee Namchee linked a pull request Dec 1, 2023 that will close this issue
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant