mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2013-10-12, 14:24   #1
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

5×13×53 Posts
Default Poly Search vs Sieving times

Sorry for the neophyte question, but for smaller composites ~150 digits across multiple machines, is there a real gain in overall sieving if a poly with a greater than expected E score is found early in the search?

Specifics:
Code:
Msieve v. 1.52 (SVN 886)
random seeds: 55df12b7 e5d3c816
factoring 218876969782929216599190531580538390484044829345681891460187089862281796240529496476113446316632558113449224677358919720113328517497603198421529 (144 digits)
searching for 15-digit factors
commencing number field sieve (144-digit input)
commencing number field sieve polynomial selection
polynomial degree: 5
max stage 1 norm: 8.34e+21
max stage 2 norm: 1.39e+20
min E-value: 1.03e-11
poly select deadline: 311905
time limit set to 86.64 CPU-hours
expecting poly E from 1.12e-11 to > 1.29e-11
(The msieve machine has four cores and I hard set the search time to 12 hours.)

The following poly was found within the first few minutes:
Code:
# norm 8.158791e-14 alpha -8.748871 e 1.309e-11 rroots 5
skew: 52981938.39
c0: 5925697648913135366967245004294844179177
c1: 468536815244189902014756820336233
c2: -26076232373209850831435621
c3: -542019174557361769
c4: 10239243052
c5: 48
Y0: -21467961164039091417408999106
Y1: 1118175346469539
I'm running several machines and expect the sieving and LA to take approximately four days. (Of course, I may be way off.)

Would a better poly outweigh the 11 hours of search time left for a 48-60 hour project?

Thanks...

Last fiddled with by EdH on 2013-10-12 at 14:26 Reason: added info
EdH is online now   Reply With Quote
Old 2013-10-12, 17:38   #2
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

41·109 Posts
Default

If the "expected score" is accurate at this size, you should not search further. You may well find a poly that's 5% faster by completing the search, but it's pretty clear that 5% of sieve time is greater than the poly-search time.

However, the Expected Score code is simply guesswork- without previous experience about its accuracy, you don't know if you might improve by 10% or more. I'd compromise, and search a couple more hours- if nothing comes close in that time, I'd assume I got lucky at the outset and proceed to sieving.

A5 coefficients below 10000 should not be searched- msieve takes longer at very low A5 values to do the same work. Also note skew is 50M, very high for this size of number; this occasionally causes hiccups in later stages (I have not run into such a hiccup yet, but I follow Frmky's advice to use large A5, say 5-50M for this size number). Large A5 coefficients have lower skews than very small values.
VBCurtis is offline   Reply With Quote
Old 2013-10-12, 18:32   #3
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

5×13×53 Posts
Default

Thanks!

My impatience got me to break in at about 2.5 hours of searching and that was the poly chosen - no others were close.

My first set of relations came in at 2.2% of the estimated minimum (32523338) in about 1.2 hours. This calculates to (very) roughly 55 hours for sieving, although a couple of the machines will be off at night.

I guess I'll see how it turns out...
EdH is online now   Reply With Quote
Old 2013-10-12, 19:44   #4
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

5·13·53 Posts
Default

Wow! I have a new estimate for sieving time of ~26 hours. I guess the first estimate hadn't received relations from several of the machines. I'll have to see how it works out in reality.

The "Wow!" part is that I remember taking over two weeks to factor c100s...
EdH is online now   Reply With Quote
Old 2013-10-13, 14:14   #5
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

5·13·53 Posts
Default

There I was!

closing in on a matrix,

when the power company lost control,

and my scripts weren't robust enough to carry through a restart,

so I had to resort to semi-manually* completing the job.

So much for an accurate timing for this composite factorization...

Oh, well, if anything good has come of it, it got me off my a** to place the main factoring machine on a UPS that was already sitting there, waiting to be put into use...

*semi-manually meaning a manual restart of factmsieve.py and manually concatenating all the relations from those machines that are still running...
EdH is online now   Reply With Quote
Old 2013-10-13, 18:05   #6
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

5×13×53 Posts
Default

Well, that didn't work.

Now I'm lost!

factmsieve.py wouldn't restart - kept giving an error 255. Renamed number.dat.cyc and that cleared the factmsieve.py error. But, number.dat was trashed. Rebuilt that, but factmsieve.py wouldn't go anywhere, so I have moved to msieve direct entry. Now all I get are -11 errors for the entire 4G number.dat file. Currently, I'm retrieving the rels from the spairs.save.gz file to see if I can get anywhere from there.

Last fiddled with by EdH on 2013-10-13 at 18:08 Reason: removed erroneous info
EdH is online now   Reply With Quote
Old 2013-10-13, 19:45   #7
wombatman
I moo ablest echo power!
 
wombatman's Avatar
 
May 2013

5·347 Posts
Default

One thing to try is restoring the relations found using the spairs.gz file like you're doing, deleting all the .cyc and such, and then rerunning using the "-nc" command. That should take of it, if I understand your error correctly. I've had to do that before when my .dat file disappeared.
wombatman is offline   Reply With Quote
Old 2013-10-13, 20:07   #8
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

5·13·53 Posts
Default

Quote:
Originally Posted by wombatman View Post
One thing to try is restoring the relations found using the spairs.gz file like you're doing, deleting all the .cyc and such, and then rerunning using the "-nc" command. That should take of it, if I understand your error correctly. I've had to do that before when my .dat file disappeared.
Thanks! That's what I've done and it is working through the msieve steps, but I have encountered another stumbling block:
Code:
matrix needs more columns than rows; try adding 2-3% more relations
This keeps coming up even when I add more relations. This might be due to the poly. I'm suspecting this may be what VBCurtis posted about:
Quote:
Originally Posted by VBCurtis
A5 coefficients below 10000 should not be searched- msieve takes longer at very low A5 values to do the same work. Also note skew is 50M, very high for this size of number; this occasionally causes hiccups in later stages (I have not run into such a hiccup yet, but I follow Frmky's advice to use large A5, say 5-50M for this size number). Large A5 coefficients have lower skews than very small values.
I will keep adding for now, but at some point I may need to start over from scratch...
EdH is online now   Reply With Quote
Old 2013-10-14, 15:56   #9
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

5×13×53 Posts
Default

The matrix finally built properly for a solve...
EdH is online now   Reply With Quote
Old 2013-10-14, 16:00   #10
wombatman
I moo ablest echo power!
 
wombatman's Avatar
 
May 2013

5·347 Posts
Default

I have that issue sometimes as well--I've gotten to 120% of the estimated relations before the matrix builds, even when using a large interval step. Maybe somebody better versed in this can suggest a cause?
wombatman is offline   Reply With Quote
Old 2013-10-14, 20:00   #11
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

10001011101012 Posts
Default

The estimates for # of relations in the factmsieve script are not very accurate- it uses an exponential with size of number as input, while the actual situation is more like a step function with the steps located where lpbr jumps bits. Serge (Batalov) posted a patch to fix this in some thread- I'll see if I can find and link it.

Actual rels needed is roughly 21M for 28-bit projects, 40M for 29-bit projects, and (I am told) the low 80s for 30-bit projects. Some polys produce more or fewer duplicate relations, and sometimes a matrix builds with fewer-than-typical relations, so there is a fair amount of variety from project to project.

My vague grasp of the "hiccup" mentioned above is that skew alters the area sieved for each special-Q, with higher skews associated with smaller areas. Very high skews may require more special-Q to be searched, and that requirement can lead to using special-Q higher than a poly's efficient sieve range. So it's not that reaching 120% of the script's expected rels is a hiccup- it's that the last few rels might be found at a rate half (or worse?) of the sec/rel you achieved during most of the sieving. If you read through threads of large forum-team-factorizations, you'll see discussions amounting to "we've run out of good Q, now what?". High-skew polys run out of good Q more often than low-skew polys.

At single-user-size projects, we can preempt this problem by choosing the next-higher siever version for a project we're even slightly nervous about. We might choose to use 14e instead of 13e for projects a few digits lower than the script's cutoff; in fact, I edited my factmsieve code to shift the cutoff a bit lower. As Mr Womack points out, this makes factorizations in the 135 to 150 digit level more fire-and-forget at the expense of a few hours of sieving. I have not yet attempted a 30-bit project myself to know how much of this extends upward.
-Curtis

Last fiddled with by VBCurtis on 2013-10-14 at 20:02 Reason: added info in first paragraph
VBCurtis is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Poly search candidates schickel Msieve 32 2013-11-05 19:11
Resume msieve poly search job? Andi47 Msieve 1 2011-03-28 04:30
gpu poly search error bdodson Msieve 10 2010-11-09 19:46
Poly search for c157 from 4788:2422 henryzz Aliquot Sequences 59 2009-07-04 06:27
Poly search for c137 from 4788:2408 axn Aliquot Sequences 15 2009-05-28 16:50

All times are UTC. The time now is 00:32.

Wed Nov 25 00:32:22 UTC 2020 up 75 days, 21:43, 4 users, load averages: 2.70, 2.60, 2.50

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.