Principal Investigator Richard P Brent Project k58

Research School of information Sciences and Engineering Machine VP


Integer Factorization Algorithms.

The security of computers and data networks is of great practical importance. Large composite numbers are often used to maintain security via "asymmetric" or "public key" cryptosystems. 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 VP2200 is 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 basic questions addressed?

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? How much can parallel computation decrease the time required for factorization?

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

The second phase developed for the elliptic curve algorithm improves the efficiency by a factor of 6 to 10, and both phases can be vectorized efficiently. Using a few minutes of VP2200 time it is routine to find prime factors of size up to 25 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). Run-times on a 128-processor AP1000 are comparable to those on the VP2200. These results imply that the composite numbers used in public-key cryptosystems should be considerably larger than 100 decimal digits. Applications to mathematics include results on the orders of certain finite groups and bounds on the size of odd perfect numbers. As a byproduct of testing factorization 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 and why is a supercomputer required?

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. For example, our recent factorization of the tenth Fermat number required 140 Mflop-years of computation. 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 such as the Fujitsu AP1000, DEC alpha farm, SGI Power Challenge, Fujitsu VPP500, and PCs or workstations with special hardware support.

Publications

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

Factorization of large integers on some vector and parallel computers, C. Eldershaw and R. P. Brent, Proceedings of Neural, Parallel and Scientific Computations 1, 143-148, (1995).

Integer factorization on the AP1000, C Eldershaw and R. P. Brent, Proceedings Parallel Computing Workshop 1995, Imperial College, London, 233-242. (1995)

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