Pollard's rho algorithm
Algoritmo rho de Pollard
- Date
- 1975 · confidence high
- Place
- Cambridge, England, United Kingdom
- Credited to
- John M. Pollard
- Field
- Knowledge & symbols
What it is
Probabilistic integer-factorization algorithm devised by John Pollard, using very little memory, whose expected running time depends on the square root of the smallest prime factor of the composite number.
What it led to
- Efficient factorization methods used in cryptanalysis
- Variants such as Pollard's rho algorithm for the discrete logarithm
- Practical assessment of the security of small RSA keys
- Boost to research in computational number-theoretic algorithms