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:
“In the core of God’s abysm,—
Was a weed of self and schism;
And ever the Daemonic Love
Is the ancestor of wars,
And the parent of remorse.”
—Ralph Waldo Emerson (1803–1882)
“Harvey, Jr.: I was afraid something like this would happen. Being around all those young students was bound to give Father ideas.
Laura: Young ideas, nuts. They’re the oldest ideas in the world.”
—Tom Waldman (d. 1985)