Principal Investigator Richard P Brent Project k58

Research School of Information Sciences and Engineering Machine VP

Integer Factorization Algorithms

Large composite numbers are used to maintain the security of computers and data networks via `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. No one can answer this question with certainty, but 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. Unfortunately (or fortunately, depending on your point of view), computers and factorization algorithms keep improving, so 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 (e.g. its proximity to a power of a small prime)? Can parallel computation effectively decrease the time required for factorization?

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 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 (several of 35 or more 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 larger than 100 decimal digits. Applications to mathematics include new 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. 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. We are also comparing implementations of the algorithms on the VP2200 with implementations on other high-performance computers such as the Fujitsu AP1000 and VPP500 and on PCs or workstations with special hardware support.

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.

The techniques used are a vectorized implementation of Lenstra's 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 machines, such as the Fujitsu AP1000 and an IBM PC with a special board designed to speed up multiple-precision operations.

Publications

Update 1 to Factorizations of a^n +- 1, 13 <= a < 100, R P Brent, P L Montgomery and H J J te Riele, Report NM-R9419, 46 pp., CWI, Amsterdam, September 1994.

On the periods of generalized Fibonacci recurrences, R P Brent, Mathematics of Computation (1995), to appear.

Factorisation of Large Integers on some Vector and Parallel Computers, C Eldershaw and R P Brent, Report TR-CS-95-01, 6 pp., Computer Sciences Lab, ANU, January 1995.