GNFS targets which need more ECM - Page 21

Max0526 · 2017-02-26, 21:06

Nothing record breaking, but works as baseline.
Trying to beat 1.221e-14.
Found by CADO-NFS.

Code:

Y0: -104485128099637817320522910179858680682
Y1: 13308902415133253604212869
c0: 70739647258963288259007482794959495340863328665
c1: 416725117265632260907547277548156503579
c2: -130383975006441836568037405346307
c3: -57114303389686469554939
c4: 3507014313990642
c5: 191880
skew: 200374261.68756
# lognorm 62.53, E 54.55, alpha -7.98 (proj -2.17), 5 real roots
# MurphyE=8.60374023e-15

Max0526 · 2017-02-27, 11:20

Code:

Y0: -55295288169917793017590362246300749206
Y1: 400173740814420255252859
c0: -70056747158173974126640007008240300290602942550
c1: 606608021191877905105484530177983756055
c2: 72336626451727119188335009838826
c3: -135362582587816781337259
c4: -8780488635135672
c5: 2851200
skew: 104826005.22192
# lognorm 62.33, E 54.40, alpha -7.93 (proj -2.21), 5 real roots
# MurphyE = 9.21785886e-15

swellman · 2017-03-18, 12:03

I've run a good bit of test sieving on C194_144_91 and have concluded that the best approach is SNFS. The top two SNFS polys I could find are nearly identical in e-score and sieving performance when run on the 15e siever (Yafu slightly prefers the second poly):

Code:

n: 61411172602513602114086542609422772595687132712317112661975765093048029536174886070309463055714389706621125069974641983349539264180609971474976394461078414389892605396353638153629876745768119873
# 144^91+91^144, difficulty: 282.70, anorm: 1.20e+037, rnorm: 9.72e+052
# scaled difficulty: 285.36, suggest sieving rational side
# size = 7.636e-014, alpha = 0.552, combined = 1.622e-014, rroots = 0
type: snfs
size: 282
skew: 1.1447
c6: 4
c0: 9
Y1: -474752627599539612657900582862848
Y0: 103990439982641976602358193567219214216215193761
rlim: 250000000
alim: 250000000
lpbr: 32
lpba: 32
mfbr: 64
mfba: 64
rlambda: 2.8
alambda: 2.8

yield = 1.06 @q=100M, 0.85 @q=300M
ETA (weeks) = 280 @q=100M, 381 @q=300M

and

Code:

n: 61411172602513602114086542609422772595687132712317112661975765093048029536174886070309463055714389706621125069974641983349539264180609971474976394461078414389892605396353638153629876745768119873
# 144^91+91^144, difficulty: 282.10, anorm: 2.40e+037, rnorm: 6.87e+052
# scaled difficulty: 284.68, suggest sieving rational side
# size = 7.893e-014, alpha = 0.090, combined = 1.673e-014, rroots = 0
type: snfs
size: 282
skew: 2.2894
c6: 1
c0: 144
Y1: -237376313799769806328950291431424
Y0: 103990439982641976602358193567219214216215193761
rlim: 250000000
alim: 250000000
lpbr: 32
lpba: 32
mfbr: 64
mfba: 64
rlambda: 2.8
alambda: 2.8

yield = 1.08 @q=100M, 0.84 @q=300M
ETA (wks) = 287 @q=100M, 381 @q=300M

(The ETA is a gross estimate produced by Yafu and was run on an old computer, so the absolute values are likely much higher than one might see on a modern machine but the relative values are significant.)

Both of these polys handily beat the best target score of 1.221e-14 for a GNFS 194 and subsequent sieving showed that neither GNFS poly in this thread was close in yield or speed. I even experimented with 3LPs (with disappointing results), despite the unlikelihood that a C194 which had survived so much ECM could still have three undetected factors. SNFS seems the clear path forward, in my opinion of course.

Kudos to Max0526 for his search efforts. FWIW, I did try my hand at GPU poly searching but could not beat Max's scores. It would seem that several GPU-months of searching would likely still come up short.

fivemack · 2017-03-18, 20:23

Thanks for the comprehensive work here; I have queued up the best SNFS polynomial on NFS@home 15e.

"even experimented with 3LPs (with disappointing results), despite the unlikelihood that a C194 which had survived so much ECM could still have three undetected factors" suggests a degree of confusion - the number of large primes used in factorising the intermediate numbers in the sieving has nothing to do with the number of factors of the number being worked on.

swellman · 2017-03-18, 21:47

Quote:

Originally Posted by fivemack

Thanks for the comprehensive work here; I have queued up the best SNFS polynomial on NFS@home 15e.

Thank you for enqueueing it.

Quote:

"even experimented with 3LPs (with disappointing results), despite the unlikelihood that a C194 which had survived so much ECM could still have three undetected factors" suggests a degree of confusion - the number of large primes used in factorising the intermediate numbers in the sieving has nothing to do with the number of factors of the number being worked on.

You're being kind - it suggests a large degree of confusion.

My only defense is that the posting was made early in the morning after St Patrick's day. The point of my post was the 3LP technique did not improve sieving. I did try to go back later and edit out the babble but too much time had elapsed.

fivemack · 2017-03-20, 07:11

Can we have a status report on C195_130_121 ?

I have queued up 24 blocks of 1280 stage-1 curves on C196_135_124 on my GPU, with luck that will be done by Easter

swellman · 2017-03-20, 16:13

Quote:

Originally Posted by fivemack

Can we have a status report on C195_130_121 ?

I have queued up 24 blocks of 1280 stage-1 curves on C196_135_124 on my GPU, with luck that will be done by Easter

Progress is slow on my CPU, only a few thousand curves to date. However I am slowly pointing more machines at the problem as they complete other work. My plan was to use a GPU based approach but the performance of my old video card has been very disappointing. So I'll keep grinding away with CPUs. But it won't finish before early May at the earliest.

swellman · 2017-03-21, 21:19

I've run some analysis on C195_148_83. GNFS seems to be the best path forward.

Found two best SNFS polys, I test sieved both on 15e as a 33-bit job. The first poly seems to be the best of the two candidates by a narrow margin.

Code:

n: 381561850643132192208674758610411932490718230709839957579865900912682122578450712971586027322622023987809483202750035529814471437539511315715591324656223579939763941274703578342055376885237948959
# 148^83+83^148, difficulty: 289.43, anorm: 4.04e+039, rnorm: 4.87e+053
# scaled difficulty: 291.78, suggest sieving rational side
# size = 7.557e-015, alpha = 0.000, combined = 3.081e-015, rroots = 0
type: snfs
size: 289
skew: 3.7933
c6: 37
c0: 110224
Y1: -1209578391745185513325400686592
Y0: 948314321612795910252258014082399778603283811443
rlim: 500000000
alim: 500000000
lpbr: 33
lpba: 33
mfbr: 66
mfba: 66
rlambda: 3.0
alambda: 3.0

yield = 0.60 @q=250M, 0.52 @q=500M
ETA (weeks) = 1727 @q=250M, 2448 @ q=500M

Code:

n: 381561850643132192208674758610411932490718230709839957579865900912682122578450712971586027322622023987809483202750035529814471437539511315715591324656223579939763941274703578342055376885237948959
# 148^83+83^148, difficulty: 290.03, anorm: 2.02e+039, rnorm: 6.89e+053
# scaled difficulty: 292.45, suggest sieving rational side
# size = 7.312e-015, alpha = 1.679, combined = 2.990e-015, rroots = 0
type: snfs
size: 290
skew: 1.8966
c6: 148
c0: 6889
Y1: -2419156783490371026650801373184
Y0: 948314321612795910252258014082399778603283811443
rlim: 500000000
alim: 500000000
lpbr: 33
lpba: 33
mfbr: 66
mfba: 66
rlambda: 3.0
alambda: 3.0

yield = 0.61 @q=250M, 0.51@500M
ETA (weeks) = 1706 @q=250M, 2491 @q=500M

where ETA is a estimate produced by Yafu and a decent proxy for relative speed comparisons.

These results show that 15e probably is not up the task of SNFS for this composite. Please note that I did not test sieve on 16e.

The biggest indicator of SNFS vs GNFS is the e-score. The best value for the above polys is 3.081e-015. Consulting the Best msieve poly scores thread, we find a G194 had an e-score 1.221e-14 and a G196 had a score of 8.164e-15. These values bound the likely best e-score for a GNFS 195, say ~9e-15.

Even a half-hearted GNFS poly search should give superior sieving results when compared to the SNFS polys above. Obviously poly searching and test sieving are needed to confirm this conclusion.

Max0526 · 2017-03-25, 01:50

@swellman
I will beat up this number with a CADO stick for 48 hours and let you know at the end of the weekend. Sieving is your part of the contract. Promise to do my best.

swellman · 2017-03-25, 02:19

Quote:

Originally Posted by Max0526

@swellman
I will beat up this number with a CADO stick for 48 hours and let you know at the end of the weekend. Sieving is your part of the contract. Promise to do my best.

Sounds great Max. I'll run some test sieving once you nail down the poly.

Max0526 · 2017-03-25, 15:08

@swellman
Progress so far. You may start sieving. :)
CADO's pick:

Code:

Y0: -129441581526393021674488647128289599365
Y1: 226800817851771043265593
c0: -21562247984710874798860790557932834375312174780000
c1: -448200104391597687882733006686145914058334
c2: -838480617100535022887408610242335
c3: 3146145212611958758038469
c4: 909982787100690
c5: 105000
skew: 1115116548.370
# lognorm 64.36, E 55.63, alpha -8.73 (proj -2.15), 3 real roots
# MurphyE=7.29e-15

And c5/Y1 pair is confirmed by Msieve:

Code:

R0: -129441600375944847025073263786639919572
R1: 226800817851771043265593
A0: 143003988524256393842305073839144984896421906479402
A1: -658874441221299197228291298894867804311189
A2: -1585803176300574088327231149082132
A3: 2850881094798893222235229
A4: 866349722625690
A5: 105000
skew 1270185267.11, size 2.562e-019, alpha -8.878, combined = 7.290e-015 rroots = 3

Alpha is different though, I believe they could sieve very differently just because of that.
Hope that will pass for "a half-hearted GNFS poly".
CADO run continues till Monday morning.

2017-03-18, 12:03	#223
swellman Jun 2012 2²·13·59 Posts	C194_144_91 I've run a good bit of test sieving on C194_144_91 and have concluded that the best approach is SNFS. The top two SNFS polys I could find are nearly identical in e-score and sieving performance when run on the 15e siever (Yafu slightly prefers the second poly): Code: n: 61411172602513602114086542609422772595687132712317112661975765093048029536174886070309463055714389706621125069974641983349539264180609971474976394461078414389892605396353638153629876745768119873 # 144^91+91^144, difficulty: 282.70, anorm: 1.20e+037, rnorm: 9.72e+052 # scaled difficulty: 285.36, suggest sieving rational side # size = 7.636e-014, alpha = 0.552, combined = 1.622e-014, rroots = 0 type: snfs size: 282 skew: 1.1447 c6: 4 c0: 9 Y1: -474752627599539612657900582862848 Y0: 103990439982641976602358193567219214216215193761 rlim: 250000000 alim: 250000000 lpbr: 32 lpba: 32 mfbr: 64 mfba: 64 rlambda: 2.8 alambda: 2.8 yield = 1.06 @q=100M, 0.85 @q=300M ETA (weeks) = 280 @q=100M, 381 @q=300M and Code: n: 61411172602513602114086542609422772595687132712317112661975765093048029536174886070309463055714389706621125069974641983349539264180609971474976394461078414389892605396353638153629876745768119873 # 144^91+91^144, difficulty: 282.10, anorm: 2.40e+037, rnorm: 6.87e+052 # scaled difficulty: 284.68, suggest sieving rational side # size = 7.893e-014, alpha = 0.090, combined = 1.673e-014, rroots = 0 type: snfs size: 282 skew: 2.2894 c6: 1 c0: 144 Y1: -237376313799769806328950291431424 Y0: 103990439982641976602358193567219214216215193761 rlim: 250000000 alim: 250000000 lpbr: 32 lpba: 32 mfbr: 64 mfba: 64 rlambda: 2.8 alambda: 2.8 yield = 1.08 @q=100M, 0.84 @q=300M ETA (wks) = 287 @q=100M, 381 @q=300M (The ETA is a gross estimate produced by Yafu and was run on an old computer, so the absolute values are likely much higher than one might see on a modern machine but the relative values are significant.) Both of these polys handily beat the best target score of 1.221e-14 for a GNFS 194 and subsequent sieving showed that neither GNFS poly in this thread was close in yield or speed. I even experimented with 3LPs (with disappointing results), despite the unlikelihood that a C194 which had survived so much ECM could still have three undetected factors. SNFS seems the clear path forward, in my opinion of course. Kudos to Max0526 for his search efforts. FWIW, I did try my hand at GPU poly searching but could not beat Max's scores. It would seem that several GPU-months of searching would likely still come up short.

2017-03-20, 07:11	#226
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 1913₁₆ Posts	Can we have a status report on C195_130_121 ? I have queued up 24 blocks of 1280 stage-1 curves on C196_135_124 on my GPU, with luck that will be done by Easter Last fiddled with by fivemack on 2017-03-20 at 07:11

2017-03-25, 01:50	#229
Max0526 "Max" Jun 2016 Toronto 19·47 Posts	C195_148_83 gnfs poly search @swellman I will beat up this number with a CADO stick for 48 hours and let you know at the end of the weekend. Sieving is your part of the contract. Promise to do my best.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Ready GNFS targets	XYYXF	XYYXF Project	86	2020-03-07 16:23
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

2017-03-18, 20:23	#224
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 6419₁₀ Posts	Thanks for the comprehensive work here; I have queued up the best SNFS polynomial on NFS@home 15e. "even experimented with 3LPs (with disappointing results), despite the unlikelihood that a C194 which had survived so much ECM could still have three undetected factors" suggests a degree of confusion - the number of large primes used in factorising the intermediate numbers in the sieving has nothing to do with the number of factors of the number being worked on.