mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2021-05-31, 21:43   #12
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

116128 Posts
Default

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.
VBCurtis is offline   Reply With Quote
Old 2021-06-01, 02:15   #13
charybdis
 
charybdis's Avatar
 
Apr 2020

2·251 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
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.
charybdis is offline   Reply With Quote
Old 2021-06-01, 08:09   #14
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

13×31 Posts
Default

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
bur is offline   Reply With Quote
Old 2021-06-01, 09:28   #15
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

1100100112 Posts
Default

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
bur is offline   Reply With Quote
Old 2021-06-01, 10:28   #16
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2·32·7·47 Posts
Default

Quote:
Originally Posted by bur View Post
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).
henryzz is offline   Reply With Quote
Old 2021-06-01, 10:38   #17
charybdis
 
charybdis's Avatar
 
Apr 2020

2·251 Posts
Default

Quote:
Originally Posted by bur View Post
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!
charybdis is offline   Reply With Quote
Old 2021-06-01, 11:01   #18
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

13×31 Posts
Default

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
bur is offline   Reply With Quote
Old 2021-06-01, 13:17   #19
charybdis
 
charybdis's Avatar
 
Apr 2020

2×251 Posts
Default

Quote:
Originally Posted by bur View Post
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!
charybdis is offline   Reply With Quote
Old 2021-06-01, 15:10   #20
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

67728 Posts
Default

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.
bsquared is offline   Reply With Quote
Old 2021-06-01, 15:55   #21
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

19316 Posts
Default

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
bur is offline   Reply With Quote
Old 2021-06-01, 16:06   #22
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

67728 Posts
Default

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

Quote:
Originally Posted by bur View Post
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).
bsquared is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
A new tool to identify aliquot sequence margins and acquisitions garambois Aliquot Sequences 24 2021-02-25 23:31
Comparison of GNFS/SNFS With Quartic (Why not to use SNFS with a Quartic) EdH EdH 14 2020-04-20 16:21
new candidates for M...46 and M48 cochet Miscellaneous Math 4 2008-10-24 14:33
Please identify! Brian-E Lounge 24 2008-08-01 14:13
Easily identify composites using multiplication Nightgamer360 Miscellaneous Math 9 2007-07-09 17:38

All times are UTC. The time now is 18:58.


Mon Oct 25 18:58:33 UTC 2021 up 94 days, 13:27, 0 users, load averages: 2.04, 2.07, 1.82

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.