Pollard's rho algorithm
Pollard's rho algorithm is an algorithm for integer factorization. It was invented by John Pollard in 1975. It uses only a small amount of space, and its expected running time is proportional to the square root of the size of the smallest prime factor of the composite number being factorized. Core ideas. The algorithm is used to factorize a number formula_1, where formula_2 is a non-trivial factor. A polynomial modulo formula_3, called formula_4 (e.g., formula_5), is used to generate a pseudorandom sequence: A starting value, say 2, is chosen, and the sequence continues as  formula_6, formula_7, formula_8, etc. The sequence is related to another sequence formula_9. Since formula_2 is not known beforehand, this sequence cannot be explicitly computed in the algorithm. Yet, in it lies the core idea of the algorithm. Because the number of possible values for these sequences is finite, both the formula_11 sequence, which is mod formula_3, and formula_9 sequence will eventually repeat, even though these values are unknown. If the sequences were to behave like random numbers, the birthday paradox implies that the number of formula_14 before a repetition occurs would be expected to be formula_15, where formula_16 is  the number of possible values. So the sequence formula_9 will likely repeat much earlier than the sequence formula_11. Once a sequence has a repeated value, the sequence will cycle, because each value depends only on the one before it. This structure of eventual cycling gives rise to the name "rho algorithm", owing to similarity to the shape of the Greek letter "ρ" when the values formula_19, formula_20, etc. are represented as nodes in a directed graph. This is detected by Floyd's cycle-finding algorithm: two nodes formula_21 and formula_22 (i.e., formula_23 and formula_24) are kept. In each step, one  moves to the next node in the sequence and the other moves forward by two nodes. After that, it is checked whether formula_25. If it is not 1, then this implies that there is a repetition in the formula_9 sequence (i.e. formula_27. This works because if the formula_23 is the same as formula_24, the difference between formula_23 and formula_24 is necessarily a multiple of formula_2. Although this always happens eventually, the resulting greatest common divisor (GCD) is a divisor of formula_3 other than 1. This may be formula_3 itself, since the two sequences might repeat at the same time. In  this (uncommon) case the algorithm fails, and can be repeated with a different parameter. Algorithm. The algorithm takes as its inputs , the integer to be factored; and , a polynomial in computed modulo . In the original algorithm, formula_35, but nowadays it is more common to use formula_5. The output is either a non-trivial factor of , or failure. It performs the following steps: Here and corresponds to and in the previous section. Note that this algorithm may fail to find a nontrivial factor even when is composite. In that case, the method can be tried again, using a starting value other  than 2 or a different . Example factorization. Let formula_37 and formula_38. 97 is a non-trivial factor of 8051. Starting values other than may give the cofactor (83) instead of 97. One extra iteration is shown above to make it clear that moves twice as fast as . Note that even after a repetition, the GCD can return to 1. Variants. In 1980, Richard Brent published a faster variant of the rho algorithm. He used the same core ideas as Pollard but a different method of cycle detection, replacing Floyd's cycle-finding algorithm with the related Brent's cycle finding  method. A further improvement was made by Pollard and Brent. They observed that if formula_39, then also formula_40 for any positive integer . In particular, instead of computing formula_41 at every step, it suffices to define as the product of 100 consecutive formula_42 terms modulo , and then compute a single formula_43. A major speed up results as 100 steps are replaced with 99 multiplications modulo and a single . Occasionally it may cause the algorithm to fail by introducing a repeated factor, for instance when is a square. But it then suffices to go back to the previous term, where formula_44, and  use the regular "ρ" algorithm from there. Application. The algorithm is very fast for numbers with small factors, but slower in cases where all factors are large. The "ρ" algorithm's most remarkable success was the 1980 factorization of the Fermat number = 1238926361552897 × 93461639715357977769163558199606896584051237541638188580280321. The "ρ" algorithm was a good choice for because the prime factor = 1238926361552897 is much smaller than the other factor. The factorization took 2 hours on a UNIVAC 1100/42. Example: factoring = 10403 = 101 · 103. In following table shows numbers produced by the algorithm, starting with formula_45 and using the polynomial formula_46 . The third and fourth columns of the table contain additional information not known by the algorithm. They are included to show how the algorithm works. The first repetition modulo 101 is 97 which occurs in step 17. The repetition is not detected until step 23, when formula_47. This causes formula_48 to be formula_49, and a factor is found. Complexity. If the pseudorandom number formula_50 occurring in the Pollard "ρ" algorithm were an actual random number, it would follow that success would be achieved half the time, by the Birthday paradox in formula_51 iterations. It is believed that the same analysis  applies as well to the actual rho algorithm, but this is a heuristic claim, and rigorous analysis of the algorithm remains open.