The Number Field Sieve (NFS) is the fastest known integer factoring algorithm. The polynomial selection and sieving steps of NFS are easily parallelizable and may be performed on many independent machines with little internode communication. Purdue's Condor system has tens of thousands of machines available and is well-positioned to perform this part of the algorithm. However, the linear algebra step of NFS is best performed on several cores of a multicore machine with large memory. Although Purdue's Condor system is available to all faculty, use of its multicore machines is restricted to those faculty who helped to pay for the machine through a grant. Multicore service is available through TeraGrid, but this service is limited and requires annual applications. The award will be used to purchase part of a new multicore machine and then the PI and his students will have access to it during its lifetime. The machine will be used to run the linear algebra step of NFS to factor important numbers, such as those in the Cunningham Project.
The factorizations of Cunningham numbers, which will be discovered by the multicore machine after the Condor system performs the sieving, have significant applications throughout mathematics. These applications include period lengths of decimal fractions, discovery of new algebraic identities, perfect numbers, evaluation of arithmetic functions, determining the structure of cyclotomic fields, construction of elliptic curve cryptosystems, and design of linear feedback shift registers. Furthermore, the running time taken by each factorization will provide another benchmark for the difficulty of factoring integers, and tell cryptographers how large to choose parameters for certain ciphers. These ciphers and the elliptic curve cryptosystems are used to secure private communication by business and government and for many other purposes. The PI's students will use the multicore machine and gain experience programming supercomputers as well as learn the best techniques for factoring integers. When they graduate, these students will take this knowledge to careers in research, education, government and business.
The purpose of this NSF grant was to purchase equipment. The funds were used to buy compute clusters at Purdue University. These nodes are used to perform the linear algebra portion of a fast integer factoring algorithm, the number field sieve (NFS). The other parts of the algorithm are done as thousands of short jobs on the Condor system. The program was ported to the Condor/compute cluster environment by the PI and a graduate student, who gained valuable experience. After the program was working, it was used to factor several large integers using NFS. It will factor many more large numbers during the lifetime of the compute clusters. When the compute clusters are not busy with NFS linear algebra, they are used to factor numbers with the elliptic curve method. One finding was the factors themselves, which have many uses in mathematics. Another finding was how to choose parameters for the NFS in an unusual computing environment in which it is cheap to run many short jobs, but expensive to run one long job whose time is shorter than the total time for the short jobs. In this case the size of the factor base of small primes should be smaller than it would be if the cost of a job was simply proportional to its time. An unexpected finding was the discovery of two large prime factors by the elliptic curve method when the nodes were not doing NFS. The 79 and 75-digit primes discovered are the largest two primes ever found by this algorithm, as of September, 2012. The results of this grant have been published on several web pages. These include Zimmermann's list of record elliptic curve factorizations www.loria.fr/~zimmerma/records/factor.html and www.loria.fr/~zimmerma/records/top50.html. Brent has published some results of this grant at http://wwwmaths.anu.edu.au/~brent/ftp/champs.txt. The PI has put some of the factors on his web pages http://homes.cerias.purdue.edu/~ssw/cun/oldp/cun124 http://homes.cerias.purdue.edu/~ssw/cun/oldp/chmp124
