Applications of Integer Factorization


The integer factorization problem is an essential ingredient of public-key cryptosystems such as the RSA system, which is used to ensure the security of many transactions on the Internet. Thus, there is a great interest in discovering the best integer factorization algorithms, because the choice of key sizes in the RSA system depends on how quickly large integers can be split into their prime factors. This project involves the implementation and testing of integer factorization algorithms.


Principal Investigator

Richard Brent
Computing Lab
Oxford University, UK

Project

k58

Facilities Used

PC, VPP, MDSS

Co-Investigators

John Cannon
Computer Sciences Laboratory
University of Sydney

Brendan McKay
Computer Science
Faculty of Science
ANU

RFCD Codes

230102, 280401


Significant Achievements, Anticipated Outcomes and Future Work

We have demonstrated improvements to the elliptic curve algorithm (ECM) which has been used to find factors up to 55 decimal digits.

Brian Murphy (former Ph.D. student), in collaboration with Peter Montgomery (Microsoft and CWI), has improved the polynomial selection phase of the number field sieve algorithm. Murphy's polynomial selection algorithm was used in the record-breaking factorisations of a 512-bit (155 decimal digit) number and (in January 2002) of a 158-decimal digit number by Bahr, Franke and Kleinjung.

We have extended the tables of factors of numbers of special forms and incorporated these tables in the Magma package of John Cannon. All relevant numbers with fewer than 108 decimal digits have now been factored.

 

Computational Techniques Used

The numbers of interest in cryptography and some other applications such as the analysis of very long period random number generators are very large, so a large amount of computation is required, even when the most efficient known algorithms are used. A quantum computer using Shor's algorithm would be helpful, but no such computer is available at the present time.

Our programs include a vectorized implementation of Lenstra's elliptic curve algorithm with a second phase, based on the "birthday paradox", which was developed at ANU. We also use the Magma package and an implementation in Magma of the PPMPQS quadratic sieve algorithm which was developed by collaborators at the University of Sydney and elsewhere, and an implementation of the number field sieve (NFS) algorithm which was developed mainly by collaborators at the Centre for Mathematics and Computer Science (CWI), Amsterdam.

 

Publications, Awards and External Funding

R. P. Brent, Factorization of the tenth Fermat number, Mathematics of Computation 68 (1999), 429-451.

R. P. Brent, Large factors found by ECM, available from ftp://ftp.comlab.ox.ac.uk/pub/Documents/techpapers/Richard.Brent/champs.txt

R. P. Brent, R. E. Crandall, K. Dilcher and C. Van Halewyn, Three new factors of Fermat numbers, Mathematics of Computation 69 (2000), 1297-1304.

R. P. Brent, Some parallel algorithms for integer factorisation, Lecture Notes in Computer Science 1685 (1999), 1-22.

R. P. Brent, Recent progress and prospects for integer factorisation algorithms, Lecture Notes in Computer Science 1858 (2000), 3-22.

R. P. Brent, P. L. Montgomery and H. J. J. te Riele, Factorizations of Cunningham numbers with bases 13 to 99, Report PRG-TR-14-00, December 2000, 502pp.