Integer Factorization Algorithms
             

Principal Investigator

Richard Brent

Computer Science Laboratory, Research School of Information Sciences and Engineering, and Oxford University

Would you put your credit card details on the Internet ? With the growing use of the Internet for commercial transactions, the security of computers and data networks is of great importance. A vital ingredient in maintaining this security is the use of cryptographic techniques such as "public key" cryptography. The most popular public key cryptosystem 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 system and modify or forge data on the network. Thus it is vitally 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. Beceause 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.
 

Co-Investigators

     

John Cannon

Mathematics and Statistics

University of Sydney

Brendan McKay

Department of Computer Science

Computer Sciences Laboratory

      

Projects

k58 - VPP,PC

      
           

 

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

We have demonstrated improvements to the elliptic curve algorithm (ECM) and used it to find factors of up to 48 decimal places (5 digits more than a year ago). Currently our program holds the world record for the largest factor found by ECM, although we do not expect this record to last for long.

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 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 collaborators at the University of Sydney). The database is regularly updated as new factors are found.
             
Appendix A -
             
     

We intend to continue working on applications of integer factorization, and will try new ideas for improving the efficiency of these algorithms, such as improved polynomial selection strategies in the number field sieve algorithm (NFS). We also plan to experiment with algorithms for related problems, such as the problem of computing discrete logarithms over large finite fields, elliptic curves 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 techniques used are a vectorized implementation of Lenstra's elliptic curve algorithm with a second phase which was developed at ANU, an implementation of the two-large-prime multiple-polynomial quadratic sieve (PPMPQS) which was developed mainly by collaborators at the University of Sydney, and an implementation of the number field sieve (NFS) 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, 1998, to appear.

R. P. Brent, R. E. Crandall, K. Dilcher, Two new factors of Fermat numbers, Report TR-CS-97-11, CS Lab, ANU, 7 pp May 1997 (revision submitted for publication).

R. P. Brent, P. L. Montgomery, H. J. J. te Riele, Factorizations of a^n +- 1, 13 <= a < 100: Update 3, CWI, Amsterdam, 1998, to appear.

B. A. Murphy, R. P. Brent, On quadratic polynomials for the number field sieve, Australian Computer Science Communications 20, 3 (1998), 199-213. Also Report TR-CS-97-17, CSL, ANU, August 1997, 18 pp.
     
- Appendix A