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)
“Modesty and taste are questions of latitude and education; the more people know,—the more their ideas are expanded by travel, experience, and observation,—the less easily they are shocked. The narrowness and bigotry of women are the result of their circumscribed sphere of thought and action.”
—Elizabeth Cady Stanton (1815–1902)