The pollard rho is a factorization algorithm that's fairly simple to implement, as well as efficient. The algorithm works by choosing a function in Z mod n, and a starting value x sub 1. We successivly compute x sub i=f(x sub i-1). Let d be a divisor of n. Eventually some x sub i will be congruent to x sub j mod d, and so d divides x sub i minus x sub j, and gcd of x sub i minus x sub j and n could be a factor of n.

Log in or register to write something here or to contact authors.