NFS Expected Runtime

[nivek000]

Hi. I have been watching a good number of GNFS factorings in YAFU, but it is still very difficult for me to understand the estimated time remaining. Is there a way to approximate this with the accumulated yield, current search range, etc.? Sometimes very similar digit length numbers take significantly different lengths of time to factor. Is this related to the yield rate (and is this based on the polynomial selection)? Or the size of the factors it will eventually find? Or all of the above?

Thanks.

- Kevin

[swellman]

Originally Posted by nivek000

Hi. I have been watching a good number of GNFS factorings in YAFU, but it is still very difficult for me to understand the estimated time remaining. Is there a way to approximate this with the accumulated yield, current search range, etc.? Sometimes very similar digit length numbers take significantly different lengths of time to factor. Is this related to the yield rate (and is this based on the polynomial selection)? Or the size of the factors it will eventually find? Or all of the above?

Thanks.

- Kevin

To the best of my knowledge, speed of sieving a number N using GNFS is dependent on the Murphy e-score of the polynomial. This value is usually called “combined =“ in the log file produced by msieve. Both speed and score are also dependent on log(N). In other words, a C151 with a first digit of 1 will have characteristics which differ from a C151 starting with digit 9 even though they are both 151 decimal digits long. But I’m certainly no expert!

CADO uses another definition to score its polynomials. But a CADO produced polynomial can be scored in the same manner as msieve by either using msieve (see this post), or by what is often referred to as cownoise from its website domain - click on calculators at the top of the page and use “optimal skew” to calculate the e-score of a polynomial.

Lastly, see this list of top scoring polynomials for reference.

[VBCurtis]

GNFS factoring time does not depend on the size of the factors, only on the size of the input. But that time doubles about every five digits, so a C140 takes about four times as long as a C130 to factor.

I don't use YAFU, so I can't give you good guidance about how to use the screen info to forecast time remaining- but it's pretty easy to forecast the total time for a job using that "double every 5 digits" rule of thumb.

It's not a great plan to skip from e.g. 100 digit demo jobs to a 160 digit beast without getting experience using the factoring software tools. Things happen to make jobs not quite smooth sailing, and learning what to do to save such a job when the cost of a mistake is hours rather than weeks is good for the user's sanity. As you gain experience, you learn what your personal hardware performance is- for instance, what size of job you can finish in a single day. That sort of reference point provides you a useful benchmark to estimate job time for nearly any length of job- though once you get to 170+ digits, memory capacity and custom NFS parameters become important (see the CADO subforum for such discussion examples).

[nivek000]

Originally Posted by VBCurtis

I don't use YAFU, so I can't give you good guidance about how to use the screen info to forecast time remaining-

As a programmer, I can imagine there must be a line in ggnfs that basically says, "If <condition is met> do msieve filter check Else lattice sieve again". The questions would be: what is the condition and does YAFU (or ggnfs, really) write out log data related to the condition check.

I have surmised that there may be an accumulated relations "yield" goal that when reached an msieve filter is run to see if linear algebra can be started. Sometimes it can't start linear algebra and it says "raising min_rels by 5.00 percent" at which point more sieving is done, but is also gives a new min_rels goal. It would be nice to know what the min_rels goal is when nfs starts. Just one sieve would then give you an estimate of the factoring time.

The only thing YAFU prints at the beginning of nfs are some poly constants. I have looked in some of the other misc. files output during processing but have not come across a min_rels type number anywhere.

- Kevin

[swellman]

There are manual ways to run a small amount of sieving, and once completed Yafu will display its goal number of relations and expected time to reach that goal. I believe the # of relations are hard coded in Yafu based on lpbr and lpba values, the timing is just extrapolation of running time on your hardware.

Once the minimum number of raw relations is reached, Yafu enters the filtering phase after which it may or may not be able to build a matrix. The ability to build a matrix is highly conditional but if a matrix can’t be built, Yafu looks for another 5% raw relations. (This value can be set by the user but 5% is the default.) Repeat.

I presume you’ve read through the code for Yafu. Ggnfs is old, almost abandonware these days, though someone updated it a few years ago.

Hope this helps.

[bsquared]

Originally Posted by nivek000

As a programmer, I can imagine there must be a line in ggnfs that basically says, "If <condition is met> do msieve filter check Else lattice sieve again". The questions would be: what is the condition and does YAFU (or ggnfs, really) write out log data related to the condition check.

I have surmised that there may be an accumulated relations "yield" goal that when reached an msieve filter is run to see if linear algebra can be started. Sometimes it can't start linear algebra and it says "raising min_rels by 5.00 percent" at which point more sieving is done, but is also gives a new min_rels goal. It would be nice to know what the min_rels goal is when nfs starts. Just one sieve would then give you an estimate of the factoring time.

The only thing YAFU prints at the beginning of nfs are some poly constants. I have looked in some of the other misc. files output during processing but have not come across a min_rels type number anywhere.

- Kevin

After the first round of sieving completes you should see a message like this:

nfs: found 336433 relations, need at least 4468504 (filtering ETA: 0h 13m), continuing with sieving ...

Which tells you both the min_rels and the ETA to the first filter. It waits to print this until after the sieve so that it can estimate the ETA...

[EdH]

Originally Posted by bsquared

After the first round of sieving completes you should see a message like this:

nfs: found 336433 relations, need at least 4468504 (filtering ETA: 0h 13m), continuing with sieving ...

Which tells you both the min_rels and the ETA to the first filter. It waits to print this until after the sieve so that it can estimate the ETA...

Is this logged somewhere other than the terminal? By the time I check this, any such message has scrolled away. I don't see it in the nfs.log. Actually, my nfs.log appears to be from an earlier session. Is the nfs.log updated as it sieves or after the fact?

[Kvasir]

Originally Posted by EdH

Is this logged somewhere other than the terminal? By the time I check this, any such message has scrolled away. I don't see it in the nfs.log. Actually, my nfs.log appears to be from an earlier session. Is the nfs.log updated as it sieves or after the fact?

Details are logged in factor.log when it's sieving and nfs.log when doing linear algebra. You can follow them using tail -f on linux, or download baretail.exe on windows.

[nivek000]

Originally Posted by bsquared

After the first round of sieving completes you should see a message like this:

nfs: found 336433 relations, need at least 4468504 (filtering ETA: 0h 13m), continuing with sieving ...

Which tells you both the min_rels and the ETA to the first filter. It waits to print this until after the sieve so that it can estimate the ETA...

I have never seen an ETA in this type of message. I must be using a different NFS library that you are. I see messages like...

12/29/21 18:10:03, final ECM pretested depth: 36.38
12/29/21 18:10:03, scheduler: switching to sieve method
12/29/21 18:10:03, nfs: commencing nfs on c152: 11047006535274396604827194619846887383623935779264657081145934950581563078251248440455538938686026540917445630537112531580439524505632520211989740047529
12/29/21 18:10:03, nfs: input divides 2^521 + 271441
12/29/21 18:10:03, nfs: using supplied cofactor: 11047006535274396604827194619846887383623935779264657081145934950581563078251248440455538938686026540917445630537112531580439524505632520211989740047529
12/29/21 18:10:03, nfs: commencing snfs on c152: 11047006535274396604827194619846887383623935779264657081145934950581563078251248440455538938686026540917445630537112531580439524505632520211989740047529
12/29/21 18:10:05, nfs: commencing lattice sieving with 8 threads
12/29/21 18:22:36, nfs: commencing lattice sieving with 8 threads

And then that continues until...

12/30/21 23:35:26, nfs: commencing lattice sieving with 8 threads
12/30/21 23:44:39, nfs: commencing msieve filtering
12/30/21 23:47:15, nfs: raising min_rels by 5.00 percent to 10579706
12/30/21 23:47:15, nfs: commencing lattice sieving with 8 threads
12/30/21 23:56:44, nfs: commencing lattice sieving with 8 threads
12/31/21 00:06:15, nfs: commencing msieve filtering
12/31/21 00:09:33, nfs: commencing msieve linear algebra
12/31/21 00:22:06, nfs: commencing msieve sqrt

The only min_rels ever output by the library I am using is if filtering fails.

If you can point me to where to download a "better" library I would be grateful.

[swellman]

What verbose level are you using? I use -v and always see what bsquared is describing. Could that be the issue?

yafu “nfs(number_to_be_factored)” -v -r -R -ns 20000000,20010000 -siever 14

Or similar syntax.

[nivek000]

So, that would be the issue. I have not been using the -v flag. With that flag I see lots of ETA values for different parts of the process. Many thanks!

- Kevin