## Integer Factorization Algorithms |
||||||

## Principal Investigator## Richard P. BrentResearch School of Information Sciences and Engineering |
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. |
|||||

## Projectsk58 - 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. ## PublicationsR. P. Brent, P. L. Montgomery and H. J. J. te Riele, R. P. Brent, Large factors found by ECM,R P Brent |
|||

## - Appendix A |
|||