RSA Laboratories

2.3.4 What are the best factoring methods in use today?

Factoring is a very active field of research among mathematicians and computer scientists; the best factoring algorithms are mentioned below with some references and their big-O asymptotic efficiencies; O-notation refers to the upper bound on the asymptotic running time of an algorithm [CLR90]; a brief description is given in Section A.7. For textbook treatment of factoring algorithms, see [Knu81] [Kob94] [LL90] [Bre89].

Factoring algorithms come in two flavors, special purpose and general purpose; the efficiency of the former depends on the unknown factors, whereas the efficiency of the latter depends on the number to be factored. Special-purpose algorithms are best for factoring numbers with small factors, but the numbers used for the modulus in the RSA cryptosystem do not have any small factors. Therefore, general-purpose factoring algorithms are the more important ones in the context of cryptographic systems and their security.

Special-purpose factoring algorithms include the Pollard rho method [Pol75], with expected running time O(Öp), and the Pollard p-1 method [Pol74], with running time O(p¢), where p¢ is the largest prime factor of p-1. The Pollard p+1 method is also a special purpose factoring algorithm, with running time O(p¢), where p¢ is the largest prime factor of p+1. All of these take an amount of time that is exponential in the size (bit length) of p, the prime factor that they find; thus these algorithms are too slow for most factoring jobs. The elliptic curve method (ECM) [Len87] is superior to these; its asymptotic running time is O(eÖ{2(lnp)(lnlnp)}). The ECM is often used in practice to find factors of randomly generated numbers; it is not fast enough to factor a large modulus of the kind used in the RSA cryptosystem.

The best general-purpose factoring algorithm today is the Number Field Sieve (NFS) [BLP94] [BLZ94], which runs in time approximately O(e1.9(lnn)1/3(lnlnn)2/3). Previously, the most widely used general-purpose algorithm was the Multiple Polynomial Quadratic Sieve (MPQS) [Sil87], which has running time O(e(lnn)1/2(lnlnn)1/2).

Recent improvements to the Number Field Sieve make the NFS more efficient than MPQS in factoring numbers larger than about 115 digits [DL95], while MPQS is better for small integers. While RSA-129 (see Question 2.3.6) was factored using a variation of MPQS, a variant of the NFS was used in the recent factoring of RSA-155 (a 155-digit number). It is now estimated that if the NFS had been used for RSA-129, it would have taken one quarter of the time. Clearly, NFS has overtaken MPQS as the most widely used factoring algorithm.

A "general number" is one with no special form that might make it easier to factor; moduli used in the RSA cryptosystem are created to be general numbers. A number being of a "special form" means generally that there is an easy way of expressing it. For example, the number might be a Fermat number, which means that it is equal to 22n + 1 for some integer n. The Cunningham Project [BLS88] keeps track of the factorizations of numbers with special forms and maintains a "10 Most Wanted" list of desired factorizations. A good way to survey current factoring capability of "general numbers" is to look at recent results of the RSA Factoring Challenge (see Question 2.3.6).

Top of the page