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

 2021-05-31, 21:43 #12 VBCurtis     "Curtis" Feb 2005 Riverside, CA 2×23×109 Posts Does CADO compute skew automagically, or does Bur need to supply it? If you need it, I suggest you use myfactors.mooo.com, "calculators" link at the top of the page. Enter your poly, and the site's script will spit out the skew that yields the highest score for that poly. That's also how I got score numbers for my previous post.
2021-06-01, 02:15   #13
charybdis

Apr 2020

7718 Posts

Quote:
 Originally Posted by VBCurtis Does CADO compute skew automagically, or does Bur need to supply it?
Oh yeah, well remembered, pretty sure CADO still needs a skew value. The standard rule for a degree d polynomial is skew = (c0/cd)^(1/d). This is not optimal in general but in real life it's close enough.

The skew controls the shape of the (a,b)-rectangle in lattice sieving, so that skew is a typical value of a/b. For the polynomials we're considering, where the algebraic norm is c5*a^5 + c0*b^5, choosing skew = (c0/c5)^(1/5) makes the two terms comparable and the norm as small as possible. If some of the other coefficients are non-zero, the calculations aren't as simple.

 2021-06-01, 08:09 #14 bur     Aug 2020 79*6581e-4;3*2539e-3 13·31 Posts Ok, so for number in my example I'd use skew = (4/1281979)^1/5 = 0.07922017839 (how many digits to use?), all else in the .poly file would be the self-constructed values I posted earlier? I just omit c4 and so on because it's zero or do I need to specify them? Then I edit the params.c120 file. "the algebraic and rational side parameters swapped (lim0 and lim1 etc)" - the 0 denotes algebraic and the 1 rational parameters? So if it says tasks.sieve.ncurves0 = 17 and tasks.sieve.ncurves1 = 20, I change that to tasks.sieve.ncurves0 = 20 and tasks.sieve.ncurves1 = 17? And the calculation of rels_wanted, you wrote lpba and lpbr, for algebraic and rational, I guess. In the params it's 0 and 1, which is which? Last fiddled with by bur on 2021-06-01 at 08:12
 2021-06-01, 09:28 #15 bur     Aug 2020 79*6581e-4;3*2539e-3 13×31 Posts And yet one more question, which number do I feed to CADO? The numbers usually have a lot of known small factors, do I divide by them? It won't have the x^5 form anymore though, but it seems in EdH's guide he just uses the unknown co-factor for CADO, also it was mentioned in this thread that divisors of these numbers also can be factored with SNFS. Last fiddled with by bur on 2021-06-01 at 10:20
2021-06-01, 10:28   #16
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

3·52·79 Posts

Quote:
 Originally Posted by bur And yet one more question, which number do I feed to CADO? The numbers usually have a lot of known small factors, do I divide by them? It won't have the x^5 form anymore though, but it seems in EdH's guide he just uses the unknown co-factor for CADO, also it was mentioned in this thread that divisors of these numbers also can be factored with SNFS.
Feed the remaining composite after small factors have been removed. The polynomial can be a multiple of the number being factored and we often use that to generate better polynomials(the polynomials must be irreducible).

2021-06-01, 10:38   #17
charybdis

Apr 2020

1111110012 Posts

Quote:
 Originally Posted by bur Ok, so for number in my example I'd use skew = (4/1281979)^1/5 = 0.07922017839 (how many digits to use?), all else in the .poly file would be the self-constructed values I posted earlier? I just omit c4 and so on because it's zero or do I need to specify them?
2 or 3 significant figures is fine though there's no harm in adding more. It should be OK to omit the coefficients that are zero.

Quote:
 Then I edit the params.c120 file. "the algebraic and rational side parameters swapped (lim0 and lim1 etc)" - the 0 denotes algebraic and the 1 rational parameters? So if it says tasks.sieve.ncurves0 = 17 and tasks.sieve.ncurves1 = 20, I change that to tasks.sieve.ncurves0 = 20 and tasks.sieve.ncurves1 = 17? And the calculation of rels_wanted, you wrote lpba and lpbr, for algebraic and rational, I guess. In the params it's 0 and 1, which is which?
Apologies, I phrased that very badly. 0 is rational and 1 is algebraic, so lpbr = lpb0 and lpba = lpb1.

Good luck!

 2021-06-01, 11:01 #18 bur     Aug 2020 79*6581e-4;3*2539e-3 13·31 Posts I calculated rels_wanted and got 44.8e6 whereas Curtis' params.c120 file has rels_wanted 31.5e6. So I'll use the lower original value? The skew from mooo.com gives 0.10906 instead 0.07 with the formula, should I go with the website's calculator? I have the following files now, does it look ok? n = (2^523*1281979+1)/740978807478081 c120.poly Code: n: 47507574309657478521751799345139218804140387137236190452560952011171490037478086338262231226836394024672540061211068254774576452771166352879924377793 skew: 0.10906 c5: 1281979 c0: 4 Y1: 1 Y0: -40564819207303340847894502572032 params.c120 (showing only the section where I modified things) Code: tasks.lim0 = 4500000 tasks.lim1 = 2500000 tasks.lpb0 = 29 tasks.lpb1 = 29 tasks.sieve.mfb0 = 54 tasks.sieve.mfb1 = 54 tasks.sieve.lambda0 = 1.81 tasks.sieve.lambda1 = 1.81 tasks.sieve.ncurves0 = 20 tasks.sieve.ncurves1 = 17 tasks.I = 13 tasks.qmin = 60000 tasks.sieve.qrange = 2000 tasks.sieve.rels_wanted = 31500000 tasks.sieve.sqside = 0 Screw work... :D Thanks a lot, I'll try and piece everything together after work. If it works I should combine it into a better organized post, otherwise all that valuable information will be hard to find. Last fiddled with by bur on 2021-06-01 at 11:44
2021-06-01, 13:17   #19
charybdis

Apr 2020

7718 Posts

Quote:
 Originally Posted by bur I calculated rels_wanted and got 44.8e6 whereas Curtis' params.c120 file has rels_wanted 31.5e6. So I'll use the lower original value? The skew from mooo.com gives 0.10906 instead 0.07 with the formula, should I go with the website's calculator?
The change to rels_wanted was only if you were using sieving parameters generated by YAFU. As you're using Curtis's file you should keep his rels_wanted. Sorry about the confusion.

Go with what the website says - the formula is really only a guideline whereas the Murphy E score gives a better idea of how a polynomial will actually perform.

Everything else looks good!

 2021-06-01, 15:10 #20 bsquared     "Ben" Feb 2007 2×1,789 Posts At the risk of increasing confusion, I ran this through yafu's poly select and it slightly prefers the other degree 5: Code: ./yafu "snfs(2^523*1281979+1,475075743096574785217517993451392188041403871372361904525609520111714037478086338262231226836394024672540061211068254774576452771166352879924377793)" -v ... gen: ======================================================== gen: selected polynomial: gen: ======================================================== n: 47507574309657478521751799345139218804140387137236190452560952011171490037478086338262231226836394024672540061211068254774576452771166352879924377793 # 1281979*2^523+1, difficulty: 163.55, anorm: 1.34e+39, rnorm: 1.18e+39 # scaled difficulty: 163.56, suggest sieving algebraic side # size = 4.795e-12, alpha = 0.784, combined = 2.207e-10, rroots = 1 type: snfs size: 163 skew: 0.0396 c5: 10255832 c0: 1 Y1: -1 Y0: 20282409603651670423947251286016 m: 20282409603651670423947251286016 But they score very close.
 2021-06-01, 15:55 #21 bur     Aug 2020 79*6581e-4;3*2539e-3 13×31 Posts The factorization completed successfully! Code: Info:Complete Factorization / Discrete logarithm: Total cpu/elapsed time for entire factorization: 68366.4/6925.44 14074467019842618596383447874291304186513827826802503924128815906893967308840587655218071 3375443932809663909086793903695124177071577045470998628634983 Slightly less than 2 hours instead of 3 days for a GNFS c149. It went back to sieving a couple of times due to me setting the rels_wanted too low as charybdis mentioned. Very nice, I'll do this for another number and then compile an how-to. Thanks again for the great help everybody! bsquared, are you using an older yafu version to circumvent the bug that was mentioned? Last fiddled with by bur on 2021-06-01 at 15:57
2021-06-01, 16:06   #22
bsquared

"Ben"
Feb 2007

2·1,789 Posts

Quote:
 Originally Posted by bur The factorization completed successfully!
Cool, good job working through this.

Quote:
 Originally Posted by bur bsquared, are you using an older yafu version to circumvent the bug that was mentioned?
No, I fixed the bug. The latest git version should work (if you use pre-compiled windows binary, you will have to wait a bit until I can rebuild that).

 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 17:54.

Thu Oct 28 17:54:27 UTC 2021 up 97 days, 12:23, 2 users, load averages: 1.60, 1.49, 1.49

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.