mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2021-06-03, 13:34   #34
charybdis
 
charybdis's Avatar
 
Apr 2020

5×101 Posts
Default

Quote:
Originally Posted by bsquared View Post
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
charybdis is offline   Reply With Quote
Old 2021-06-03, 13:45   #35
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

501010 Posts
Default

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.
VBCurtis is online now   Reply With Quote
Old 2021-06-04, 19:04   #36
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

13×31 Posts
Default

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

2×1,789 Posts
Default

Quote:
Originally Posted by charybdis View Post
@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.
bsquared is offline   Reply With Quote
Old 2021-06-30, 15:11   #38
Max0526
 
"Max"
Jun 2016
Toronto

2·3·151 Posts
Default 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
Max0526 is offline   Reply With Quote
Old 2021-06-30, 15:52   #39
charybdis
 
charybdis's Avatar
 
Apr 2020

5×101 Posts
Default

Quote:
Originally Posted by Max0526 View Post
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.
charybdis is offline   Reply With Quote
Old 2021-06-30, 16:18   #40
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

5,009 Posts
Default

Quote:
Originally Posted by Max0526 View Post
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.
Dr Sardonicus is offline   Reply With Quote
Old 2021-06-30, 17:13   #41
Max0526
 
"Max"
Jun 2016
Toronto

2·3·151 Posts
Default

Quote:
Originally Posted by charybdis View Post
Change all the Fs to Ls and the -1 at the end to -25.
Quote:
Originally Posted by Dr Sardonicus View Post
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?
Max0526 is offline   Reply With Quote
Old 2021-07-10, 05:21   #42
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

13×31 Posts
Default

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
bur is offline   Reply With Quote
Old 2021-07-10, 05:48   #43
axn
 
axn's Avatar
 
Jun 2003

3·17·101 Posts
Default

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
axn is offline   Reply With Quote
Old 2021-07-10, 05:59   #44
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

13·31 Posts
Default

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.
bur 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 04:30.


Wed Oct 27 04:30:59 UTC 2021 up 95 days, 22:59, 0 users, load averages: 1.26, 1.54, 1.64

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.