GNFS targets which need more ECM

[fivemack]

Nearly finished the ECM effort on C196_135_124 (30720 curves run stage-1 on GPU, 2560 left to run stage-2 on CPU). Have switched to polynomial selection on the GPU, let's give that two weeks and see what happens.

[swellman]

Originally Posted by fivemack

Nearly finished the ECM effort on C196_135_124 (30720 curves run stage-1 on GPU, 2560 left to run stage-2 on CPU). Have switched to polynomial selection on the GPU, let's give that two weeks and see what happens.

Below is the best SNFS poly I could find. It appears to be a 16e/33 effort. I've also included the best deg 5 SNFS poly. It is certainly inferior to the deg 6 poly but the e-score may be comparable with those of the GNFS deg 5 polys.

GNFS seems the clear choice but let's see what you get from the GPU search.

n: 4771226874718372401816440104013864668203176737532592253493283671988174637757061596298231366896680873325048456869159071364714864324343301436670519204700311140849625690800089534409817719724210684309
# 135^124+124^135, difficulty: 283.51, anorm: 1.73e+039, rnorm: -7.00e+052
# scaled difficulty: 285.78, suggest sieving rational side
# size = 1.533e-014, alpha = 0.000, combined = 5.282e-015, rroots = 0
type: snfs
size: 283
skew: 9.5207
c6: 1
c0: 744775
Y1: -22714703342386579455158090252925131190280650752
Y0: 181923115004036823095631551174640655517578125


n: 4771226874718372401816440104013864668203176737532592253493283671988174637757061596298231366896680873325048456869159071364714864324343301436670519204700311140849625690800089534409817719724210684309
# 135^124+124^135, difficulty: 283.31, anorm: 1.34e+031, rnorm: 3.14e+062
# scaled difficulty: 288.54, suggest sieving rational side
# size = 2.644e-019, alpha = 0.705, combined = 3.619e-015, rroots = 1
type: snfs
size: 283
skew: 1.1247
c5: 5
c0: 9
Y1: -60425876350537708314228454492376377880573272705078125
Y0: 332954968017607722800751971697982347541173495171723034624

C195_130_121 should be ECM'd by late April. Many thanks to Wombatman for his ECM contributions!

[axn]

Originally Posted by swellman

Below is the best SNFS poly I could find. It appears to be a 16e/33 effort. I've also included the best deg 5 SNFS poly. It is certainly inferior to the deg 6 poly but the e-score may be comparable with those of the GNFS deg 5 polys.

Did you test sieve the SNFS polys to see which is better out of the two? In theory, an SNFS-284 should be firmly in degree-5 territory. It would be touch and go whether the deg-5 or GNFS on C196 would be faster.

[swellman]

Originally Posted by axn

Did you test sieve the SNFS polys to see which is better out of the two? In theory, an SNFS-284 should be firmly in degree-5 territory. It would be touch and go whether the deg-5 or GNFS on C196 would be faster.

SNFS-284 firmly a deg 5? Not in my experience. But to answer your question, no I did not test sieve the quintic though it was test sieved by YAFU during the selection process. So YAFU thought the sextic was the better choice, but it really needs to be confirmed by human intervention as well as compared against the final GNFS poly.

[VBCurtis]

Originally Posted by axn

Did you test sieve the SNFS polys to see which is better out of the two? In theory, an SNFS-284 should be firmly in degree-5 territory. It would be touch and go whether the deg-5 or GNFS on C196 would be faster.

The transition from deg 5 to deg 6 happens around 210 digits, for GNFS or SNFS. 284 is closer to deg 7 than deg 5!

[axn]

Originally Posted by swellman

SNFS-284 firmly a deg 5? Not in my experience. But to answer your question, no I did not test sieve the quintic though it was test sieved by YAFU during the selection process. So YAFU thought the sextic was the better choice, but it really needs to be confirmed by human intervention as well as compared against the final GNFS poly.

Ok. So probably "firmly" is stretching the case, but I would still expect deg-5 to be (marginally) better than deg-6 at that size. Note that the optimal sieve parameters would be completely different between deg-5 and deg-6 -- not sure if yafu accounts for this.

Originally Posted by VBCurtis

The transition from deg 5 to deg 6 happens around 210 digits, for GNFS or SNFS. 284 is closer to deg 7 than deg 5!

Huh? SNFS 210 would be like GNFS-145 ish, so the degree should be similar, isn't it?

[swellman]

Originally Posted by axn

Ok. So probably "firmly" is stretching the case, but I would still expect deg-5 to be (marginally) better than deg-6 at that size. Note that the optimal sieve parameters would be completely different between deg-5 and deg-6 -- not sure if yafu accounts for this.

I don't recall if YAFU accounts for the degree of the poly in parameter selection, but it does self adjust things like lpb and siever # based on the results of the test sieving. And it does get it wrong occasionally, e.g. settling on a local minima for sieving time instead of moving to a true minimum. YAFU is just a tool like any other, not a fire and forget solution. Definitely takes human oversight.

Your comment about sieve parameters being completely different between deg-5 and deg-6 intrigues me. My methods do not consider the degree of the polynomial but much of what I do personally to prep for sieving is based on what I've read on the forum and what has worked for me in the past, not what is the theoretically best practice. Always willing to learn more. A very abbreviated version of my method:

- goal is to maximize yield (in range 1.0-3.0) while minimizing sieving time
- if two input files ("job file") have equal ETAs, pick the one with highest yield
- if two files have equal yield and ETAs, use the one with lowest siever #

- generate poly (I usually work with a deg-5 and a deg-6)
- pick lpbr/a (usually 31-33)
- r/alim=2^(lpb-4) rounded down
- mfb=2*lpb
- lambda=2.7, 2.8 or 3.0 (corresponds to value of lpb)
- pick a siever # and test sieve
- adjust siever and/or lpb then retest
- eventually declare optimal results for poly
- repeat with another poly
- pick best poly and factor composite

This method is highly empirical, with no preconceived notions of degree to be used. That said, in my experience with several hundred poly builds over the last few years I do tend to shortcut a few steps. For example, siever 14e will never efficiently sieve a SNFS 275, nor is using lpb=33 necessary on a GNFS 161.

It all comes down to test sieving.

[VBCurtis]

Originally Posted by axn

Huh? SNFS 210 would be like GNFS-145 ish, so the degree should be similar, isn't it?

Have a peek at the wiki for SNFS factorization: https://en.wikipedia.org/wiki/Specia...er_field_sieve

You'll find the conjectured formula for optimal degree of poly under "choice of parameters". Plugging in 205 digits results in N = 6, and 330 results in N = 7. The formula is specifically listed there for SNFS, but I'm pretty sure it's the same for GNFS. You mention the difficulty equivalence from SNFS to GNFS, but that has nothing to do with choosing degree. 285 digits is closer to 330 than 205, which is what I was referring to; it's more than halfway up the deg-6-optimal range.

On my near-Cunningham (aka riesel) numbers, I found deg 6 to be superior around 680 bits, a bit higher than the formula indicates; I think deg 6 and 7 are about the same at 1060 bits, but I have merely toyed with test-sieving a number that big to see if I could find a case where deg 7 is better.

[axn]

Originally Posted by VBCurtis

You mention the difficulty equivalence from SNFS to GNFS, but that has nothing to do with choosing degree.

This is the part I am having trouble with. :-(

[fivemack]

Range of 10kQ, alim=rlim=268e6, siever 15e, 32-bit large primes, using the GNFS polynomial from a 1% sample of the search range

$ cat SNFS-a.aus 
total yield: 3790, q=268010003 (1.55223 sec/rel) 
$ cat SNFS-r.aus 
total yield: 4607, q=268010003 (1.43881 sec/rel) 
$ cat GNFS-6159.aus 
total yield: 6015, q=268010003 (1.21251 sec/rel) 
$ cat GNFS.23-6159.aus  <- 3 A-side large primes
total yield: 7728, q=268010003 (1.05761 sec/rel)

So it's definitely a GNFS number, and it's definitely a bit too big for 15e/32. Doing some runs at 15e/33.

[fivemack]

$ cat GNFS-6159.LP33.aus 
total yield: 11688, q=268010003 (0.53504 sec/rel)
$ cat GNFS-6159.LP33.3ALPaus 
total yield: 16589, q=268010003 (0.45467 sec/rel)

So significantly more than twice the relations per second, and rather more than twice the relations per Q when using 3 large primes. It's a plausible 15e/33 job.

Now trial-sieving with 16e