Integer Factorization Algorithms  
                 
Principal Investigator

Richard Brent

Research School of Information Sciences and Engineering and Oxford University

Co-Investigators

John Cannon

Mathematics and Statistics

University of Sydney

Brendan McKay

Computer Science

Brian Murphy

Research School of Information Sciences and Engineering

Projects

k58 - VPP, PC

With the growing use of the Internet for
commercial transactions, the security of
computers and data networks is of great importance. An important ingredient in maintaining this security is the use of cryptographic techniques such as "public key" cryptography. The most popular public key cryptosystem, the RSA system, depends on the difficulty of factoring a composite number which is the product of two or three large prime numbers. Someone who can factor large composite numbers can crack the system and modify or forge data on the network. On the other hand, if the numbers are too large the system will run too slowly. Thus, in order to choose the appropriate parameters for the cryptosystem, it is necessary 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. 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.
 
           
                 

   
                 

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

We have demonstrated improvements to the elliptic curve algorithm (ECM) which has been used to find factors of up to 53 decimal digits.

Murphy (PhD student, ANU) in collaboration with Montgomery (CWI, Amsterdam) has improved the polynomial selection phase of the number field sieve algorithm and used this to factor the 140-digit RSA challenge number. It now appears feasible to factor a 155-digit number.

These results imply that the composite numbers used in public-key cryptosystems should be considerably larger than 512 bits and have all their prime factors larger than 60 decimal digits.

                 
- Appendix A

                 

       

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 very large amount of computer time (at ANU and elsewhere), the database is now readily accessible from a personal computer or via the computer algebra package Magma (developed by Cannon at the University of Sydney). The database is regularly updated as new factors are found.

We intend to continue working on applications of integer factorization, and will try some new ideas for improving the efficiency of these algorithms. We also plan to experiment with algorithms for related problems, such as the problem of computing discrete logarithms over large finite fields, elliptic or hyper-elliptic curves.

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 programs used include a vectorized implementation of Lenstra's elliptic curve algorithm with a second phase which was developed at ANU, the Magma package and an implementation in Magma of the two-large prime multiple-polynomial quadratic sieve (PPMPQS) algorithm which was developed by collaborators at the University of Sydney, and an implementation of the number field sieve (NFS) algorithm which was developed mainly by collaborators at the Centre for Mathematics and Computer Science, Amsterdam.

Publications

R. P. Brent, Factorization of the tenth Fermat number, Mathematics of Computation, 68, 225 (Jan. 1999), 429-451.

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

B. A. Murphy and R. P. Brent, On quadratic polynomials for the number field sieve, Australian Computer Science Communications 20, 3 (1998), 199-213. Proceedings Fourth Australasian Theory Symposium (Xuemin Lin, ed.), Springer-Verlag Singapore, 1998, 199-213. ISBN 981-3083-92-1.

H. te Riele, S. Cavallar, B. Dodson, A. Lenstra, P. Leyland, W. Lioen, P. Montgomery, B. Murphy, and P. Zimmermann, Factorization of RSA-140 using the Number Field Sieve, electronic announcement, 4 Feb 1999.

See http://www.rsa.com/rsalabs/html/factoring.html.

       
Appendix A -