page_title: Pollard's rho algorithm
section_title: Core ideas
hierarchical_section_title: Pollard's rho algorithm / Core ideas
caption_attribution_description: Nederlands: voorbeeld pollard rho cyckel
context_page_description: 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.
context_section_description: Suppose we need to factorize a number , where  is a non-trivial factor. A polynomial modulo , called  (e.g., ), is used to generate a pseudorandom sequence: A starting value, say 2, is chosen, and the sequence continues as , , , etc. The sequence is related to another sequence . Since  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 are finite, both the  sequence, which is mod , and  sequence will eventually repeat, even though we do not know the latter. Assume that the sequences behave like random numbers. Due to the birthday paradox, the number of  before a repetition occurs is expected to be , where  is the number of possible values. So the sequence  will likely repeat much earlier than the sequence . 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 character ρ when the values , , etc. are represented as nodes in a directed graph.
  This is detected by Floyd's cycle-finding algorithm: two nodes  and  (i.e.,  and ) 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 . If it is not 1, then this implies that there is a repetition in the  sequence (i.e. . This works because if the  is the same as , the difference between  and  is necessarily a multiple of . Although this always happens eventually, the resulting Greatest common divisor (GCD) is a divisor of  other than 1. This may be  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.
caption: Cycle diagram resembling the Greek letter ρ
exif: {}