Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Pollard's rho algorithm
Summary
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 smallest prime factor of the composite number being factorized.
The algorithm is used to factorize a number , where is a non-trivial factor. A polynomial modulo , called (e.g., ), is used to generate a pseudorandom sequence. It is important to note that must be a polynomial. 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 is finite, both the sequence, which is mod , and 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 before a repetition occurs would be expected to be , where is the number of possible values. So the sequence will likely repeat much earlier than the sequence . When one has found a such that but , the number is a multiple of , so has been found.
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 , , 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 .
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.