mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > CADO-NFS

Reply
 
Thread Tools
Old 2021-07-20, 13:19   #12
charybdis
 
charybdis's Avatar
 
Apr 2020

17·29 Posts
Default

Quote:
Originally Posted by bur View Post
So having an SNFS-177 take as long as a GNFS-139 really seems a bit long? I thought it might be due to the large coeffcient but the steep increase surprised me.
It was the 4-digit increase in GNFS equivalent difficulty for a 3-digit increase in SNFS difficulty that surprised me. Judging by the E scores of the polynomials, I would have expected them to sieve more like GNFS-134 and 135, so the second number has taken longer than it should have done. I'm especially surprised given that you used the same parameters for both numbers. Are you sure you didn't have any other processes slowing the second job down?

I'd have used roughly c135 parameters for both jobs given the E scores.

Quote:
I managed to build a matrix using msieve with 60M relations. From my experience msieve tends to require more relations than cado to build a matrix (why is that?), so for the current factorization I decreased rels_wanted to 60M.
I think the CADO filtering tools are just slightly better tuned than msieve. I've never tried this, but it's possible that playing around with some of the additional arguments for -nc1 might allow msieve to build a matrix with slightly fewer relations.

If the rels_wanted figure was off for the c135 parameters, maybe it was off for the c130 parameters too. That still doesn't explain the discrepancy between the two numbers.

By the way, it is essential to add tasks.sieve.adjust_strategy = 2 whenever you use tasks.A = [even number] rather than tasks.I. There should be a noticeable speedup.
charybdis is offline   Reply With Quote
Old 2021-07-20, 16:20   #13
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

6168 Posts
Default

Quote:
Originally Posted by charybdis View Post
By the way, it is essential to add tasks.sieve.adjust_strategy = 2 whenever you use tasks.A = [even number] rather than tasks.I. There should be a noticeable speedup.
Then that might be a big part of the problem, I didn't include it in the params file.


Other than that, I don't remember the exact point of this increase but it was quite sudden. I found a possible explanation though. I don't do every number by SNFS since most are factored by easy ECM. So it might have been that I compared a number with an exponent divisible by 5 to one that was == 4 (mod 5).


SNFS-179 number 1281979*2^594+1 with polynomial 1281979*2^4*(2^118)^5+1 has an E-score of 3.365E-11 while the SNFS-175 number 1281979*2^580+1 yields an E-score of 5.747E-11. I am not sure how strongly that affects sieving times, but the former E-score is 42% lower, so it might be quite significant?


Add to that the problem with the missing adjust_strategy and it might explain everything.

Last fiddled with by bur on 2021-07-20 at 16:21
bur is offline   Reply With Quote
Old 2021-07-20, 17:42   #14
charybdis
 
charybdis's Avatar
 
Apr 2020

17×29 Posts
Default

Quote:
Originally Posted by bur View Post
SNFS-179 number 1281979*2^594+1 with polynomial 1281979*2^4*(2^118)^5+1 has an E-score of 3.365E-11 while the SNFS-175 number 1281979*2^580+1 yields an E-score of 5.747E-11. I am not sure how strongly that affects sieving times, but the former E-score is 42% lower, so it might be quite significant?
The E-score is supposed to be directly proportional to yield for a fixed set of parameters, so you'd expect the number with the lower score here to take about 70% longer if the parameters remain the same. You can reduce that 70% figure a bit by using slightly different parameters for the two jobs, but this E-score ratio is consistent with a 3-4 digit increase in GNFS equivalent difficulty.
charybdis is offline   Reply With Quote
Old 2021-07-20, 18:10   #15
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

2×199 Posts
Default

Alright, thanks. The tasks.sieve.adjust_strategy = 2, is there a general rule if it's useful for SNFS or not? And if I was to test and change this back to 0, I should probably also revert to tasks.I? From the manual either 13 or 14 would correspond to A = 26, correct?
bur is offline   Reply With Quote
Old 2021-07-20, 18:59   #16
charybdis
 
charybdis's Avatar
 
Apr 2020

17×29 Posts
Default

tasks.I = n corresponds to tasks.A = 2n-1, so A=26 is between I=13 and I=14.

If you're using an even value of A, you should use adjust_strategy = 2 whatever the circumstances. For tasks.I (in other words, odd values of A), VBCurtis's testing showed that adjust_strategy = 2 is advantageous for GNFS from around 125 digits upwards, though the difference in speed is very small. I don't think much SNFS testing has been done but I'd expect the dynamics to be similar, i.e. use strategy 2 for SNFS jobs of difficulty equivalent to GNFS-125 or higher.
charybdis is offline   Reply With Quote
Old 2021-07-21, 05:45   #17
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

2·199 Posts
Default

Yes, according to CADO manual A can be used to fine-tune that parameter. So for integer values of I (or odd values of A) it doesn't matter which one is used?


This 188 digit 2^602*1281979+1 took 9:20 for sieving, even with adjust_strategy. So I guess it is just a peculiarity of these SNFS numbers that the E-scores are low and sieving takes long.


Btw, is the only difference between GNFS and SNFS that the latter has a simple polynomial? Earlier I was under the impression that SNFS was having a different sieving process, but it doesn't seem so. Or does cado recognize the SNFS type polynomial and internally switches to "SNFS"?
bur is offline   Reply With Quote
Old 2021-07-21, 11:37   #18
charybdis
 
charybdis's Avatar
 
Apr 2020

17×29 Posts
Default

The advantage for adjust_strategy=2 with integer I seems to get greater for larger jobs. I don't know why this happens, but it does. So if you're doing a big job then you definitely will want strategy 2: saving 5% of sieving time on a c180 GNFS is absolutely worth it.

I don't know how your timings for GNFS and other SNFS jobs compare, so I can't tell what counts as slow. If you're meaning that these SNFS jobs take longer than the "rules of thumb" for SNFS-GNFS conversion indicate, then yes - that's because of the large c5 coefficient.

There is no difference between the SNFS and GNFS algorithms once we've got a polynomial. SNFS just means the special form of the number allows a polynomial to be easily found, usually with small coefficients. (Historical note: in the early days, there was more of a difference, because SNFS was initially only developed for numbers of the form b^n +- c where the algebraic number theory is easier.)
charybdis is offline   Reply With Quote
Old 2021-07-22, 06:38   #19
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

2×199 Posts
Default

Ok thanks, good to know.
bur is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
I found the primality test, there seems to be no composite numbers that pass the test sweety439 sweety439 7 2020-02-11 19:49
Modifying the Lucas Lehmer Primality Test into a fast test of nothing Trilo Miscellaneous Math 25 2018-03-11 23:20
Advantage of lattice sieve over line sieve binu Factoring 3 2013-04-13 16:32
Double check LL test faster than first run test lidocorc Software 3 2008-12-03 15:12
A primality test for Fermat numbers faster than P├ępin's test ? T.Rex Math 0 2004-10-26 21:37

All times are UTC. The time now is 03:31.


Mon Oct 18 03:31:36 UTC 2021 up 86 days, 22 hrs, 0 users, load averages: 1.32, 1.21, 1.13

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.