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:
“I conceive that the leading characteristic of the nineteenth century has been the rapid growth of the scientific spirit, the consequent application of scientific methods of investigation to all the problems with which the human mind is occupied, and the correlative rejection of traditional beliefs which have proved their incompetence to bear such investigation.”
—Thomas Henry Huxley (1825–95)
“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 application requisite to the duties of the office I hold [governor of Virginia] is so excessive, and the execution of them after all so imperfect, that I have determined to retire from it at the close of the present campaign.”
—Thomas Jefferson (1743–1826)