mersenneforum.org How to identify SNFS candidates and factor them?
 Register FAQ Search Today's Posts Mark Forums Read

2021-06-03, 13:34   #34
charybdis

Apr 2020

2·251 Posts

Quote:
 Originally Posted by bsquared I use the following as average a,b values for norm estimates (I got these from you a few months back): a = sqrt((double)(1ULL << (2 * I - 1)) * 1000000.0 * poly->poly->skew); b = sqrt((double)(1ULL << (2 * I - 1)) * 1000000.0 / poly->poly->skew); But don't take into account root properties and obviously the Q is static. If there is a better way that is nearly as simple that'd be great.
Don't think the static Q is the issue here, it's more that you're taking a and b at the edge of the sieving rectangle. The relations are concentrated towards the middle, where a and b, and therefore the norms, are smaller - and since the algebraic norm scales with the fifth power of a and b, you end up overestimating it more. Can't think of any way around this other than adding some fudge factor, but if we're going to test-sieve algebraic vs rational then this isn't too important.

Last fiddled with by charybdis on 2021-06-03 at 13:35

 2021-06-03, 13:45 #35 VBCurtis     "Curtis" Feb 2005 Riverside, CA 23·54 Posts For GNFS, Q-max to Q-min ratio around 8 is best- after Charybdis did his testing on a large job, I repeated the tests for C110-C140 and confirmed his findings. I now use Qmin = 150k for the C120 file. For SNFS, a wider ratio seems to work okay, but more testing is needed. I don't think it's a terrible idea to use 80k-1M, but if you expanded down to the 10k range you'll find that you need more raw relations because the duplicate ratio is higher (as Charybdis explained). I'd aim for Q-max to Q-min of 10x for SNFS jobs, and I wouldn't worry about it rising to around 12x on the occasions where a poly has lower-than-expected yield.
 2021-06-04, 19:04 #36 bur     Aug 2020 79*6581e-4;3*2539e-3 40110 Posts Ok, I suspected something something like those relations being not as useful, but I thought maybe it was different for SNFS. I ran a better comparison on 1281979*2^547+1 using the poly and parameters listed below and got CPU times of 123936 s for the self-constructued poly and 132316 s for the yafu poly and parameters. Yafu was going with the algebraic side again, also the parameters were slightly different from VBCurtis' ones. But the difference in total runtime is by no means as large as I had before, so disregard that. I commented the lambdas for yafu parameters as suggested by charybdis. And I just realized I forgot to switch lambda0 and lambda1 for the non-yafu run. The rels_wanted for yafu were calculated with the "fudge"-formula but turned out to be too low, the matrix was build with 17e6 relations. c125.poly Code: n: 64114249202003782174714518503455061682048018480541440980450169650489022687410445023173449432639279431900621347038011616801357412684045342625257617782577139 skew: 0.12599 c0: 8 c5: 1281979 Y0: -1298074214633706907132624082305024 Y1: 1 # f(x) = 1281979*x^5+8 # g(x) = x-1298074214633706907132624082305024 c125.yafu.poly Code: n: 64114249202003782174714518503455061682048018480541440980450169650489022687410445023173449432639279431900621347038011616801357412684045342625257617782577139 # 1281979*2^547+1, difficulty: 170.77, anorm: 9.45e+38, rnorm: 3.53e+40 # scaled difficulty: 170.77, suggest sieving algebraic side # size = 1.652e-12, alpha = 0.931, combined = 1.178e-10, rroots = 1 type: snfs #size: 170 skew: 0.0455 c0: 1 c5: 5127916 Y0: 649037107316853453566312041152512 Y1: -1 # f(x) = 5127916*x^5+1 # g(x) = -x+649037107316853453566312041152512 params.c125 Code: tasks.lim0 = 5500000 tasks.lim1 = 5500000 tasks.lpb0 = 28 tasks.lpb1 = 28 tasks.sieve.mfb0 = 54 tasks.sieve.mfb1 = 52 tasks.sieve.ncurves0 = 19 tasks.sieve.ncurves1 = 15 tasks.sieve.lambda0 = 1.83 tasks.sieve.lambda1 = 1.91 tasks.I = 13 tasks.sieve.adjust_strategy = 2 tasks.sieve.rels_wanted = 22900000 tasks.qmin = 50000 tasks.sieve.qrange = 10000 tasks.sieve.sqside = 0 params.yafu.c125 Code: tasks.lim0 = 7000000 tasks.lim1 = 7000000 tasks.lpb0 = 27 tasks.lpb1 = 27 tasks.sieve.mfb0 = 54 tasks.sieve.mfb1 = 54 tasks.sieve.ncurves0 = 15 tasks.sieve.ncurves1 = 19 #tasks.sieve.lambda0 = 1.83 #tasks.sieve.lambda1 = 1.91 tasks.I = 13 tasks.sieve.adjust_strategy = 2 tasks.sieve.rels_wanted = 10000000 tasks.qmin = 50000 tasks.sieve.qrange = 10000 tasks.sieve.sqside = 1 Last fiddled with by bur on 2021-06-04 at 19:07
2021-06-04, 23:49   #37
bsquared

"Ben"
Feb 2007

2·1,789 Posts

Quote:
 Originally Posted by charybdis @bsquared, if you're reading this - maybe worth getting YAFU to test-sieve algebraic vs rational when the estimated norms are close together?
This change has been checked in. I left the existing test sieving the same - top three polys - then if the best has norms within 5 orders of magnitude of each other it checks the opposite side.

 2021-06-30, 15:11 #38 Max0526   "Max" Jun 2016 Toronto 38A16 Posts factoring Lucas numbers by GCDs Could anybody please point me in the direction of the analog of the two formulas below, with the same/similar structure but for the Lucas numbers? I think I saw them before somewhere, they would be important for factoring to rule out the GCDs. $(F_{n-2})(F_{n-1})(F_{n+1})(F_{n+2})=F_{n}^4-1$ $(F_{n})(F_{n+2})(F_{n+3})(F_{n+5})=(F_{n+4}^2-2F_{n+3}^2)^2-1$
2021-06-30, 15:52   #39
charybdis

Apr 2020

2×251 Posts

Quote:
 Originally Posted by Max0526 Could anybody please point me in the direction of the analog of the two formulas below, with the same/similar structure but for the Lucas numbers? I think I saw them before somewhere, they would be important for factoring to rule out the GCDs. $(F_{n-2})(F_{n-1})(F_{n+1})(F_{n+2})=F_{n}^4-1$ $(F_{n})(F_{n+2})(F_{n+3})(F_{n+5})=(F_{n+4}^2-2F_{n+3}^2)^2-1$
Change all the Fs to Ls and the -1 at the end to -25.

2021-06-30, 16:18   #40
Dr Sardonicus

Feb 2017
Nowhere

4,993 Posts

Quote:
 Originally Posted by Max0526 Could anybody please point me in the direction of the analog of the two formulas below, with the same/similar structure but for the Lucas numbers? I think I saw them before somewhere, they would be important for factoring to rule out the GCDs. $(F_{n-2})(F_{n-1})(F_{n+1})(F_{n+2})=F_{n}^4-1$ $(F_{n})(F_{n+2})(F_{n+3})(F_{n+5})=(F_{n+4}^2-2F_{n+3}^2)^2-1$
The Fibonacci identity Fn+1Fn-1 - Fn*Fn = +/-1 arises from the ratio of consecutive Fibonacci numbers being convergents to a simple continued fraction [the simple continued fraction for (1 + sqrt(5))/2].

Then combining with Fn+2Fn-2 - Fn*Fn = -/+1 (don't ask me to prove it off the cuff, I'd screw it up) gives the first identity.

For Lucas numbers, [scribble scribble] the corresponding identities appear to be Ln+1Ln-1 - Ln*Ln = +/-5 and Ln+2Ln-2 - Ln*Ln = -/+5

so Ln-2Ln-1Ln+1Ln+2 = Ln4 - 25.

Vaguely similar identities for sums and differences are in this thread.

2021-06-30, 17:13   #41
Max0526

"Max"
Jun 2016
Toronto

2·3·151 Posts

Quote:
 Originally Posted by charybdis Change all the Fs to Ls and the -1 at the end to -25.
Quote:
 Originally Posted by Dr Sardonicus The Fibonacci identity Fn+1Fn-1 - Fn*Fn = +/-1 arises from the ratio of consecutive Fibonacci numbers being convergents to a simple continued fraction [the simple continued fraction for (1 + sqrt(5))/2]. Then combining with Fn+2Fn-2 - Fn*Fn = -/+1 (don't ask me to prove it off the cuff, I'd screw it up) gives the first identity. For Lucas numbers, [scribble scribble] the corresponding identities appear to be Ln+1Ln-1 - Ln*Ln = +/-5 and Ln+2Ln-2 - Ln*Ln = -/+5 so Ln-2Ln-1Ln+1Ln+2 = Ln4 - 25. Vaguely similar identities for sums and differences are in this thread.
Bingo! Thank you both so much!
Exactly what I kinda remember and was looking for!
Any idea on how to approach the conversion of the second formula to Lucas universe?

 2021-07-10, 05:21 #42 bur     Aug 2020 79*6581e-4;3*2539e-3 6218 Posts I wanted to factor the c119 co-factor of 1281979*2^559+1 and after 5% of sieving got an ETA of about 1:30 hours. A cado GNFS run had an ETA of 0:40 hours. Code: n: 12698277665702007683889275815276693326593280837281482940452961346094193789732001920277335420071981852156946378079178463 skew: 0.0958 c5: = 1281979 c0: = 2 y1: = 1 y0: = -5192296858534827628530496329220096 Did I create the polynomial wrong? But in that case cado usually fails generating the fb. edit: I used the c120 parameters because the co-factor was small and it was stated here every 30 bits I should switch to 5 digits more/less of params file. Now that I think about it, was that meant for the original Proth number? I.e. regardless of the co-factor's size if the Proth number has an exponent around 550 I should use the c125 parameters? edit2: That also wasn't the case. I did the same with the c125 params I used to factor a c155 co-factor of 1281979*2^557+1 and it had an ETA for the c119 of more than 2 hours. Is there something wrong with the polynomial? I did the "multiply by 2^n" before, it was usually slower than "pull 2^x" but not by that much and and especially not when it was 2^1, in that case it's usually faster. Last fiddled with by bur on 2021-07-10 at 05:43
 2021-07-10, 05:48 #43 axn     Jun 2003 141D16 Posts This is a case where GNFS _is_ the faster option. Although probably not by a factor of 2. Rather than SNFS on 2*(1281979*2^559+1), you could try (1281979*2^4)(2^111)^5+1 with appropriate skew which might be a shade faster. You have to chose parameters appropriate for SNFS-175 (including sieving on rational side and sieve region size), not for the composite c119. Last fiddled with by axn on 2021-07-10 at 05:49
2021-07-10, 05:59   #44
bur

Aug 2020
79*6581e-4;3*2539e-3

401 Posts

Interesting, is there a way to know if GNFS is faster or does it just turn out by experiment?

Quote:
 You have to chose parameters appropriate for SNFS-175 (including sieving on rational side and sieve region size), not for the composite c119.
Ok, that's what I did so far, I just got a bit confused.

Quote:
 (1281979*2^4)(2^111)^5+1
That's what I was trying to describe with the "pull 2^n". I usually do that, just not for exponents == 4 (mod 5), as in my experience in that case it's faster to multiply the whole expression by 2.

 Similar Threads Thread Thread Starter Forum Replies Last Post garambois Aliquot Sequences 24 2021-02-25 23:31 EdH EdH 14 2020-04-20 16:21 cochet Miscellaneous Math 4 2008-10-24 14:33 Brian-E Lounge 24 2008-08-01 14:13 Nightgamer360 Miscellaneous Math 9 2007-07-09 17:38

All times are UTC. The time now is 05:45.

Sat Oct 23 05:45:25 UTC 2021 up 92 days, 14 mins, 0 users, load averages: 1.35, 1.48, 1.39