Applications of Integer Factorization
The integer factorization problem is an essential ingredient of publickey 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 
Project k58 Facilities Used PC, VPP, MDSS 
CoInvestigators John CannonComputer Sciences Laboratory University of Sydney
Brendan McKay

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 recordbreaking factorisations of a 512bit (155 decimal digit) number and (in January 2002) of a 158decimal 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), 429451.
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), 12971304.
R. P. Brent, Some parallel algorithms for integer factorisation, Lecture Notes in Computer Science 1685 (1999), 122.
R. P. Brent, Recent progress and prospects for integer factorisation algorithms, Lecture Notes in Computer Science 1858 (2000), 322.
R. P. Brent, P. L. Montgomery and H. J. J. te Riele, Factorizations of Cunningham numbers with bases 13 to 99, Report PRGTR1400, December 2000, 502pp.