mersenneforum.org Factoring humongous Cunningham numbers
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2020-03-27, 00:25   #1783
EdH

"Ed Hall"
Dec 2009

3×5×211 Posts

Quote:
 Originally Posted by swellman 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 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
###########################################################################

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

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

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

###########################################################################
# 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.

2020-03-27, 03:30   #1784
jyb

Aug 2005
Seattle, WA

2×13×59 Posts

Quote:
 Originally Posted by R.D. Silverman 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.

 2020-03-27, 15:47 #1785 EdH     "Ed Hall" Dec 2009 Adirondack Mtns 3×5×211 Posts 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.
2020-03-27, 16:31   #1786
R.D. Silverman

Nov 2003

1CFB16 Posts

Quote:
 Originally Posted by EdH 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

 2020-03-28, 18:34 #1787 EdH     "Ed Hall" Dec 2009 Adirondack Mtns 316510 Posts 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?
2020-03-28, 18:56   #1788
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

22×3×349 Posts

Quote:
 Originally Posted by EdH 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.

2020-03-28, 19:27   #1789
EdH

"Ed Hall"
Dec 2009

3·5·211 Posts

Quote:
 Originally Posted by VBCurtis 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.

 2020-03-28, 19:48 #1790 VBCurtis     "Curtis" Feb 2005 Riverside, CA 101348 Posts 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
2020-03-28, 20:24   #1791
EdH

"Ed Hall"
Dec 2009

3·5·211 Posts

Quote:
 Originally Posted by VBCurtis 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.

 2020-03-28, 20:38 #1792 EdH     "Ed Hall" Dec 2009 Adirondack Mtns 3×5×211 Posts 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
2020-03-28, 22:08   #1793
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

22·3·349 Posts

Quote:
 Originally Posted by EdH 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post wpolly Factoring 26 2016-07-29 04:34 Xyzzy Cunningham Tables 42 2014-04-02 18:31 jasong GMP-ECM 6 2006-06-30 08:51 jasong Factoring 1 2006-04-03 17:18 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