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:
“Individual science fiction stories may seem as trivial as ever to the blinder critics and philosophers of today—but the core of science fiction, its essence ... has become crucial to our salvation if we are to be saved at all.”
—Isaac Asimov (1920–1992)
“Although all new ideas are born in France, they are not readily adopted there. It seems that they must first commence to prosper in a foreign country.”
—Sarah Bernhardt (1845–1923)