mersenneforum.org Poly Search vs Sieving times
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2013-10-12, 14:24 #1 EdH     "Ed Hall" Dec 2009 Adirondack Mtns 24·3·109 Posts 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
 2013-10-12, 17:38 #2 VBCurtis     "Curtis" Feb 2005 Riverside, CA 2·32·313 Posts 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.
 2013-10-12, 18:32 #3 EdH     "Ed Hall" Dec 2009 Adirondack Mtns 24×3×109 Posts 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...
 2013-10-12, 19:44 #4 EdH     "Ed Hall" Dec 2009 Adirondack Mtns 147016 Posts 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...
 2013-10-13, 14:14 #5 EdH     "Ed Hall" Dec 2009 Adirondack Mtns 24×3×109 Posts 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...
 2013-10-13, 18:05 #6 EdH     "Ed Hall" Dec 2009 Adirondack Mtns 24×3×109 Posts 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
 2013-10-13, 19:45 #7 wombatman I moo ablest echo power!     May 2013 22·463 Posts 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.
2013-10-13, 20:07   #8
EdH

"Ed Hall"
Dec 2009
Adirondack Mtns

24·3·109 Posts

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

 2013-10-14, 15:56 #9 EdH     "Ed Hall" Dec 2009 Adirondack Mtns 147016 Posts The matrix finally built properly for a solve...
 2013-10-14, 16:00 #10 wombatman I moo ablest echo power!     May 2013 22·463 Posts 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?
 2013-10-14, 20:00 #11 VBCurtis     "Curtis" Feb 2005 Riverside, CA 2·32·313 Posts 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

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post schickel Msieve 32 2013-11-05 19:11 Andi47 Msieve 1 2011-03-28 04:30 bdodson Msieve 10 2010-11-09 19:46 henryzz Aliquot Sequences 59 2009-07-04 06:27 axn Aliquot Sequences 15 2009-05-28 16:50

All times are UTC. The time now is 20:22.

Wed Feb 1 20:22:04 UTC 2023 up 167 days, 17:50, 0 users, load averages: 0.74, 1.00, 0.98

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

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔