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)
“The myth of motherhood as martyrdom has been bred into women, and behavioral scientists have helped embellish the myth with their ideas of correct “feminine” behavior. If women understand that they do not have to ignore their own needs and desires when they become mothers, that to be self-interested is not to be selfish, it will help them to avoid the trap of overattachment.”
—Grace Baruch (20th century)