NFS@Home Project Goals
Joined: 26 Sep 09
The goal of NFS@Home is to factor large numbers using the Number Field Sieve algorithm. After setting up two polynomials and various parameters, the project participants "sieve" the polynomials to find values of two variables, called "relations," such that the values of both polynomials are completely factored. Each workunit finds a small number of relations and returns them. Once these are returned, the relations are combined together into one large file then start the "postprocessing." The postprocessing involves combining primes from the relations to eliminate as many as possible, constructing a matrix from those remaining, solving this matrix, then performing square roots of the products of the relations indicated by the solutions to the matrix. The end result is the factors of the number.
NFS@Home is interested in the continued development of open source, publicly available tools for large integer factorization. Over the past couple of years, the capability of open source tools, in particular the lattice sieve of the GGNFS suite and the program msieve, have dramatically improved.
Integer factorization is interesting both mathematical and practical perspectives. Mathematically, for instance, the calculation of multiplicative functions in number theory for a particular number require the factors of the number. Likewise, the integer factorization of particular numbers can aid in the proof that an associated number is prime. Practically, many public key algorithms, including the RSA algorithm, rely on the fact that the publicly available modulus cannot be factored. If it is factored, the private key can be easily calculated. Until quite recently, RSA-512, which uses a 512-bit modulus (155 digits), was used. As recently demonstrated by factoring the Texas Instruments calculator keys, these are no longer secure.
NFS@Home BOINC project makes it easy for the public to participate in state-of-the-art factorizations. The project interests is to see how far we can push the envelope and perhaps become competitive with the larger university projects running on clusters, and perhaps even collaborating on a really large factorization.
The numbers are chosen from the Cunningham project. The project is named after Allan Joseph Champneys Cunningham, who published the first version of the factor tables together with Herbert J. Woodall in 1925. This project is one of the oldest continuously ongoing projects in computational number theory, and is currently maintained by Sam Wagstaff at Purdue University.
Concerning target size there are three sievers (application) available:
lasieved - app for RSALS subproject, uses less than 0.5 GB memory: yes or no
lasievee - work nearly always available, uses up to 0.5 GB memory: yes or no
lasievef - used for huge factorizations, uses up to 1 GB memory: yes or no (not available anymore)
lasieve5f - used for huge factorizations, uses up to 1 GB memory: yes or no
How's the credit distributed per target wu?
lasieved - 36
lasievee - 44
lasieve5f - 130
Why the difference in credits?
The more valuable calculation gets more credit. Especially for 16e (lasieve5f), the extra credit also awards for the large memory usage.
lasieved: each workunit managing 16k Q values
lasievee: each workunit managing 4k Q values
lasieve5f: each workunit managing 2k Q values
What project uses what application?
lasieved - Oddperfect, n^n+(n+1)^(n+1), Fibonacci, Lucas, Cunningham, Cullen and Woodall for SNFS difficulty below 260
lasievee - Cunningham, Oddperfect, Fibonacci, Lucas or other for SNFS difficulty above 250 to ~280.
lasieve5f - push the state of art for very difficulty factorizations, above SNFS difficulty of 280
The limits depends upon the boundaries chosen for the poly and characteristics of the number being factored.
For a (much) more technical description of the NFS, see:
- Wikipedia article (http://en.wikipedia.org/wiki/Number_field_sieve)
- Briggs' Master's thesis (http://scholar.lib.vt.edu/theses/available/etd-32298-93111/unrestricted/etd.pdf)
Joined: 26 Sep 09
Placeholder for corrections.
24/12/2017: To be updated soon but the main has been updated.