Pollard's rho algorithm is an algorithm for integer factorization, 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.
Facts
Time Complexity
Time Complexity (category)Sub-Linear / Root Time -- O(sqrt n) 1 Connections
Associated With
Verified en.wikipedia.org/wiki/Baby-step_giant-step: "Alternatively one can use Pollard's rho algorithm for logarithms, which has about the same running time as the baby-step giant-step algorithm, but only a small memory requirement."
In Field
Source Pollard's rho algorithm (Wikipedia)
Sources
1. Wikidata: Pollard's Rho Algorithm
Wikidata Q946489, class allow-list match (w-wdresolver-0926)View the Source Pollard's rho algorithm (Wikipedia)
In Field: Algorithms and Complexity Theory, Lead sentenceQuote, In Field: Algorithms and Complexity Theory, Lead sentence
Pollard's rho algorithm is an algorithm for integer factorization.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.