Compute Cluster Nodes for Factoring Integers

Purdue University, West Lafayette IN

Investigators

Abstract

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.