Core Ideas
The rho algorithm is based on Floyd's cycle-finding algorithm and on the observation that (as in the birthday problem) two numbers x and y are congruent modulo p with probability 0.5 after numbers have been randomly chosen. If p is a factor of n, the integer we are aiming to factor, then since p divides both and .
The rho algorithm therefore uses a function modulo n as a generator of a pseudo-random sequence. It runs one sequence twice as "fast" as the other; i.e. for every iteration made by one copy of the sequence, the other copy makes two iterations. Let x be the current state of one sequence and y be the current state of the other. The GCD of |x − y| and n is taken at each step. If this GCD ever comes to n, then the algorithm terminates with failure, since this means x = y and therefore, by Floyd's cycle-finding algorithm, the sequence has cycled and continuing any further would only be repeating previous work.
Read more about this topic: Pollard's Rho Algorithm
Famous quotes containing the words core and/or ideas:
“For books are more than books, they are the life
The very heart and core of ages past,
The reason why men lived and worked and died,
The essence and quintessence of their lives.”
—Amy Lowell (1874–1925)
“Cities need old buildings so badly it is probably impossible for vigorous streets and districts to grow without them.... for really new ideas of any kind—no matter how ultimately profitable or otherwise successful some of them might prove to be—there is no leeway for such chancy trial, error and experimentation in the high-overhead economy of new construction. Old ideas can sometimes use new buildings. New ideas must use old buildings.”
—Jane Jacobs (b. 1916)