1

I've read about factorization of integers into the prime factors and did a proof of concept implementation of Pollard's rho algorithm:

https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm

The algorithm is easy to implement, works so far. However it may (and does) fail for certain numbers. The Wikipedia page suggest to restart the algorithm using a different start condition or pick a random generator function.

That does not sound very deterministic to me. Is there an approach that guarantees that the algorithm will eventually terminate?

I know that the state of the art is the elliptic curve integer factorization, and I plan to implement it for laughs and giggles later. To do so I first need a prime factorization algorithm for small numbers though, that is why I have to deal with something like Pollards rho algorithm first.

Nils Pipenbrinck
  • 83,631
  • 31
  • 151
  • 221
  • 2
    "That does not sound very deterministic to me" Well it's a randomized algorithm. You just repeat with random starting values until you've reached a certain confidence level – Niklas B. Nov 16 '14 at 14:29
  • Please give an example of a number on which it fails. – user448810 Nov 16 '14 at 17:50
  • @user448810 With the algorithm implemented as the wikipedia pseudo-code (e.g. start value=2, g(x) = (x*2-1) mod n, the algorithm fails with the argument 49 (clearly the prime 7 is a factor). – Nils Pipenbrinck Nov 16 '14 at 17:56
  • The algorithm didn't fail. In fact, it found _two_ factors, 7 and 7, at the same time, so it returned their product, 7 * 7 = 49. Of course, that's not very helpful. – user448810 Nov 16 '14 at 18:08
  • @user448810 — The number 2609953993 fails with f(x) = x² + 1, but then succeeds with f(x) = x² + 2. – Todd Lehman Jun 06 '15 at 06:32
  • Sometimes the rho algorithm falls into a cycle before it finds a factor, and in that case you try again with a different random number generator. But that isn't a failure, it's the nature of the algorithm, and you did successfully factor your integer. – user448810 Jun 06 '15 at 12:41

0 Answers0