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:
“The threadbare trees, so poor and thin,
They are no wealthier than I;
But with as brave a core within
They rear their boughs to the October sky.
Poor knights they are which bravely wait
The charge of Winter’s cavalry,
Keeping a simple Roman state,
Discumbered of their Persian luxury.”
—Henry David Thoreau (1817–1862)
“Things perceived by the senses are immediately perceived by the senses; and things immediately perceived by the senses are ideas; and ideas cannot exist without the mind, their existence therefore consists in being perceived; when therefore they are actually perceived, there can be no doubt of their existence.”
—George Berkeley (1685–1753)