mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > XYYXF Project

Reply
 
Thread Tools
Old 2016-04-02, 18:56   #34
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

144668 Posts
Default

10400 stage-1 curves run on C190_149_91, 84% of them taken to stage 2, found a P55 but it turns out that it had already been submitted
fivemack is offline   Reply With Quote
Old 2016-04-03, 23:56   #35
XYYXF
 
XYYXF's Avatar
 
Jan 2005
Minsk, Belarus

24·52 Posts
Default

C177_148_94 was suggested as GNFS, but its SNFS difficulty is not too high:

Difficulty 248: 4879681*(4724)6 + 29986576*(26*3715)6 = 58008018918812545143463727211454278525294078099759247887923759309261425 * C177

Difficulty 254: 1369*(4725)6 + 35344*(26*3716)6 = 175423268180778312831796670198430324228190852757122036482075886926082969832425 * C177
XYYXF is offline   Reply With Quote
Old 2016-04-07, 11:00   #36
swellman
 
swellman's Avatar
 
Jun 2012

23×13×37 Posts
Default

C177_148_94 is on the list of possible GNFS candidates because the best SNFS poly I could find using Yafu would take an estimated 247M core-seconds to sieve versus ~85M core-seconds using GNFS. If my estimates are off then perhaps GNFS is not the best path forward.

Can anybody provide a quick and dirty GNFS poly we can test with?

Using an ECM rule of thumb of 0.31*GNFS gives ~t55, which this number has already survived. The 5000 curves @B1=26e7 listed in this thread may be unnecessary though certainly prudent (for peace of mind if nothing else).

Best SNFS poly I found follows:

Code:
n: 509324937687618809222445320276337252810119679947032399409215533120195327608346172383916906170272967333837017570484086026229163006167878198943819573285050609840596958297287281873
# 148^94+94^148, difficulty: 248.37, anorm: 3.92e+033, rnorm: -1.41e+055
# scaled difficulty: 251.97, suggest sieving rational side
# size = 1.438e-017, alpha = 0.000, combined = 7.015e-014, rroots = 1
type: snfs
size: 248
skew: 20.7443
c5: 1
c0: 3841451
Y1: -3096263264537031876137686856267255616967297523567
Y0: 159982589693655584703558945119488
rlim: 57000000
alim: 57000000
lpbr: 31
lpba: 31
mfbr: 62
mfba: 62
rlambda: 2.7
alambda: 2.7
swellman is online now   Reply With Quote
Old 2016-04-07, 20:40   #37
debrouxl
 
debrouxl's Avatar
 
Sep 2009

3D316 Posts
Default

The sextic SNFS polynomial produced by snfspoly has hideous coefficients, yeah... but a quintic of that SNFS difficulty is no piece of cake either.
debrouxl is offline   Reply With Quote
Old 2016-04-07, 20:54   #38
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

22×3×311 Posts
Default

Quote:
Originally Posted by swellman View Post

Code:
n: 509324937687618809222445320276337252810119679947032399409215533120195327608346172383916906170272967333837017570484086026229163006167878198943819573285050609840596958297287281873
# 148^94+94^148, difficulty: 248.37, anorm: 3.92e+033, rnorm: -1.41e+055
# scaled difficulty: 251.97, suggest sieving rational side
# size = 1.438e-017, alpha = 0.000, combined = 7.015e-014, rroots = 1
type: snfs
size: 248
skew: 20.7443
c5: 1
c0: 3841451
Y1: -3096263264537031876137686856267255616967297523567
Y0: 159982589693655584703558945119488
rlim: 57000000
alim: 57000000
lpbr: 31
lpba: 31
mfbr: 62
mfba: 62
rlambda: 2.7
alambda: 2.7
Was this the winner of the automated test sieving in yafu? For numbers of this size it is probably worthwhile to do more test sieving, especially if the sextics were close performance-wise. Chunks of 2 to 5k special-q in several locations throughout the estimated sieve region.
bsquared is offline   Reply With Quote
Old 2016-04-07, 21:56   #39
swellman
 
swellman's Avatar
 
Jun 2012

1111000010002 Posts
Default

Quote:
Originally Posted by bsquared View Post
Was this the winner of the automated test sieving in yafu? For numbers of this size it is probably worthwhile to do more test sieving, especially if the sextics were close performance-wise. Chunks of 2 to 5k special-q in several locations throughout the estimated sieve region.
It is the optimal Yafu answer. I've done several hundred of these, and the decision on whether a Yafu generated poly is optimal is usually an obvious yes/no or "it doesn't matter", meaning two polys are so close in performance that even if the ultimate winner turns out to be slightly suboptimal it's so close to the optimal solution that the total sieving time difference is near negligible. Just my opinion of course.

I have found a lot of scatter when plotting sieving times vs SNFS difficulty - hardly surprising - and this particular case is especially hideous as Lionel notes. It's just a case where the ugly SNFS poly can likely be beat by a decent GNFS poly.

That said, of course we can use SNFS to factor this number. My list is hardly authoritative - it's just a set of candidates that are likely best solved via GNFS.
swellman is online now   Reply With Quote
Old 2016-04-07, 22:02   #40
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

1110100101002 Posts
Default

Quote:
Originally Posted by swellman View Post
It is the optimal Yafu answer. I've done several hundred of these, and the decision on whether a Yafu generated poly is optimal is usually an obvious yes/no or "it doesn't matter", meaning two polys are so close in performance that even if the ultimate winner turns out to be slightly suboptimal it's so close to the optimal solution that the total sieving time difference is near negligible. Just my opinion of course.
You've used it a lot more than I have . Just pointing out that if two polynomials are "nearly the same", then the differences are magnified when applied to very large sieving tasks. You're right that the better question in this case is probably SNFS vs. GNFS.
bsquared is offline   Reply With Quote
Old 2016-04-07, 22:24   #41
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

2·2,819 Posts
Default

I'll let a GPU run a few hours to get an "in the vicinity" poly for your comparison task this evening. We can estimate the improvement for a full poly-search using the estimated-good poly score that msieve produces in case the test is inconclusive.
VBCurtis is online now   Reply With Quote
Old 2016-04-07, 22:27   #42
swellman
 
swellman's Avatar
 
Jun 2012

23·13·37 Posts
Default

Agreed. Before embarking on a big factoring job, one should definitely perform extensive test sieving. 1% difference in performance is negligible when it's a 1000 hour job, not so much when it's 200000 hours.

So back to an earlier question - does anyone have a quick and dirty GNFS poly so we can decide a path forward?

ETA: thanks VBCurtis!

Last fiddled with by swellman on 2016-04-07 at 22:28
swellman is online now   Reply With Quote
Old 2016-04-08, 03:03   #43
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

2×2,819 Posts
Default

2 GPU-hr produced this:
Code:
N 509324937687618809222445320276337252810119679947032399409215533120195327608346172383916906170272967333837017570484086026229163006167878198943819573285050609840596958297287281873
SKEW 44744195.26
R0 -15372279160491459270723477022022637
R1 42075573946251179
A0 -28036751366398061170413492158368626575647616
A1 2446095126548667802453043510317136360
A2 132445682988042341783594025606
A3 -4958312126359633450937
A4 102677914180448
A5 593340
skew 44744195.26, size 2.117e-17, alpha -7.554, combined = 1.104e-13 rroots = 3
Msieve says target score is 1.22e-13, but this poly exceeds the previous best found for a c178 on the forum, so it's at least decent. I'd guess 7-10% improvement for a full search.
VBCurtis is online now   Reply With Quote
Old 2016-04-08, 16:33   #44
swellman
 
swellman's Avatar
 
Jun 2012

23·13·37 Posts
Default

I ran some test sieving using a Win64 box with an i5-3340M processor. Results follow, but GNFS is the clear winner.

poly siever lpbr/a a/r ETA (wks) yield a/rlim (M) spec_Q0 (M) spec_Q range
gnfs 15e 31 a 55 1.70 120 40 4000
gnfs 14e 31 a 61 0.78 120 40 4000
gnfs 15e 31 a 56 1.58 150 50 4000
gnfs 14e 31 a 65 0.74 150 50 4000
snfs 15e 31 r 108 1.32 57 28.5 4000
snfs 14e 31 r 83 0.58 57 28.5 4000
snfs 14e 31 r 82 0.58 57 28.5 10000
gnfs 15e 31 a 49 1.68 150 50 10000

Do we need to run more ECM (5000 curves @B1=26e7) prior to starting GNFS?
swellman is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Ready GNFS targets XYYXF XYYXF Project 87 2022-04-27 10:59
SNFS targets which need more ECM XYYXF XYYXF Project 57 2017-07-04 19:15
Ready SNFS targets XYYXF XYYXF Project 25 2016-11-20 21:35
3,697+ (GNFS 220.9) pinhodecarlos NFS@Home 0 2014-12-24 19:13
3,766+ (GNFS 215.5) pinhodecarlos NFS@Home 34 2014-04-01 21:27

All times are UTC. The time now is 18:37.


Sat Feb 4 18:37:18 UTC 2023 up 170 days, 16:05, 1 user, load averages: 0.94, 1.04, 0.99

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.

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