javac++cmathfactorization

Pollard rho integer factorization

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.

Solution

  • 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.