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)
“... two men could be just alike in all their dispositions to verbal behavior under all possible sensory stimulations, and yet the meanings or ideas expressed in their identically triggered and identically sounding utterances could diverge radically, for the two men, in a wide range of cases.”
—Willard Van Orman Quine (b. 1908)