Global Sales Contact List

Contact   A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

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

Notes:
Connect with EMCConnect with EMC
Need help immediately? EMC Sales Specialists are standing by to answer your questions real time.
Use Live Chat for fast, direct access to EMC Customer Service Professionals to resolve your support questions.
Explore and compare EMC products in the EMC Store, and get a price quote from EMC or an EMC partner.
We're here to help. Send us your sales inquiry and an EMC Sales Specialist will get back to you within one business day.
Want to talk? Call us to speak with an EMC Sales Specialist live.