ABSTRACT
A proper understanding of this issue is extremely important for the real-world deployment of cryptosystems based on these problems. The goal is merely to give a taste of existing algorithms for these problems, as well as to provide some basic guidance for setting parameters in practice. The reader may also notice that we only describe algorithms for factoring and computing discrete logarithms, and not algorithms for, say, solving the RSA or decisional Diffie-Hellman problems. Pollard’s rho algorithm is better than trial division, but runs in exponential time. The quadratic sieve algorithm runs in sub-exponential time. It was the fastest known factoring algorithm until the early 1990s and remains the factoring algorithm of choice for numbers up to about 300 bits long. Understanding the best available algorithms for solving various cryptographic problems is essential for determining the appropriate key length for achieving a desired level of security.
