Application
The algorithm is very fast for numbers with small factors. For example, on a 3 GHz workstation, the original rho algorithm found the factor 274177 of the sixth Fermat number (18446744073709551617) in 26 milliseconds; the Richard Brent variant found the same factor in 5 milliseconds. However, for a semiprime of the same size (10023859281455311421), the same workstation using the original rho algorithm took 109 milliseconds to find a factor; the Richard Brent variant took 31 milliseconds.
For f, we choose a polynomial with integer coefficients. The most common ones are of the form:
The rho algorithm's most remarkable success has been the factorization of the eighth Fermat number by Pollard and Brent. They used Brent's variant of the algorithm, which found a previously unknown prime factor. The complete factorization of F8 took, in total, 2 hours on a UNIVAC 1100/42.
Read more about this topic: Pollard's Rho Algorithm
Famous quotes containing the word application:
“Science is intimately integrated with the whole social structure and cultural tradition. They mutually support one other—only in certain types of society can science flourish, and conversely without a continuous and healthy development and application of science such a society cannot function properly.”
—Talcott Parsons (1902–1979)
“The best political economy is the care and culture of men; for, in these crises, all are ruined except such as are proper individuals, capable of thought, and of new choice and the application of their talent to new labor.”
—Ralph Waldo Emerson (1803–1882)
“If you would be a favourite of your king, address yourself to his weaknesses. An application to his reason will seldom prove very successful.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)