in the real world
The rho methodTrial division searches for a prime divisor p of n by trying all primes in sequence: 2, 3, 5, 7, 11, 13, etc. Batch trial division speeds up handling many numbers n but still needs to enumerate all the small primes. There are about p/log p primes up to p.
The rho method finds a prime divisor p of n using only about sqrt(p) operations.
How it worksSage code first:
def rho(n): c = 10 a0 = 1 a1 = a0^2+c a2 = a1^2+c while gcd(n,a2-a1) == 1: a1 = (a1^2+c) % n a2 = (a2^2+c) % n a2 = (a2^2+c) % n g = gcd(n,a2-a1) return [g,n / g] # examples (second example is faster because prime is smaller): print rho(314159265358979323) # output: [990371647, 317213509] print rho(698599699288686665490308069057420138223871) # output: [2053, 340282366920938463463374607431768211507]
Now the explanation.
The rho method iterates the function lambda x: (x*x+10) mod p starting from 1, where p is a divisor of n. In other words, it starts from 1, squares, adds 10, reduces mod p, squares, adds 10, reduces mod p, etc.
You should object that we don't know p; the whole point is to find p. This objection is answered below.
(There's nothing special about the number 1: a random number would also work. There's almost nothing special about the number 10: most other numbers would work, although there are a few bad choices such as 0 and -2.)
The rho method continues iterating the function modulo p until it finds a collision: the same integer modulo p appearing twice. The birthday paradox suggests that this will happen in only about sqrt(p) steps. The rho method recognizes this collision in very little memory by Floyd's method: run another iteration at double speed and check at each step whether the single-speed and double-speed iterations (a1 and a2 in the code above) are at the same point.
The rho method actually performs computations mod n, which we do know, as a way to implicitly perform computations mod p. To check whether the single-speed and double-speed iterations are at the same point mod p, the rho method subtracts the results, computes a gcd with n, and checks whether this gcd is larger than 1. Of course, if the gcd is smaller than n then it is a nontrivial factor of n.
Version: This is version 2012.12.28 of the rho.html web page.