mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2020-03-27, 00:25   #1783
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

3×5×211 Posts
Default

Quote:
Originally Posted by swellman View Post
Robert Balfour just reserved 9-7_269.

I can start poly searching 8+3_320 later tonight unless Ed wants it.
Go ahead and grab it. I've got irons in lots of fires and can easily move between them, when my current reservation completes.
Quote:
Originally Posted by jyb View Post
Can you tell me what parameters you're using for the sieving? Does CADO-NFS have settings that map reasonably clearly to the ones in ggnfs? I'm currently sieving for 5+3,1185L, which only has an SFNS difficulty of 222 (though it's a quartic, of course), and as expected, it's a real slog. I've been at it for about 24 hours and have only accumulated about 22M relations. Either your parameters are way better than mine, or you have a lot more hardware to throw at it than I do.
I probably have more hardware, even though it's ancient. Without counting, I'd estimate ~120 cores, with nearly half hyperthreaded.

As to the polynomial, it was generated by YAFU. The parameters are based on a modified CADO-NFS file for a c155. (Modification by VBCurtis.):
Code:
n:  182020007230135528991139915341347872965880609847705423888116875025588252350522154240713634227215698881699545439356408616763969093995140732452346538717063179710306355261
skew: 1.0000
c4: 1
c3: -1
c2: 1
c1: -1
c0: 1
Y1: -5293955920339377119177015629247762262821197509765625
Y0: 3829944921253794893077685127088430174646042802674934480896
Code:
# SNFS Test File

name = snfsTest
N = 182020007230135528991139915341347872965880609847705423888116875025588252350522154240713634227215698881699545439356408616763969093995140732452346538717063179710306355261

###########################################################################
# Polynomial selection
###########################################################################

tasks.polyselect.admin = 0
tasks.polyselect.admax = 0
tasks.polyselect.adrange = 0
tasks.polyselect.import = parameters/polynomials/snfsTest.poly

###########################################################################
# Sieve
###########################################################################

tasks.lim0 = 48938845
tasks.lim1 = 34372230
tasks.lpb0 = 32
tasks.lpb1 = 30
tasks.sieve.mfb0 = 92
tasks.sieve.mfb1 = 60
tasks.sieve.lambda0 = 3.6
tasks.sieve.lambda1 = 2.6
tasks.sieve.ncurves0 = 21
tasks.sieve.ncurves1 = 24
tasks.I = 14
tasks.qmin = 150000
tasks.sieve.qrange = 10000
tasks.sieve.rels_wanted = 75000000
tasks.sieve.sqside = 0

###########################################################################
# Filtering
###########################################################################

tasks.filter.purge.keep = 180
tasks.filter.target_density = 135.0

###########################################################################
# Linear algebra
###########################################################################

tasks.linalg.bwc.interval = 3000
tasks.linalg.bwc.interleaving = 0
tasks.linalg.m = 64
tasks.linalg.n = 64

###########################################################################
# Characters
###########################################################################

tasks.linalg.characters.nchar = 50
In looking over relations being returned, they have definitely fallen off considerably from yesterday. At the start (two days ago), each WU was returning ~25k relations, but now, I'm only seeing ~7-8k relations per WU. I still don't know how many I'll need.
EdH is offline   Reply With Quote
Old 2020-03-27, 03:30   #1784
jyb
 
jyb's Avatar
 
Aug 2005
Seattle, WA

2×13×59 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Query: How much are you skewing the (size of) the factor bases? The rational side
should have a much bigger base and LP bound. [for quartics].
Indeed, and I did test sieving in various configurations, but I think I wasn't aggressive enough in having the two sides differ. I've got a larger base and three large primes on the rational side, but the large prime bound is the same. I see that Ed's parameters are much more in line with your suggestions. A good note for next time.
jyb is offline   Reply With Quote
Old 2020-03-27, 15:47   #1785
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

3×5×211 Posts
Default

If it is of interest, I have a high rate of duplication:
Code:
Fri Mar 27 11:33:15 2020  found 43835807 duplicates and 78888962 unique relations
This is from an msieve LA test of the current set.
EdH is offline   Reply With Quote
Old 2020-03-27, 16:31   #1786
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1CFB16 Posts
Default

Quote:
Originally Posted by EdH View Post
If it is of interest, I have a high rate of duplication:
Code:
Fri Mar 27 11:33:15 2020  found 43835807 duplicates and 78888962 unique relations
This is from an msieve LA test of the current set.
The norms arising from the quartic polynomial are much smaller than those arising
from similar sized composites that use quintics/sextics. Since the norms are smaller
their factorizations will have factors that are smaller than average. This makes
collisions more likely. This is especially true with collisions with the special q. It
becomes more likely that a factor which is used as a special-q in one relation will be
just an ordinary factor in another. [and vice versa]

Last fiddled with by R.D. Silverman on 2020-03-27 at 16:31
R.D. Silverman is offline   Reply With Quote
Old 2020-03-28, 18:34   #1787
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

316510 Posts
Default

I appear to be a long way from a matrix:
Code:
Sat Mar 28 08:54:11 2020  found 40627050 hash collisions in 149142208 relations
Sat Mar 28 08:54:26 2020  added 3657700 free relations
Sat Mar 28 08:54:26 2020  commencing duplicate removal, pass 2
Sat Mar 28 09:09:38 2020  found 54439971 duplicates and 98359937 unique relations
Sat Mar 28 09:09:38 2020  memory use: 852.8 MB
Sat Mar 28 09:09:38 2020  reading ideals above 114229248
Sat Mar 28 09:09:38 2020  commencing singleton removal, initial pass
Sat Mar 28 09:31:10 2020  memory use: 3012.0 MB
Sat Mar 28 09:31:10 2020  reading all ideals from disk
Sat Mar 28 09:32:09 2020  memory use: 1945.9 MB
Sat Mar 28 09:32:15 2020  commencing in-memory singleton removal
Sat Mar 28 09:32:20 2020  begin with 98359937 relations and 136284566 unique ideals
Sat Mar 28 09:32:33 2020  reduce to 3135035 relations and 475585 ideals in 17 passes
Sat Mar 28 09:32:33 2020  max relations containing the same ideal: 7
Sat Mar 28 09:32:33 2020  reading ideals above 100000
Sat Mar 28 09:32:33 2020  commencing singleton removal, initial pass
Sat Mar 28 09:41:15 2020  memory use: 376.5 MB
Sat Mar 28 09:41:15 2020  reading all ideals from disk
Sat Mar 28 09:41:15 2020  memory use: 129.4 MB
Sat Mar 28 09:41:15 2020  commencing in-memory singleton removal
Sat Mar 28 09:41:16 2020  begin with 3717125 relations and 14228244 unique ideals
Sat Mar 28 09:41:16 2020  reduce to 2382 relations and 0 ideals in 4 passes
Sat Mar 28 09:41:16 2020  max relations containing the same ideal: 0
Sat Mar 28 09:41:16 2020  filtering wants 1000000 more relations
And, relations are now being found at well less that 7k/WU.

I'm almost wondering if I should cancel this snfs run and restart as a gnfs run. If msieve won't build a matrix, I might be looking at the CADO-NFS LA taking longer than a restart with gnfs.

Thoughts?
EdH is offline   Reply With Quote
Old 2020-03-28, 18:56   #1788
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

22×3×349 Posts
Default

Quote:
Originally Posted by EdH View Post
I appear to be a long way from a matrix:
Code:
Sat Mar 28 09:32:15 2020  commencing in-memory singleton removal
Sat Mar 28 09:32:20 2020  begin with 98359937 relations and 136284566 unique ideals
Sat Mar 28 09:32:33 2020  reduce to 3135035 relations and 475585 ideals in 17 passes
Sat Mar 28 09:32:33 2020  max relations containing the same ideal: 7
And, relations are now being found at well less that 7k/WU.

Thoughts?
Note that after duplicate removal, you have 98M relations and 136M ideals. Compare those to a successful filtering run with similar bounds, and you'll get an idea of how much longer you have to go. I'd say you need 40M more unique rels, at minimum; so you're about 2/3rds done.
VBCurtis is offline   Reply With Quote
Old 2020-03-28, 19:27   #1789
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

3·5·211 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
Note that after duplicate removal, you have 98M relations and 136M ideals. Compare those to a successful filtering run with similar bounds, and you'll get an idea of how much longer you have to go. I'd say you need 40M more unique rels, at minimum; so you're about 2/3rds done.
Since the relations being returned have fallen from over 25k to ~6k per WU, doesn't that become about 1/6th done relative to time? At 4+ days in, that means quite a bit longer before I can even start LA, which will take several days.
EdH is offline   Reply With Quote
Old 2020-03-28, 19:48   #1790
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

101348 Posts
Default

If memory requirements allow, you could try restarting the server with A bumped by 1, or I.
That is, if you're running I=14, you could change that line from tasks.I=14 to tasks.A=28.
That's only going to work if your clients are running a fairly recent CADO version, though- I don't think A was a "thing" until 8/2019 or so.

Going all the way to I=15 is a 4x increase in memory, while A=28 only doubles memory needs.

While your yield is way down, I don't think sec/rel falls in the same way. That is, workunits are going by more quickly.

EDIT: If there is a range of low Q you didn't do, I'd do those with I=15. Say, Q=100k to the Q-min you selected. You could even use A=30; desperate jobs call for desperate measures!

Last fiddled with by VBCurtis on 2020-03-28 at 19:50
VBCurtis is offline   Reply With Quote
Old 2020-03-28, 20:24   #1791
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

3·5·211 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
If memory requirements allow, you could try restarting the server with A bumped by 1, or I.
That is, if you're running I=14, you could change that line from tasks.I=14 to tasks.A=28.
That's only going to work if your clients are running a fairly recent CADO version, though- I don't think A was a "thing" until 8/2019 or so.

Going all the way to I=15 is a 4x increase in memory, while A=28 only doubles memory needs.

While your yield is way down, I don't think sec/rel falls in the same way. That is, workunits are going by more quickly.

EDIT: If there is a range of low Q you didn't do, I'd do those with I=15. Say, Q=100k to the Q-min you selected. You could even use A=30; desperate jobs call for desperate measures!
A few of my machines won't run the later version, but most are at whatever was available at the end of 2019. My server is using an older version, though, since I got tired of restarting it to kick the WU issuing back in. I could easily go back to the latest and restart, though.

Oddly, I'm showing a 28% memory use on both a 6GB 8 thread and a 8GB 4 thread machine. I guess I should stay away from I=15. I suppose I could always try the A=28 route and see which ones fail.

I guess for the moment, I'll see if I can extract some data on WU cycling times and see where that is headed.

My qmin was already at 150k, so not too much room left there.

Thanks for all the help.
EdH is offline   Reply With Quote
Old 2020-03-28, 20:38   #1792
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

3×5×211 Posts
Default

Well, I've added 10M more relations in the last 6.5 hours, so maybe the return isn't as bad as I thought. But, OTOH, msieve knocked them all down to the same 2382 relations by the end.
Code:
Sat Mar 28 15:35:59 2020  found 43577634 hash collisions in 159168080 relations
Sat Mar 28 15:36:13 2020  added 3657717 free relations
Sat Mar 28 15:36:13 2020  commencing duplicate removal, pass 2
Sat Mar 28 15:41:16 2020  found 58150363 duplicates and 104675434 unique relations
Sat Mar 28 15:41:16 2020  memory use: 852.8 MB
Sat Mar 28 15:41:16 2020  reading ideals above 114229248
Sat Mar 28 15:41:16 2020  commencing singleton removal, initial pass
Sat Mar 28 16:06:59 2020  memory use: 3012.0 MB
Sat Mar 28 16:06:59 2020  reading all ideals from disk
Sat Mar 28 16:07:17 2020  memory use: 2087.7 MB
Sat Mar 28 16:07:23 2020  commencing in-memory singleton removal
Sat Mar 28 16:07:28 2020  begin with 104675434 relations and 140890929 unique ideals
Sat Mar 28 16:07:41 2020  reduce to 3251271 relations and 559067 ideals in 17 passes
Sat Mar 28 16:07:41 2020  max relations containing the same ideal: 7
Sat Mar 28 16:07:41 2020  reading ideals above 100000
Sat Mar 28 16:07:41 2020  commencing singleton removal, initial pass
Sat Mar 28 16:11:52 2020  memory use: 376.5 MB
Sat Mar 28 16:11:52 2020  reading all ideals from disk
Sat Mar 28 16:11:52 2020  memory use: 134.9 MB
Sat Mar 28 16:11:53 2020  commencing in-memory singleton removal
Sat Mar 28 16:11:53 2020  begin with 3833373 relations and 14396078 unique ideals
Sat Mar 28 16:11:53 2020  reduce to 2382 relations and 0 ideals in 4 passes
Sat Mar 28 16:11:53 2020  max relations containing the same ideal: 0
Sat Mar 28 16:11:53 2020  filtering wants 1000000 more relations
EdH is offline   Reply With Quote
Old 2020-03-28, 22:08   #1793
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

22·3·349 Posts
Default

Quote:
Originally Posted by EdH View Post
Well, I've added 10M more relations in the last 6.5 hours, so maybe the return isn't as bad as I thought. But, OTOH, msieve knocked them all down to the same 2382 relations by the end.
Code:
Sat Mar 28 16:07:23 2020  commencing in-memory singleton removal
Sat Mar 28 16:07:28 2020  begin with 104675434 relations and 140890929 unique ideals
Sat Mar 28 16:07:41 2020  reduce to 3251271 relations and 559067 ideals in 17 passes
Sat Mar 28 16:07:41 2020  max relations containing the same ideal: 7
Focus here, not on the final filtering result. When you're halfway through gathering relations, "all" of the relations will have a singleton prime. As you gather more relations, more of the primes pair up and thus more survive the singleton-removal phase.

You gained 6M relations and 4M ideals since your previous post, but future counts will see the ideal count grow more slowly; that is, more factors will match previous factors rather than becoming new singletons.
VBCurtis is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
New phi for homogeneous Cunningham numbers wpolly Factoring 26 2016-07-29 04:34
Mathematics of Cunningham Numbers (3rd ed., 2002, A.M.S.) Xyzzy Cunningham Tables 42 2014-04-02 18:31
Don't know how to work on Cunningham numbers. jasong GMP-ECM 6 2006-06-30 08:51
Doing Cunningham numbers but messed up. jasong Factoring 1 2006-04-03 17:18
Need help factoring Cunningham numbers jasong Factoring 27 2006-03-21 02:47

All times are UTC. The time now is 11:33.

Sat Jun 6 11:33:20 UTC 2020 up 73 days, 9:06, 0 users, load averages: 9.37, 3.65, 2.38

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.