- Sep 30, 2006
- 4,267
- 421
- 126
NFS@Home needs some crunch!
- Thread starter Rudy Toody
- Start date
petrusbroder
Elite Member
- Nov 28, 2004
- 13,343
- 1,138
- 126
waffleironhead
Diamond Member
- Aug 10, 2005
- 6,919
- 429
- 136
VirtualLarry
No Lifer
- Aug 25, 2001
- 56,315
- 10,031
- 126
waffleironhead
Diamond Member
- Aug 10, 2005
- 6,919
- 429
- 136
Hmm, well I checked both off. I'm getting wu's that say GB200... so I guess I'm getting the right units.
These tasks are very memory intensive though. 4 running at the same time overloads my 4 gigs. Does anyone know how to set boinc up so it only runs 2 NFS units at a time while leaving my other 2 cores to work on other things like correlizer and primegrid?
These tasks are very memory intensive though. 4 running at the same time overloads my 4 gigs. Does anyone know how to set boinc up so it only runs 2 NFS units at a time while leaving my other 2 cores to work on other things like correlizer and primegrid?
- Sep 30, 2006
- 4,267
- 421
- 126
There's a new update from Greg, NFS@Home administrator:
This B200 is very important for math community so bring on the big cannons!!
You can set up boinc either using lasievef or lasieve5f. Linux 64 bits will earn more points compared to windows users because the latter is only available in 32 bits version.
lasieved - rarely used so work is rarely available, only for small numbers: no
lasievee - work nearly always available, uses up to 0.5 GB memory: no
lasievef - used for huge factorizations, uses up to 1 GB memory: yes
lasieve5f - used for huge factorizations, uses up to 1 GB memory: no
Carlos
This B200 is very important for math community so bring on the big cannons!!
You can set up boinc either using lasievef or lasieve5f. Linux 64 bits will earn more points compared to windows users because the latter is only available in 32 bits version.
lasieved - rarely used so work is rarely available, only for small numbers: no
lasievee - work nearly always available, uses up to 0.5 GB memory: no
lasievef - used for huge factorizations, uses up to 1 GB memory: yes
lasieve5f - used for huge factorizations, uses up to 1 GB memory: no
Carlos
Just to explain how much work is needed to sieve B200.
Right now wu's are at q=202M and the goal is to go up to q=420M. You can check which q range you are sieving by going into your task property.
Anyway, each wu sieves a q=1000 range so we still need ~218k tasks to reach q=420M.
Hope Anandtech can bring more power.
Thank you.
Carlos
Right now wu's are at q=202M and the goal is to go up to q=420M. You can check which q range you are sieving by going into your task property.
Code:
Stderr output
<core_client_version>7.0.24</core_client_version>
<![CDATA[
<stderr_txt>
boinc initialized
work files resolved, now working
-> ../../projects/escatter11.fullerton.edu_nfs/lasievef_1.10_x86_64-pc-linux-gnu
-> -a
-> -f
-> 202256000
-> -c
-> 1000
-> -R
-> ../../projects/escatter11.fullerton.edu_nfs/GB200.poly
-> -o
-> ../../projects/escatter11.fullerton.edu_nfs/GB200_202256_0_0
total yield: 1622, q=202257001 (0.80009 sec/rel, 100.10000 % done of 1000)
called boinc_finish
</stderr_txt>
]]>Anyway, each wu sieves a q=1000 range so we still need ~218k tasks to reach q=420M.
Hope Anandtech can bring more power.
Thank you.
Carlos
blckgrffn
Diamond Member
I'd tweak the shares so that they are all on the same "level" - that should give you a good if not exactly optimal mix.
Greg just released a 64-bit Mac OS X app. As he said it uses less memory and is much faster than the older 32-bit app for Mac.
About B200 he said on mersenneforum:
About B200 he said on mersenneforum:
- Sep 30, 2006
- 4,267
- 421
- 126
The range for my WUs is 397K. These are the big (64bit) ones, so that means that 23K has been done by Linux 64 apps. I would guess that adding a couple more 64bit apps would help out.
I can only use my 1100T with its 16GB memory on these because the quads get overwhelmed with swapping.
Catch me if you can!
- Sep 30, 2006
- 4,267
- 421
- 126
From the earlier estimate we should only have a couple of days left of B200. There are only 66 Linux64 users going at this time.
I have a quad on edges at this time and will switch the six-pack over when the B200s are done.
My other quad is currently dead. I hope to revive it enough to do SIMAP next month.
I have a quad on edges at this time and will switch the six-pack over when the B200s are done.
My other quad is currently dead. I hope to revive it enough to do SIMAP next month.
- Sep 30, 2006
- 4,267
- 421
- 126
- Sep 30, 2006
- 4,267
- 421
- 126
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. The third edition of the book, published by the American Mathematical Society in 2002, is available as a free download. All results obtained since the publication of the third edition are available on the Cunningham project website.
Concerning target size there are four sievers applications available (http://escatter11.fullerton.edu/nfs/prefs.php?subset=project:):
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
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
lasievef - 65
lasieve5f - 65
Why the difference in credits?
The more valuable calculation gets more credit. Especially for 16e (lasievef+lasieve5f), the extra credit also awards for the large memory usage.
What project uses what application?
lasieved - Oddperfect, n^n+(n+1)^(n+1), Fibonacci, Lucas, Cunningham, Cullen and Woodall for SNFS difficulty below 250.
lasievee - Cunningham, Oddperfect or other for SNFS difficulty above 250 to ~280.
lasievef - push the state of art for very difficulty factorizations, above SNFS difficulty of 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. It's advanced math related.
For a (much) more technical description of the NFS, see the Wikipedia article or Briggs' Master's thesis.
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. The third edition of the book, published by the American Mathematical Society in 2002, is available as a free download. All results obtained since the publication of the third edition are available on the Cunningham project website.
Concerning target size there are four sievers applications available (http://escatter11.fullerton.edu/nfs/prefs.php?subset=project:):
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
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
lasievef - 65
lasieve5f - 65
Why the difference in credits?
The more valuable calculation gets more credit. Especially for 16e (lasievef+lasieve5f), the extra credit also awards for the large memory usage.
What project uses what application?
lasieved - Oddperfect, n^n+(n+1)^(n+1), Fibonacci, Lucas, Cunningham, Cullen and Woodall for SNFS difficulty below 250.
lasievee - Cunningham, Oddperfect or other for SNFS difficulty above 250 to ~280.
lasievef - push the state of art for very difficulty factorizations, above SNFS difficulty of 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. It's advanced math related.
For a (much) more technical description of the NFS, see the Wikipedia article or Briggs' Master's thesis.
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. The third edition of the book, published by the American Mathematical Society in 2002, is available as a free download. All results obtained since the publication of the third edition are available on the Cunningham project website.
Concerning target size there are four sievers applications available (http://escatter11.fullerton.edu/nfs/prefs.php?subset=project:):
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
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
lasievef - 65
lasieve5f - 65
Why the difference in credits?
The more valuable calculation gets more credit. Especially for 16e (lasievef+lasieve5f), the extra credit also awards for the large memory usage.
What project uses what application?
lasieved - Oddperfect, n^n+(n+1)^(n+1), Fibonacci, Lucas, Cunningham, Cullen and Woodall for SNFS difficulty below 250.
lasievee - Cunningham, Oddperfect or other for SNFS difficulty above 250 to ~280.
lasievef - push the state of art for very difficulty factorizations, above SNFS difficulty of 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. It's advanced math related.
For a (much) more technical description of the NFS, see the Wikipedia article or Briggs' Master's thesis.
Number Field Sieve (NFS) References
From msieve readme.txt file:
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. The third edition of the book, published by the American Mathematical Society in 2002, is available as a free download. All results obtained since the publication of the third edition are available on the Cunningham project website.
Concerning target size there are four sievers applications available (http://escatter11.fullerton.edu/nfs/prefs.php?subset=project:):
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
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
lasievef - 65
lasieve5f - 65
Why the difference in credits?
The more valuable calculation gets more credit. Especially for 16e (lasievef+lasieve5f), the extra credit also awards for the large memory usage.
What project uses what application?
lasieved - Oddperfect, n^n+(n+1)^(n+1), Fibonacci, Lucas, Cunningham, Cullen and Woodall for SNFS difficulty below 250.
lasievee - Cunningham, Oddperfect or other for SNFS difficulty above 250 to ~280.
lasievef - push the state of art for very difficulty factorizations, above SNFS difficulty of 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. It's advanced math related.
For a (much) more technical description of the NFS, see the Wikipedia article or Briggs' Master's thesis.
Number Field Sieve (NFS) References
From msieve readme.txt file:
Last edited:
Factoring an integer using NFS has 3 main steps:
1. Select Polynomial
2. Collect Relations via Sieving (NFS@Home is dedicated to this step)
3. Combine Relations
1. Polynomial Selection
Step 1 of NFS involves choosing a polynomial-pair (customarily shortened to 'a polynomial') to use in the other NFS phases. The polynomial is completely specific to the number you need factored, and there is an effectively infinite supply of polynomials that will work. The quality of the polynomial you select has a dramatic effect on the sieving time; a *good* polynomial can make the sieving proceed two or three times faster compared to an average polynomial. So you really want a *good* polynomial, and for large problems should be prepared to spend a fair amount of time looking for one.
Just how long is too long, and exactly how you should look for good polynomials, is currently an active research area. The approximate consensus is that you should spend maybe 3-5% of the anticipated sieving time looking for a good polynomial.
We measure the goodness of a polynomial primarily by its Murphy E score; this is the probability, averaged across all the possible relations we could encounter during the sieving, that an 'average' relation will be useful for us. This is usually a very small number, and the E score to expect goes down as the number to be factored becomes larger. A larger E score is better.
Besides the E score, the other customary measure of polynomial goodness is the 'alpha score', an approximate measure of how much of an average relation is easily 'divided out' by dividing by small primes. The E score computation requires that we know the approximate alpha value, but alpha is also of independent interest. Good alpha values are negative, and negative alpha with large abo****e value is better. Both E and alpha were first formalized in Murphy's wonderful dissertation on NFS polynomial selection.
With that in mind, here's an example polynomial for a 100-digit input of no great significance:
R0: -2000270008852372562401653
R1: 67637130392687
A0: -315744766385259600878935362160
A1: 76498885560536911440526
A2: 19154618876851185
A3: -953396814
A4: 180
skew 7872388.07, size 9.334881e-014, alpha -5.410475, combined = 1.161232e-008
As mentioned, this 'polynomial' is actually a pair of polynomials, the Rational polynomial R1 * x + R0 and the 4-th degree Algebraic polynomial
A4 * x^4 + A3 * x^3 + A2 * x^2 + A1 * x + A0
The algebraic polynomial is of degree 4, 5, or 6 depending on the size of the input. The 'combined' score is the Murphy E value for this polynomial, and is pretty good in this case. The other thing to note about this polynomial-pair is that the leading algebraic coefficient is very small, and each other coefficient looks like it's a fixed factor larger than the next higher- degree coefficient. That's because the algebraic polynomial expects the sieving region to be 'skewed' by a factor equal to the reported skew above.
The polynomial selection determined that the 'average size' of relations drawn from the sieving region is smallest when the region is 'short and wide' by a factor given by the skew. The big advantage to skewing the polynomial is that it allows the low-order algebraic coefficients to be large, which in turn allows choosing them to optimize the alpha value. The modern algorithms for selecting NFS polynomials are optimized to work when the skew is very large.
NFS polynomial selection is divided into two stages. Stage 1 chooses the leading algebraic coefficient and tries to find the two rational polynomial coefficients so that the top three algebraic coefficients are small. Because stage 1 doesn't try to find the entire algebraic polynomial, it can use powerful sieving techniques to speed up this portion of the search. When stage 1 finds a 'hit', composed of the rational and the leading algebraic polynomial coefficient, Stage 2 then finds the complete polynomial pair and tries to optimize both the alpha and E values. A single stage 1 hit can generate many complete polynomials in stage 2. You can think of stage 1 as a very compute-intensive net that tries to drag in something good, and stage 2 as a shorter but still compute-intensive process that tries to polish things.
2. Sieving for Relations
The sieving step is not the theoretically most complex part of the algorithm of factorization, but it is the most time consuming part because it iterates over a large domain with some expensive calculations like division and modulo, although some of these can be avoided by using logarithms.
In general optimization of the sieving step will give the biggest reduction in actual running time of the algorithm. It is easy to use a large amount of memory in this step, and one should be aware of this and try to reuse arrays and use the smallest possible data types. The factor bases can for record factorizations contain millions of elements, so one should try to obtain the best on-disk/in-memory tradeoff.
The purpose of the sieving step is to find usable relations, i.e. elements (a, b) with the following properties
gcd(a, b) = 1
a + bm is smooth over the rational factor base
b^deg(f)*f(a/b) is smooth over the algebraic factor base
Finding elements with these properties can be done by various sieving methods like the classical line sieving or the faster lattice sieving, the latter being used at NFS@Home.
The lattice sieving was proposed by John Pollard in "Lattice sieving, Lecture Notes in Mathematics 1554 (1991), 4349.". The factor bases are split into smaller sets and then the elements which are divisible by a large prime q are sieved. The sizes of the factor bases have to be determined empirically, and are dependent on the precision of the sieving code, if all smooth elements are found or if one skips some by using special-q methods.
One advantage the lattice siever has is the following. The yield rate for the line siever decreases over time because the norms get bigger as the sieve region moves away from the origin. The lattice siever brings the sieve region "back to the origin" when special-q's are changed. This might be its biggest advantage (if there is one).
3. Combine Relations
The last phase of NFS factorization is a group of tasks collectively referred to as 'NFS postprocessing'. You need the factor base file described in the sieving section (only the polynomial is needed, not the actual factor base entries), and all of the relations from the sieving. If you have performed sieving in multiple steps or on multiple machines, all of the relations that have been produced need to be combined into a single giant file. And by giant I mean *really big*; the largest NFS jobs that I know about currently have involved relation files up to 100GB in size.
Even a fairly small 100-digit factorization generates perhaps 500MB of disk files, so you are well advised to allow plenty of space for relations. Don't like having to deal with piling together thousands of files into one? Sorry, but disk space is cheap now.
With the factor base and relation data file available, is is time to perform NFS postprocessing.However, for larger jobs or for any job where data has to be moved from machine to machine, it is probably necessary to divide the postprocessing into its three fundamental tasks. These are described below:
NFS Filtering
-------------
The first phase of NFS postprocessing is the filtering step. This analyzes the input relation file, sets up the rest of the filtering to ignore relations that will not be useful (usually 90% of them or more), and produces a 'cycle file' that describes the huge matrix to be used in the next postprocessing stage.
To do that, every relation is assigned a unique number, corresponding to its line number in the relation file. Relations are numbered starting from zero, and part of the filtering also adds 'free relations' to the dataset. Free relations are so-called because it does not require any sieving to find them; these are a unique feature of the number field sieve, although there will never be very many of them. Filtering is a very complex process. If you do not have enough relations for filtering to succeed, no output is produced other than complaints to that effect. If there are 'enough' relations for filtering to succeed, the result is a 'cycle file'.
How many relations is 'enough'? This is unfortunately another hard question, and answering it requires either compiling large tables of factorizations of similar size numbers, running the filtering over and over again, or performing simulations after a little test-sieving. There's no harm in finding more relations than you strictly need for filtering to work at all, although if you mess up and find twice as many relations as you need then getting the filtering to work can also be difficult. In general the filtering works better if you give it somewhat more relations than it stricly needs, maybe 10% more. As more and more relations are added, the size of the generated matrix becomes smaller and smaller, partly because the filtering can throw away more and more relations to keep only the 'best' ones.
NFS Linear Algebra
------------------
The linear algebra step constructs the matrix that was generated from the filtering, and finds a group of vectors that lie in the nullspace of that matrix. Finding nullspace vectors for a really big matrix is an enormous amount of work. To do the job, Msieve uses the block Lanczos algorithm with a large number of performance optimizations. Even with fast code like that, solving the matrix can take anywhere from a few minutes (factoring a 100-digit input leads to a matrix of size ~200000) to several months (using the special number field sieve on 280-digit numbers from the Cunningham Project usually leads to matrices of size ~18 million). Even worse, the answer has to be *exactly* correct all the way through; there's no throwing away intermediate results that are bad, like the other NFS phases can do. So solving a big matrix is a severe test of both your computer and your patience.
Multithreaded Linear Algebra
----------------------------
The linear algebra is fully multithread aware. Note that the solver is primarily memory bound, and using as many threads as you have cores on your multicore processor will probably not give the best performance. The best number of threads to use depends on the underlying machine; more recent processors have much more powerful memory controllers and can continue speeding up as more and more threads are used. A good rule of thumb to start off is to try two threads for each physical package on your motherboard; even if it's not the fastest choice, just two or four threads gets the vast majority of the potential speedup for the vast majority of machines.
Finally, note that the matrix solver is a 'tightly parallel' computation, which means if you give it four threads then the machine those four threads run on must be mostly idle otherwise. The linear algebra will soak up most of the memory bandwidth your machine has, so if you divert any of it away to something else then the completion time for the linear algebra will suffer.
As for memory use, solving the matrix for a 512-bit input is going to require around 2GB of memory in the solver, and a fast modern processor running the solver with four threads will need about 36 hours. A slow, less modern processor that is busy with other stuff could take up to a week!
NFS Square Root
---------------
With the solution file from the linear algebra in hand, the last phase of NFS postprocessing is the square root.
'an NFS square root' is actually two square roots, an easy one over the integers and a very complex one over the algebraic number field described by the NFS polynomial we selected. Traditionally, the best algorithm for the algebraic part of the NFS square root is the one described by Montgomery and Nguyen, but that takes some quite sophisticated algebraic number theory smarts.
Every solution generated by the linear algebra is called 'a dependency', because it is a linearly dependent vector for the matrix we built.
The square root in Msieve proceeds one dependency at a time; it requires all the relations from the data file, the cycle file from the filtering, and the dependency file from the linear algebra. Technically the square root can be speed up if you process multiple dependencies in parallel, but doing one at a time makes it possible to adapt the precision of the numbers used to save a great deal of memory toward the end of each dependency.
Each dependency has a 50% chance of finding a nontrivial factorization of the input.
msieve is the client used for post-processing phase
In conclusion, factoring an integer using NFS has 3 main steps:
1. Select Polynomial
External to NFS@Home project. If number is GNFS then polynomial search is necessary using GPU or CPU.
2. Collect Relations via Sieving
Made via NFS@Home, only CPU sievers available.
3. Combine Relations
Done by NFS@Home in part, the relations obtained by sieving effort are stored on NFS@Home server. The post-processing phase is done or by external members or in clusters to take advantage of Multithreaded Linear Algebra phase. The latter can be done by using msieve MPI.
1. Select Polynomial
2. Collect Relations via Sieving (NFS@Home is dedicated to this step)
3. Combine Relations
1. Polynomial Selection
Step 1 of NFS involves choosing a polynomial-pair (customarily shortened to 'a polynomial') to use in the other NFS phases. The polynomial is completely specific to the number you need factored, and there is an effectively infinite supply of polynomials that will work. The quality of the polynomial you select has a dramatic effect on the sieving time; a *good* polynomial can make the sieving proceed two or three times faster compared to an average polynomial. So you really want a *good* polynomial, and for large problems should be prepared to spend a fair amount of time looking for one.
Just how long is too long, and exactly how you should look for good polynomials, is currently an active research area. The approximate consensus is that you should spend maybe 3-5% of the anticipated sieving time looking for a good polynomial.
We measure the goodness of a polynomial primarily by its Murphy E score; this is the probability, averaged across all the possible relations we could encounter during the sieving, that an 'average' relation will be useful for us. This is usually a very small number, and the E score to expect goes down as the number to be factored becomes larger. A larger E score is better.
Besides the E score, the other customary measure of polynomial goodness is the 'alpha score', an approximate measure of how much of an average relation is easily 'divided out' by dividing by small primes. The E score computation requires that we know the approximate alpha value, but alpha is also of independent interest. Good alpha values are negative, and negative alpha with large abo****e value is better. Both E and alpha were first formalized in Murphy's wonderful dissertation on NFS polynomial selection.
With that in mind, here's an example polynomial for a 100-digit input of no great significance:
R0: -2000270008852372562401653
R1: 67637130392687
A0: -315744766385259600878935362160
A1: 76498885560536911440526
A2: 19154618876851185
A3: -953396814
A4: 180
skew 7872388.07, size 9.334881e-014, alpha -5.410475, combined = 1.161232e-008
As mentioned, this 'polynomial' is actually a pair of polynomials, the Rational polynomial R1 * x + R0 and the 4-th degree Algebraic polynomial
A4 * x^4 + A3 * x^3 + A2 * x^2 + A1 * x + A0
The algebraic polynomial is of degree 4, 5, or 6 depending on the size of the input. The 'combined' score is the Murphy E value for this polynomial, and is pretty good in this case. The other thing to note about this polynomial-pair is that the leading algebraic coefficient is very small, and each other coefficient looks like it's a fixed factor larger than the next higher- degree coefficient. That's because the algebraic polynomial expects the sieving region to be 'skewed' by a factor equal to the reported skew above.
The polynomial selection determined that the 'average size' of relations drawn from the sieving region is smallest when the region is 'short and wide' by a factor given by the skew. The big advantage to skewing the polynomial is that it allows the low-order algebraic coefficients to be large, which in turn allows choosing them to optimize the alpha value. The modern algorithms for selecting NFS polynomials are optimized to work when the skew is very large.
NFS polynomial selection is divided into two stages. Stage 1 chooses the leading algebraic coefficient and tries to find the two rational polynomial coefficients so that the top three algebraic coefficients are small. Because stage 1 doesn't try to find the entire algebraic polynomial, it can use powerful sieving techniques to speed up this portion of the search. When stage 1 finds a 'hit', composed of the rational and the leading algebraic polynomial coefficient, Stage 2 then finds the complete polynomial pair and tries to optimize both the alpha and E values. A single stage 1 hit can generate many complete polynomials in stage 2. You can think of stage 1 as a very compute-intensive net that tries to drag in something good, and stage 2 as a shorter but still compute-intensive process that tries to polish things.
2. Sieving for Relations
The sieving step is not the theoretically most complex part of the algorithm of factorization, but it is the most time consuming part because it iterates over a large domain with some expensive calculations like division and modulo, although some of these can be avoided by using logarithms.
In general optimization of the sieving step will give the biggest reduction in actual running time of the algorithm. It is easy to use a large amount of memory in this step, and one should be aware of this and try to reuse arrays and use the smallest possible data types. The factor bases can for record factorizations contain millions of elements, so one should try to obtain the best on-disk/in-memory tradeoff.
The purpose of the sieving step is to find usable relations, i.e. elements (a, b) with the following properties
gcd(a, b) = 1
a + bm is smooth over the rational factor base
b^deg(f)*f(a/b) is smooth over the algebraic factor base
Finding elements with these properties can be done by various sieving methods like the classical line sieving or the faster lattice sieving, the latter being used at NFS@Home.
The lattice sieving was proposed by John Pollard in "Lattice sieving, Lecture Notes in Mathematics 1554 (1991), 4349.". The factor bases are split into smaller sets and then the elements which are divisible by a large prime q are sieved. The sizes of the factor bases have to be determined empirically, and are dependent on the precision of the sieving code, if all smooth elements are found or if one skips some by using special-q methods.
One advantage the lattice siever has is the following. The yield rate for the line siever decreases over time because the norms get bigger as the sieve region moves away from the origin. The lattice siever brings the sieve region "back to the origin" when special-q's are changed. This might be its biggest advantage (if there is one).
3. Combine Relations
The last phase of NFS factorization is a group of tasks collectively referred to as 'NFS postprocessing'. You need the factor base file described in the sieving section (only the polynomial is needed, not the actual factor base entries), and all of the relations from the sieving. If you have performed sieving in multiple steps or on multiple machines, all of the relations that have been produced need to be combined into a single giant file. And by giant I mean *really big*; the largest NFS jobs that I know about currently have involved relation files up to 100GB in size.
Even a fairly small 100-digit factorization generates perhaps 500MB of disk files, so you are well advised to allow plenty of space for relations. Don't like having to deal with piling together thousands of files into one? Sorry, but disk space is cheap now.
With the factor base and relation data file available, is is time to perform NFS postprocessing.However, for larger jobs or for any job where data has to be moved from machine to machine, it is probably necessary to divide the postprocessing into its three fundamental tasks. These are described below:
NFS Filtering
-------------
The first phase of NFS postprocessing is the filtering step. This analyzes the input relation file, sets up the rest of the filtering to ignore relations that will not be useful (usually 90% of them or more), and produces a 'cycle file' that describes the huge matrix to be used in the next postprocessing stage.
To do that, every relation is assigned a unique number, corresponding to its line number in the relation file. Relations are numbered starting from zero, and part of the filtering also adds 'free relations' to the dataset. Free relations are so-called because it does not require any sieving to find them; these are a unique feature of the number field sieve, although there will never be very many of them. Filtering is a very complex process. If you do not have enough relations for filtering to succeed, no output is produced other than complaints to that effect. If there are 'enough' relations for filtering to succeed, the result is a 'cycle file'.
How many relations is 'enough'? This is unfortunately another hard question, and answering it requires either compiling large tables of factorizations of similar size numbers, running the filtering over and over again, or performing simulations after a little test-sieving. There's no harm in finding more relations than you strictly need for filtering to work at all, although if you mess up and find twice as many relations as you need then getting the filtering to work can also be difficult. In general the filtering works better if you give it somewhat more relations than it stricly needs, maybe 10% more. As more and more relations are added, the size of the generated matrix becomes smaller and smaller, partly because the filtering can throw away more and more relations to keep only the 'best' ones.
NFS Linear Algebra
------------------
The linear algebra step constructs the matrix that was generated from the filtering, and finds a group of vectors that lie in the nullspace of that matrix. Finding nullspace vectors for a really big matrix is an enormous amount of work. To do the job, Msieve uses the block Lanczos algorithm with a large number of performance optimizations. Even with fast code like that, solving the matrix can take anywhere from a few minutes (factoring a 100-digit input leads to a matrix of size ~200000) to several months (using the special number field sieve on 280-digit numbers from the Cunningham Project usually leads to matrices of size ~18 million). Even worse, the answer has to be *exactly* correct all the way through; there's no throwing away intermediate results that are bad, like the other NFS phases can do. So solving a big matrix is a severe test of both your computer and your patience.
Multithreaded Linear Algebra
----------------------------
The linear algebra is fully multithread aware. Note that the solver is primarily memory bound, and using as many threads as you have cores on your multicore processor will probably not give the best performance. The best number of threads to use depends on the underlying machine; more recent processors have much more powerful memory controllers and can continue speeding up as more and more threads are used. A good rule of thumb to start off is to try two threads for each physical package on your motherboard; even if it's not the fastest choice, just two or four threads gets the vast majority of the potential speedup for the vast majority of machines.
Finally, note that the matrix solver is a 'tightly parallel' computation, which means if you give it four threads then the machine those four threads run on must be mostly idle otherwise. The linear algebra will soak up most of the memory bandwidth your machine has, so if you divert any of it away to something else then the completion time for the linear algebra will suffer.
As for memory use, solving the matrix for a 512-bit input is going to require around 2GB of memory in the solver, and a fast modern processor running the solver with four threads will need about 36 hours. A slow, less modern processor that is busy with other stuff could take up to a week!
NFS Square Root
---------------
With the solution file from the linear algebra in hand, the last phase of NFS postprocessing is the square root.
'an NFS square root' is actually two square roots, an easy one over the integers and a very complex one over the algebraic number field described by the NFS polynomial we selected. Traditionally, the best algorithm for the algebraic part of the NFS square root is the one described by Montgomery and Nguyen, but that takes some quite sophisticated algebraic number theory smarts.
Every solution generated by the linear algebra is called 'a dependency', because it is a linearly dependent vector for the matrix we built.
The square root in Msieve proceeds one dependency at a time; it requires all the relations from the data file, the cycle file from the filtering, and the dependency file from the linear algebra. Technically the square root can be speed up if you process multiple dependencies in parallel, but doing one at a time makes it possible to adapt the precision of the numbers used to save a great deal of memory toward the end of each dependency.
Each dependency has a 50% chance of finding a nontrivial factorization of the input.
msieve is the client used for post-processing phase
In conclusion, factoring an integer using NFS has 3 main steps:
1. Select Polynomial
External to NFS@Home project. If number is GNFS then polynomial search is necessary using GPU or CPU.
2. Collect Relations via Sieving
Made via NFS@Home, only CPU sievers available.
3. Combine Relations
Done by NFS@Home in part, the relations obtained by sieving effort are stored on NFS@Home server. The post-processing phase is done or by external members or in clusters to take advantage of Multithreaded Linear Algebra phase. The latter can be done by using msieve MPI.
Hi there!
I think with my previously posts you can get to know very well what NFS@Home does.
Now to the challenge numbers and figures:
To get the most credits you should run the 16e (lasievef) or 16e V5 (lasieve5f) applications. These applications are sieving a number called 2,1037-. For linux users with more than 1.2GB per thread set
in "http://escatter11.fullerton.edu/nfs/prefs.php?subset=project".
For windows users set "yes" instead or "no" for "lasievef". 1.35 GB per thread is needed to run "lasievef" application. If you don't have it chose lasievee or lasieved application. lasieve5f is not available for windows OS.
In terms of points per application the situation is like this:
In global settings at "http://escatter11.fullerton.edu/nfs/prefs.php?subset=global" set
Carlos Pinho
PS( Windows users with more than 2GB/thread of memory with Ubuntu x64 installed under Virtual Box will get the most of it instead of only running NFS@Home under Windows environment)
PS 2( Challenges links, part I at http://boincstats.com/en/stats/challenge/team/chat/283 and part II at http://boincstats.com/en/stats/challenge/team/chat/285)
I think with my previously posts you can get to know very well what NFS@Home does.
Now to the challenge numbers and figures:
To get the most credits you should run the 16e (lasievef) or 16e V5 (lasieve5f) applications. These applications are sieving a number called 2,1037-. For linux users with more than 1.2GB per thread set
Code:
lasieved - app for RSALS subproject, uses less than 0.5 GB memory: no
lasievee - work nearly always available, uses up to 0.5 GB memory: no
lasievef - used for huge factorizations, uses up to 1 GB memory: no
lasieve5f - used for huge factorizations, uses up to 1 GB memory: yesin "http://escatter11.fullerton.edu/nfs/prefs.php?subset=project".
For windows users set "yes" instead or "no" for "lasievef". 1.35 GB per thread is needed to run "lasievef" application. If you don't have it chose lasievee or lasieved application. lasieve5f is not available for windows OS.
In terms of points per application the situation is like this:
Code:
lasieved - 36 points per wu
lasievee - 44 points per wu
lasievef - 65 points per wu
lasieve5f - 65 points per wuIn global settings at "http://escatter11.fullerton.edu/nfs/prefs.php?subset=global" set
Code:
Swap space: use at most: 98% of total
Memory: when computer is in use, use at most: 100% of total
Memory: when computer is not in use, use at most: 100% of totalCarlos Pinho
PS( Windows users with more than 2GB/thread of memory with Ubuntu x64 installed under Virtual Box will get the most of it instead of only running NFS@Home under Windows environment)
PS 2( Challenges links, part I at http://boincstats.com/en/stats/challenge/team/chat/283 and part II at http://boincstats.com/en/stats/challenge/team/chat/285)
Come an join us at the second part of the Challenge, we really need to finish 2,1037- sieve by the end of the year.
Second part of the challenge is underway at http://boincstats.com/en/stats/challenge/team/chat/285.
2,1037- figures:
Last 16e Lattice Sieve application wu received is at ~q=801M.
Last 16e Lattice Sieve V5 application wu received is at ~q=970M (second chunk restarted at 950M going to 1,000M: meaning going backwards from 1,000M until meet 16e in the middle).
Last 16e Lattice Sieve V5 application already sent all wu's from 1,000M to 1,400M (first chunk).
Overall Q range sieve of 2,1037- started at 20M to 1,400M.
Q range situation is this:
20M-801M (sent through 16e application, remaining wu's close to be done)
801M-950M (unsent)
950M-970M (sent, remaining wu's close to be done)
970M-1000M (unsent, will be sent through 16e V5 application)
1000M-1400M (sent through 16e V5 application, remaining wu's close to be done)
In terms of work still to be done we are talking about ~179k wu's left to be crunched, ~82k already created, ~46k in progress.
Considering my machine (core i5 750 with cache set to 200, 180 wu's daily done) the leading edge of the undone wu's to the finish ones is about 11M without taking into consideration the repetitive wu's that probably are in there mixed.
Carlos Pinho
(Post-processing helper of NFS@Home Boinc Project)
Second part of the challenge is underway at http://boincstats.com/en/stats/challenge/team/chat/285.
2,1037- figures:
Last 16e Lattice Sieve application wu received is at ~q=801M.
Last 16e Lattice Sieve V5 application wu received is at ~q=970M (second chunk restarted at 950M going to 1,000M: meaning going backwards from 1,000M until meet 16e in the middle).
Last 16e Lattice Sieve V5 application already sent all wu's from 1,000M to 1,400M (first chunk).
Overall Q range sieve of 2,1037- started at 20M to 1,400M.
Q range situation is this:
20M-801M (sent through 16e application, remaining wu's close to be done)
801M-950M (unsent)
950M-970M (sent, remaining wu's close to be done)
970M-1000M (unsent, will be sent through 16e V5 application)
1000M-1400M (sent through 16e V5 application, remaining wu's close to be done)
In terms of work still to be done we are talking about ~179k wu's left to be crunched, ~82k already created, ~46k in progress.
Considering my machine (core i5 750 with cache set to 200, 180 wu's daily done) the leading edge of the undone wu's to the finish ones is about 11M without taking into consideration the repetitive wu's that probably are in there mixed.
Carlos Pinho
(Post-processing helper of NFS@Home Boinc Project)
Posted several messages one about the current challenge taking place (http://boincstats.com/en/stats/challenge/team/chat/285) but I need a mod to permit it. Thank you in advance,
Carlos Pinho
Carlos Pinho
Last edited:
VirtualLarry
No Lifer
- Aug 25, 2001
- 56,315
- 10,031
- 126
Since I'm not participating in the F@H Dec. race, nor the PrimeGrid Dec. race, I added NFS@Home as a project on my main rig. Hope it helps! (Currently doing both WCG/HCC, and NFS@Home.)
TRENDING THREADS
-
Discussion Intel current and future Lakes & Rapids thread- Started by TheF34RChannel
- Replies: 23K
-
Discussion Zen 5 Speculation (EPYC Turin and Strix Point/Granite Ridge - Ryzen 9000)- Started by DisEnchantment
- Replies: 9K
-
-
Discussion Intel Meteor, Arrow, Lunar & Panther Lakes Discussion Threads
- Started by Tigerick
- Replies: 7K
-
Facebook
Twitter