Integer Factorization Algorithms

           

Principal Investigator

Richard P. Brent

Research School of Information Sciences and Engineering

 

With the growing use of the Internet for commercial transactions, the security of computers and data networks is of great importance. Large composite numbers are often used to maintain security via "asymmetric" or "public key" cryptosystems such as the RSA system. The security depends on the difficulty of factoring a composite number which is the product of two large prime numbers. Someone who can factor large composite numbers can crack the encryption system. Thus it is important to know how difficult the integer factorization problem is. Although we can not answer this question with certainty, we do know how good certain approaches to the factorization problem are, and we can generate composite numbers for use in cryptosystems with a reasonable degree of confidence that they will be secure for the next few years. Because computers and factorization algorithms keep improving, a system which is secure today may be insecure in five years time. The VPP300 and SGI PC are being used to test and improve new integer factorization algorithms, and to apply these algorithms to obtain factorizations required for various applications in mathematics.

Determining:

a) how does the time required for factorization depend on the size of the number being factored, the size of its factors, and any special properties of the number, and

b) how much can parallel computation decrease the time required for factorization,

are of fundamental interest.

 
   

Projects

k58 - VPP, PC

   
   
         

 

What are the results to date and the future of the work?

The second phase developed for the elliptic curve algorithm improves the efficiency by a factor of about 8, and both phases can be vectorized efficiently. Using a few minutes of VPP300 time it is routine to find prime factors of size up to 28 decimal digits, and with more time and a certain amount of luck even larger factors can be found (factors of up to 43 decimal digits have been found). These results imply that the composite numbers used in public-key cryptosystems should have prime factors considerably larger than 50 decimal digits. Applications to mathematics include results on the orders of certain finite groups and information on the


           

           

     

structure of finite fields. As a byproduct of testing the algorithms a large database of factors has been built up. Although the computation of this database required a large amount of computer time, it is now readily accessible from a personal computer or via the computer algebra package Magma. The database is regularly updated as new factors are found, and the updates may be obtained by electronic file transfer (ftp). We intend to continue working on applications of integer factorization, and try new ideas for improving the efficiency of the factorization algorithms.

What computational techniques are used?

The numbers of interest in cryptography and some other applications such as analysis of very long period random number generators are very large, so a large amount of computation is required, even when the most efficient algorithms are used. The techniques used are a vectorized implementation of Lenstras elliptic curve algorithm with a second phase which was developed at ANU, and an implementation of the multiple-polynomial quadratic sieve (MPQS) algorithm which was developed at the Centre for Mathematics and Computer Science, Amsterdam.

We are also experimenting with other algorithms, such as the number field sieve (NFS) algorithm; and implementations on other high-performance computers and on PCs or workstations with special hardware support.

Publications

R. P. Brent, P. L. Montgomery and H. J. J. te Riele, Factorizations of a^n +- 1, 13 <= a < 100: Update 2, Report NM-R9609, CWI, Amsterdam, March 1996.

R. P. Brent, Factorization of the tenth and eleventh Fermat numbers, Report TR-CS-96-02, Computer Sciences Laboratory, ANU, February 1996.

Large factors found by ECM,R P Brent available from ftp://nimbus.anu.edu.au/pub/Brent/champs.ecm .

     

- Appendix A