Pollard rho integer factorization

Question

I am trying to implement Pollard Rho integer factorization in C/C++.Google gives me a Java implementation of the problem here.

I don't know Java that well,so what I came up with this.My implemenation in C++ works for most cases but not in few like the one "9999", I used there.

I am aware that C++ didn't have Biginteger class so I can't have the full functionality as it gives in JAVA but I want to factorize 15 digits numbers that's sufficient for unsigned long long

Please point out what wrong in my implementation.

Answer 1

The problem's right here:

#define abs(x) (x>0)?(x):(-x)

You're missing some parentheses in your abs macro. Try:

#define abs(x) ((x)>0 ? (x) : -(x))

instead. (Consider what happens when abs(x-xx) is expanded in the case x-xx <= 0.)

Also, why does your gcd function return an int rather than a BigInteger?

You should also be aware that (assuming unsigned long long is a 64-bit integer type) this code won't work correctly for N larger than 2**32: if x (or xx) is greater than or equal to 2**32 then x*x will wrap modulo 2**64, giving you the wrong value for x*x % N.

Answer 2

I've spotted one difference: the Java code assigns c and x to be new BigInteger(N.bitLength(), random), whereas the C++ code uses rand() % N, which is a smaller random range. For the value 9999, the binary is 10011100001111, so the Java code will give c and x a maximum value of 16383.