Practical Prime Factorization

143 views Asked by At

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.

0

There are 0 answers