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 ideal of men and women sharing equally in parenting and working is a vision still. What would it be like if women and men were less different from each other, if our worlds were not so foreign? A male friend who shares daily parenting told me that he knows at his very core what his wife’s loving for their daughter feels like, and that this knowing creates a stronger bond between them.”
—Anonymous Mother. Ourselves and Our Children, by Boston Women’s Health Book Collective, ch. 6 (1978)
“Our ideas must be as broad as Nature if they are to interpret Nature.”
—Sir Arthur Conan Doyle (1859–1930)