Review of methods for integer factorization applied to cryptography

Abstract

The problem of finding the prime factors of large composite numbers has always been of mathematical interest for centuries. With the advent of public key cryptosystems it is also of practical importance, because of the security of these cryptosystems, such as the Rivest-Shamir-Adleman (RSA) systems, depends on the difficulty of factoring the public-keys. In recent years the best known integer factorization algorithms have improved greatly, to the point where it is now easy to factor a 100-decimal digit number and possible to factor larger than 250 decimal digits, given the availability of enough computing power. However, the problem of integer factorization still appears difficult, both in a practical sense (for numbers of more than over 100 decimal digits), in a theoretical sense (because none of the algorithms run in polynomial time). In this study we will outline some useful and recent integer factorization algorithms, including the Elliptic Curve Algorithm (ECM), Quadratic Sieve (QS), Number Field Sieve (NFS) and finally give some example of their usage. © 2006 Asian Network for Scientific Information.