mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2021-06-09, 03:00   #166
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

66748 Posts
Default

Remaining composites for (4,-9) and (3,-9) got more work at 11M, no more factors.

Code:
06/08/21 17:59:09, Finished 5120 curves using AVX-ECM method on C198 input, B1=11M, B2=1100M
06/08/21 19:00:52, Finished 5120 curves using AVX-ECM method on C203 input, B1=11M, B2=1100M
06/08/21 19:42:15, Finished 5120 curves using AVX-ECM method on C168 input, B1=11M, B2=1100M
06/08/21 20:43:55, Finished 5120 curves using AVX-ECM method on C234 input, B1=11M, B2=1100M
Line 123 point (8,-9) is currently blank... I'll run some curves on those 6 composites overnight.

[edit]
Several small factors removed, now a c130, c235, c287, and c300 remaining. I'll finish the c130 by gnfs and finish curves at 11M on the others. c130 split by ECM.

[edit2]
The c199 of point (8,9) has survived 13056 curves at 43M. I will finish by snfs if I can get a poly for it.

Last fiddled with by bsquared on 2021-06-09 at 03:42
bsquared is offline   Reply With Quote
Old 2021-06-09, 07:16   #167
bur
 
bur's Avatar
 
Aug 2020

22×3×52 Posts
Default

Quote:
Originally Posted by Max0526 View Post
Please let me know if anything is off.
Code:
(10, -4) c165 / snfs198 --> poly 1
Cado is running, but finds very few relations already at low q, about 3000-5000 rel / 10,000 q, ETA right now (0.3% done) is 34 hours, though that usually increases. Much faster than GNFS (7-8 days on that machine), but the low number of rels seems strange to me.

I used your equations to calculate the parameters and tried some variations, but it didn't do much. I tried algebraic and rational side sieving.

Here's the latest parameters I used (note the commented lines). Cado chose 17,000,000 relations wanted.

Code:
tasks.lim0 = 13600000
tasks.lim1 = 13600000
tasks.lpb0 = 28
tasks.lpb1 = 27
tasks.sieve.mfb0 = 55
tasks.sieve.mfb1 = 54
tasks.sieve.lambda0 = 2.5
tasks.sieve.lambda1 = 2.5
#tasks.sieve.ncurves0 = 20
#tasks.sieve.ncurves1 = 17
tasks.I = 13
tasks.qmin = 200000
tasks.sieve.qrange = 10000
#tasks.sieve.rels_wanted = 35000000
tasks.sieve.sqside = 0
lim seems quite high, is that correct? And both Y0 and Y1 are positive, I think I once read this shouldn't be the case, is that correct?

That's the poly:
Code:
n: 763374743763081217914694138634486780344024237091539368674972788624046972741046710708718787293421106975357383724033172253608940141301420411687874833865804305796864727
skew: 5.27952
c4: 1
c3: -12
c2: 62
c1: -168
c0: 196
Y1: 1419008023915103851777842927951067360939048893550
Y0: 23208752137879949244324153950621937803310882681351

Last fiddled with by bur on 2021-06-09 at 07:18
bur is offline   Reply With Quote
Old 2021-06-09, 13:18   #168
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

28·19 Posts
Default

I'd raise both large prime bounds by 2, and both mfb's by 4.
I'd consider I=13 and I=14, using whichever sieved faster (lower ETA after, say, 1% of the job or a couple workunits per client had finished). If the ETAs are close, use the larger siever as it will generate fewer duplicate relations and thus gain time in a hidden way.
VBCurtis is online now   Reply With Quote
Old 2021-06-09, 13:55   #169
bur
 
bur's Avatar
 
Aug 2020

22×3×52 Posts
Default

For I=13 that results in 18000 rels / 10000 q, but also in 63e6 rels wanted and an ETA of 38 h (34 h for initial parameters), so unless the previous relations were grossly underestimated that wouldn't be a gain.

I=14 yields even more rels/q (47000rels/10000q), but since sieving takes longer, so ETA after 0.4% is 44 hours.


So if the rels-wanted estimated by cado for the initial parameters is correct, I should continue with them, especially since I already sieved for some hours. On the other hand, if the 63e6 is overestimated, then these new parameters would be much faster.

Using the equation from the SNFS thread, the relations cado choose seems good. I get 15e6 for the inital parameters (28/27) and 68e6 for the new ones (30/29).

Last fiddled with by bur on 2021-06-09 at 14:41
bur is offline   Reply With Quote
Old 2021-06-09, 15:00   #170
Max0526
 
"Max"
Jun 2016
Toronto

19·47 Posts
Default

Quote:
Originally Posted by bsquared View Post
Remaining composites for (4,-9) and (3,-9) got more work at 11M, no more factors.

Code:
06/08/21 17:59:09, Finished 5120 curves using AVX-ECM method on C198 input, B1=11M, B2=1100M
06/08/21 19:00:52, Finished 5120 curves using AVX-ECM method on C203 input, B1=11M, B2=1100M
06/08/21 19:42:15, Finished 5120 curves using AVX-ECM method on C168 input, B1=11M, B2=1100M
06/08/21 20:43:55, Finished 5120 curves using AVX-ECM method on C234 input, B1=11M, B2=1100M
Line 123 point (8,-9) is currently blank... I'll run some curves on those 6 composites overnight.

[edit]
Several small factors removed, now a c130, c235, c287, and c300 remaining. I'll finish the c130 by gnfs and finish curves at 11M on the others. c130 split by ECM.

[edit2]
The c199 of point (8,9) has survived 13056 curves at 43M. I will finish by snfs if I can get a poly for it.
bsquared, do you want to do line 105 first?
(9, 8) http://factordb.com/index.php?id=1100000002598671066 c158/snfs188 (survived t40 2800@B1=3M) c169 split by GCD; Stargate38 -- 1; bsquared -- 1; 4 SNFS polys are coming for c158
Max0526 is offline   Reply With Quote
Old 2021-06-09, 15:45   #171
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

114008 Posts
Default

Quote:
Originally Posted by bur View Post
For I=13 that results in 18000 rels / 10000 q, but also in 63e6 rels wanted and an ETA of 38 h (34 h for initial parameters), so unless the previous relations were grossly underestimated that wouldn't be a gain.

I=14 yields even more rels/q (47000rels/10000q), but since sieving takes longer, so ETA after 0.4% is 44 hours.


So if the rels-wanted estimated by cado for the initial parameters is correct, I should continue with them, especially since I already sieved for some hours. On the other hand, if the 63e6 is overestimated, then these new parameters would be much faster.

Using the equation from the SNFS thread, the relations cado choose seems good. I get 15e6 for the inital parameters (28/27) and 68e6 for the new ones (30/29).
I agree that I=14 sounds slower; my experience is that I need about 10% fewer relations for a given job when going up a siever, but that 10% lower won't make up 6 hours.

I'm curious to hear how many relations / hours this job needs at the smaller parameters you chose; this thread may not be the place for it, you can PM me details if you decide not to post about them. I don't run jobs that have initial yield below 3.5 (35k relations per 10kQ), but that doesn't make it right.

Last fiddled with by VBCurtis on 2021-06-09 at 15:46 Reason: typo 8 hours -> 6 hours
VBCurtis is online now   Reply With Quote
Old 2021-06-09, 16:19   #172
swishzzz
 
Jan 2012
Toronto, Canada

10101112 Posts
Default

Quote:
Originally Posted by swishzzz View Post
I'll take both composites in (5, 10). The c188 looks like a very similar sized SNFS to what I booked previously and the c146 will be an interesting GNFS target to compare the timings to vs the c188 (assuming both survive ECM).
c188 = p51 * c138 by ECM, looks like I'll be doing both by GNFS - no polys needed.
swishzzz is offline   Reply With Quote
Old 2021-06-09, 16:55   #173
Max0526
 
"Max"
Jun 2016
Toronto

89310 Posts
Default GCD run on June 8

@swishzzz
I attach a copy of my output. I used radius 2 instead of 1 (<=2 at the end of the line in your script). As expected, there were diagonal points with long GCDs (not anymore, as far as I see, we are just too fast at factoring).
I will post my math analysis a bit later. For now, it seems that the factors of the 6th poly in the Magma script (x^4 - 24*x^3 + 152*x^2 - 336*x + 196, where x = a) can be (at least sometimes) recovered by 2 GCDs on three consecutive points (x-1, y), (x, y), and (x+1, y).
Attached Files
File Type: txt GCD.run.txt (9.8 KB, 15 views)

Last fiddled with by Max0526 on 2021-06-09 at 17:03
Max0526 is offline   Reply With Quote
Old 2021-06-09, 18:04   #174
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

351610 Posts
Default

Quote:
Originally Posted by Max0526 View Post
bsquared, do you want to do line 105 first?
(9, 8) http://factordb.com/index.php?id=1100000002598671066 c158/snfs188 (survived t40 2800@B1=3M) c169 split by GCD; Stargate38 -- 1; bsquared -- 1; 4 SNFS polys are coming for c158
Sure. I was able to create this poly using your instructions in post 27.

Code:
n: 65450905747953132329287628843212925588466942908707926747521851453432385566465577084163919043429825490519033179336453712931411833277467544260317417144700707839
type: snfs
skew: 3.741
c4: 1
c3: -6
c2: 17
c1: -84
c0: 196
Y0: 31163499011003626601359716776483379457194762910
Y1: 15539382401903125112142699946841259192950669329
I don't know how you are making your 3rd and 4th poly alternatives... did I miss those instructions somewhere?

Over my lunch hour I modified yafu to be able to read in these polynomials and suggest parameters. yafu has some built-in heuristics for skewing polynomials with badly mismatched norms. This is what it came up with for this poly, sieving with 13e on the rational side:

Code:
rlim: 6955967
alim: 5208806
lpbr: 29
lpba: 27
mfbr: 58
mfba: 54
rlambda: 2.5
alambda: 2.5
Anyone: feel free to get the newest .git version of yafu if you want to build and try this out, but fair warning that it isn't tested much yet!
bsquared is offline   Reply With Quote
Old 2021-06-09, 18:25   #175
Max0526
 
"Max"
Jun 2016
Toronto

19×47 Posts
Default

Quote:
Originally Posted by bsquared View Post
Sure. I was able to create this poly using your instructions in post 27.

Code:
n: 65450905747953132329287628843212925588466942908707926747521851453432385566465577084163919043429825490519033179336453712931411833277467544260317417144700707839
type: snfs
skew: 3.741
c4: 1
c3: -6
c2: 17
c1: -84
c0: 196
Y0: 31163499011003626601359716776483379457194762910
Y1: 15539382401903125112142699946841259192950669329
I don't know how you are making your 3rd and 4th poly alternatives... did I miss those instructions somewhere?

For the 3rd and 4th SNFS polys please see https://mersenneforum.org/showpost.p...&postcount=132
Max0526 is offline   Reply With Quote
Old 2021-06-09, 18:37   #176
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

22×3×293 Posts
Default

Quote:
Originally Posted by Max0526 View Post
For the 3rd and 4th SNFS polys please see https://mersenneforum.org/showpost.p...&postcount=132
Thanks! Sorry I missed that.

The 4 possible polys scores I see are:

a1 Murphy = 1.533000e-11
a2 Murphy = 9.510000e-12
a3 Murphy = 1.335000e-11
a4 Murphy = 1.274000e-11

So the first one is the best.

I have been getting the rational coefficient variations by plugging the following into wolfram alpha, where obviously the a1 changes based on the magma output:

Code:
a1 = -31163499011003626601359716776483379457194762910/15539382401903125112142699946841259192950669329; a2=7*(a1-4)/(2*a1-7); a3 = 14/a1; a4 = 2*(2*a1-7)/(a1-4)

Last fiddled with by bsquared on 2021-06-09 at 18:37
bsquared is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
factoring 2ⁿ-2 equivalent to factoring 2ⁿ-1(I think) baih Miscellaneous Math 9 2020-09-21 07:11
OpenCL GPU P-1 Factoring and ECM Factoring xx005fs GPU Computing 3 2018-10-27 14:49

All times are UTC. The time now is 07:25.


Sat Jul 24 07:25:36 UTC 2021 up 1 day, 1:54, 1 user, load averages: 1.82, 1.62, 1.48

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.