Integer Factorization Algorithms
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.
Mathematics and Statistics
University of Sydney
Department of Computer Science
Computer Sciences Laboratory
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.
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