CODEWITHSUNDEEP
algorithmfactorization
Tin Man
Tin Man

Reputation: 878

Does Pollard Rho not work for certain numbers?

I'm trying to implement Pollard Rho based on pseudocode I found on Wikipedia, but it doesn't appear to work for the numbers 4, 8, and 25, and I have no clue why.

Here's my code:

    long long x = initXY;
    long long y = initXY;
    long long d = 1;

    while (d == 1) {
        x = polynomialModN(x, n);
        y = polynomialModN(polynomialModN(y, n), n);

        d = gcd(labs(x - y), n);
    }
    if (d == n)
        return getFactor(n, initXY + 1);

    return d;

This is my polynomial function:

long long polynomialModN(long long x, long long n) {
    return (x * x + 1) % n;
}

And this is example pseudocode from Wikipedia:

x ← 2; y ← 2; d ← 1
while d = 1:
    x ← g(x)
    y ← g(g(y))
    d ← gcd(|x - y|, n)
if d = n: 
    return failure
else:
    return d

Only difference: I don't return failure but instead try different initializing variables, as Wikipedia also notes this:

Here x and y corresponds to x i {\displaystyle x_{i}} x_{i} and x j {\displaystyle x_{j}} x_{j} in the section about core idea. Note that this algorithm may fail to find a nontrivial factor even when n is composite. In that case, the method can be tried again, using a starting value other than 2 or a different g ( x ) {\displaystyle g(x)} g(x).

Does Pollard-Rho just not work for certain numbers? What are their characteristics? Or am I doing something wrong?

Upvotes: 5

Views: 2192

Answers (2)

Elliot Liu
Elliot Liu

Reputation: 9

Here, as x can be as big as n-1, the product in your polynomialModN function will overflow.

Upvotes: 0

user448810
user448810

Reputation: 17866

Pollard Rho does not work on even numbers. If you have an even number, first remove all factors of 2 before applying Pollard Rho to find the odd factors.

Pollard Rho properly factors 25, but it finds both factors of 5 at the same time, so it returns a factor of 25. That's correct, but not useful. So Pollard Rho will not find the factors of any power (square, cube, and so on).

Although I didn't run it, your Pollard Rho function looks okay. Wikipedia's advice to change the starting point might work, but generally doesn't. It is better, as Wikipedia also suggests, to change the random function g. The easiest way to do that is to increase the addend; instead of x²+1, use x²+c, where c is initially 1 and increases to 2, 3, … after each failure.

Upvotes: 4

Related Questions