GNFS targets which need more ECM - Page 24

Max0526 · 2017-04-08, 14:18

@fivemack
Can you please teach me what parameter to change in polyselect setup to look for a poly with 3 large primes? CADO has 2 large primes by default, and I don't know if it's possible to change it to 3. But apparently you know how to indicate it for Msieve/YAFU. Any help on this matter is highly appreciated.

swellman · 2017-04-08, 16:48

Quote:

Originally Posted by Max0526

@fivemack
Can you please teach me what parameter to change in polyselect setup to look for a poly with 3 large primes? CADO has 2 large primes by default, and I don't know if it's possible to change it to 3. But apparently you know how to indicate it for Msieve/YAFU. Any help on this matter is highly appreciated.

Here are a couple of posts that you might find useful

http://www.mersenneforum.org/showpos...&postcount=952

http://www.mersenneforum.org/showpos...&postcount=978

Max0526 · 2017-04-08, 16:58

@fivemack
Thank you, that was really helpful. I see that 3LPs approach has to do with actual sieving/test-sieving and not with polyselect. No further questions from me for now then.

fivemack · 2017-04-08, 21:29

Code:

$ cat 6159-16e-LP32-2ALP.aus 
total yield: 13318, q=268010003 (1.71475 sec/rel) 
$ cat 6159-16e-LP32-3ALP.aus 
total yield: 17721, q=268010003 (1.40930 sec/rel) 
$ cat 6159-16e-LP33-2ALP.aus 
total yield: 26163, q=268010003 (0.84533 sec/rel)
$ cat 6159-16e-LP33-3ALP.aus
total yield: 38297, q=268010003 (0.66923 sec/rel)

So the yields are very much higher, but the time per relation is also so much larger that this is not worthwhile.

I don't see strikingly lower duplicate rates for 16e vs 15e for numbers this size, though I only have two GNFS 16e examples in my database and they both use asymmetric rational and algebraic sides whilst none of the 15e of similar size do that. So I suspect this is a long 15e job. I should redo the trial sieving once we have a more excellent polynomial, but I think the conclusion is clear enough that a higher E-value won't change it very much.

swellman · 2017-04-12, 11:57

After extensive test sieving, the top three polynomials of those found by Max0526 for C195_148_83 are listed below. GNFS is much faster than SNFS for this composite.

Code:

Poly 1

n: 381561850643132192208674758610411932490718230709839957579865900912682122578450712971586027322622023987809483202750035529814471437539511315715591324656223579939763941274703578342055376885237948959
# norm 3.301585e-019 alpha -7.199832 e 7.625e-015 rroots 5
skew: 287641325.17
c0: -574895525937352524602338208472098702376437680181
c1: 14429620591842064101638761292252480466163
c2: 219075169379313217664562469069106
c3: -64221985543193871734263
c4: -2660477255404425
c5: 2102400
Y0: -61881957274908314693679550419904751928
Y1: 68134761333096744986009
rlim: 500000000
alim: 500000000
lpbr: 33
lpba: 33
mfbr: 66
mfba: 66
rlambda: 3.0
alambda: 3.0



Poly 2

n: 381561850643132192208674758610411932490718230709839957579865900912682122578450712971586027322622023987809483202750035529814471437539511315715591324656223579939763941274703578342055376885237948959
Y0: -61881959937567910875303173912586097736
Y1: 68134761333096744986009
c0: -806789015722600171468824051695294504291623527909
c1: -2327587355477229624386233984702886302797
c2: 200971308188333504773533642915074
c3: 383764195165512635544137
c4: -3071278983148425
c5: 2102400
skew: 343484091.734
# lognorm 63.18, E 55.98, alpha -7.20 (proj -1.61), 5 real roots
# MurphyE=7.61e-15
rlim: 500000000
alim: 500000000
lpbr: 33
lpba: 33
mfbr: 66
mfba: 66
rlambda: 3.0
alambda: 3.0



Poly 3

n: 381561850643132192208674758610411932490718230709839957579865900912682122578450712971586027322622023987809483202750035529814471437539511315715591324656223579939763941274703578342055376885237948959
Y0: -66639466470090969807796083294200781193
Y1: 34237568437838650288907
c0: -20651639625122894646111316805227359185476502909040
c1: 218676039845425136144283051205405397193958
c2: 1734492569001794961072674562370809
c3: -1253915992353438586882365
c4: 1346104891740278
c5: 580680
skew: 1096958438.913
# lognorm 64.61, E 55.53, alpha -9.08 (proj -1.68), 3 real roots
# MurphyE=8.04e-15
rlim: 500000000
alim: 500000000
lpbr: 33
lpba: 33
mfbr: 66
mfba: 66
rlambda: 3.0
alambda: 3.0

The performance of these three on the -a side on siever 15e is summarized below, with blocks of 10,000 Q used to test sieve. (ETA is a YAFU estimate in weeks to fully sieve the number, a reasonable proxy for the speed of the poly.)

I attempted to test sieve with -a and -r on the first poly with 3LP on the rational side and then the algebraic side but got odd (and very poor) results. But I am not confident in my methodology.

Code:

Poly 1

Q        ETA     Yield
50M      921     0.74
250M     746     1.13
500M     929     1.17


Poly 2

Q        ETA     Yield
50M      915     0.75
250M     820     1.12
500M     965     1.17


Poly 3

Q        ETA     Yield
50M     1032     0.62
250M     777     1.06
500M    1048     1.07

Kudos to Max0526 for his extensive poly search, stitching together Msieve and CADO tools to provide an extensive list of quality candidates.

The highest e-score reported by Max was third best in performance which I suppose is odd but not unheard of. While I think additional and extensive poly searching could result in a higher e-score poly, Max's hit is a record for a C195 GNFS. Not sure how much better a result could be found.

fivemack · 2017-04-12, 12:35

Thank you for your work.

I would rather see yields and relations-per-second figures than YAFU's estimate, because you can integrate them up to get an estimate for required range and sieving time, whilst YAFU is making a point estimate based on yield and RPS at a particular Q value.

I have often seen lower yields for polynomials with extremely large skews, to the point that my testing script filters out skews larger than 250 million; I think this is a defect of the ggnfs sievers.

I'm trying 3LPA myself to see if I see the same effect as you.

swellman · 2017-04-12, 15:45

Quote:

Originally Posted by fivemack

Thank you for your work.

I would rather see yields and relations-per-second figures than YAFU's estimate, because you can integrate them up to get an estimate for required range and sieving time, whilst YAFU is making a point estimate based on yield and RPS at a particular Q value.

YAFU's ETA is an estimate to sieve enough relations to attempt filtering, which in this case is about 743M relations. A rel/sec for a single thread could be worked out but I understand your preference now. Simple enough to run say 1000 Q on a single thread with ggnfs to give a pure speed metric, though some of my older hardware is 3-4 times slower than today's computers. It's a useful comparative tool if nothing else.

Quote:

I have often seen lower yields for polynomials with extremely large skews, to the point that my testing script filters out skews larger than 250 million; I think this is a defect of the ggnfs sievers.

Yes I did notice some large skews, many >1e9. I have yield/ETA data for all of Max's polys if you think they could be helpful. But none of the polys seem to have low skews.

Quote:

I'm trying 3LPA myself to see if I see the same effect as you.

Thank you. Something seemed to go horribly wrong and I'm too burned out to debug it. But I will try to replicate your results if you find something useful, just to teach myself how to fish from here on out.

fivemack · 2017-04-13, 08:52

Using 15e, algebraic size, Q0=5e8, range of 1e4

Code:

$ ../gnfs-lasieve4I15e -a gnfs-22 -f 500000000 -c 10000 2> 22.t
$ ../gnfs-lasieve4I15e -a gnfs-23 -f 500000000 -c 10000 2> 23.t
$ cat 23.t
total yield: 19425, q=500010029 (0.88907 sec/rel) 
$ cat 22.t
total yield: 15576, q=500010029 (0.91419 sec/rel)

so it's only slightly faster per relation but does have a rather higher yield. I'd be inclined to use it; shall I push to 15e? It would be awfully nice if I could find another volunteer for the six-weeks-on-a-32GB-hexcore linear algebra :)

I just did

Code:

mfbr: 66
mfba: 96
rlambda: 3.0
alambda: 3.6

for the 3ALP test.

swellman · 2017-04-13, 09:04

I will be happy to run the LA for this polynomial, once it is fully sieved. Might take a while on my 32 Gb i7 but I think it will have enough horsepower. Willing to make the attempt.

fivemack · 2017-04-13, 14:37

And off it goes ... the queue's really quite long by now, and some of the jobs in it are enormous, I'd expect it to be done by September.

swellman · 2017-04-13, 15:14

Excellent. Thank you for enqueuing it.

The status of the two remaining GNFS currently under consideration:

- C195_130_121 - ECM underway by swelllman. <8000 curves remaining. Estimated completion date is 26 April.

- C196_135_124 - Analysis by Fivemack complete - it's a GNFS job. Poly search by Fivemack ongoing.

2017-04-08, 21:29	#257
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 7²×131 Posts	16e is much slower per relation Code: $ cat 6159-16e-LP32-2ALP.aus total yield: 13318, q=268010003 (1.71475 sec/rel) $ cat 6159-16e-LP32-3ALP.aus total yield: 17721, q=268010003 (1.40930 sec/rel) $ cat 6159-16e-LP33-2ALP.aus total yield: 26163, q=268010003 (0.84533 sec/rel) $ cat 6159-16e-LP33-3ALP.aus total yield: 38297, q=268010003 (0.66923 sec/rel) So the yields are very much higher, but the time per relation is also so much larger that this is not worthwhile. I don't see strikingly lower duplicate rates for 16e vs 15e for numbers this size, though I only have two GNFS 16e examples in my database and they both use asymmetric rational and algebraic sides whilst none of the 15e of similar size do that. So I suspect this is a long 15e job. I should redo the trial sieving once we have a more excellent polynomial, but I think the conclusion is clear enough that a higher E-value won't change it very much.

2017-04-13, 08:52	#261
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 14423₈ Posts	3LPA on the 7.625e-15 polynomial Using 15e, algebraic size, Q0=5e8, range of 1e4 Code: $ ../gnfs-lasieve4I15e -a gnfs-22 -f 500000000 -c 10000 2> 22.t $ ../gnfs-lasieve4I15e -a gnfs-23 -f 500000000 -c 10000 2> 23.t $ cat 23.t total yield: 19425, q=500010029 (0.88907 sec/rel) $ cat 22.t total yield: 15576, q=500010029 (0.91419 sec/rel) so it's only slightly faster per relation but does have a rather higher yield. I'd be inclined to use it; shall I push to 15e? It would be awfully nice if I could find another volunteer for the six-weeks-on-a-32GB-hexcore linear algebra :) I just did Code: mfbr: 66 mfba: 96 rlambda: 3.0 alambda: 3.6 for the 3ALP test. Last fiddled with by fivemack on 2017-04-13 at 08:54

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-04-08, 14:18	#254
Max0526 "Max" Jun 2016 Toronto 19×47 Posts	@fivemack Can you please teach me what parameter to change in polyselect setup to look for a poly with 3 large primes? CADO has 2 large primes by default, and I don't know if it's possible to change it to 3. But apparently you know how to indicate it for Msieve/YAFU. Any help on this matter is highly appreciated.

2017-04-08, 16:58	#256
Max0526 "Max" Jun 2016 Toronto 19×47 Posts	@fivemack Thank you, that was really helpful. I see that 3LPs approach has to do with actual sieving/test-sieving and not with polyselect. No further questions from me for now then.

2017-04-12, 12:35	#259
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 7²×131 Posts	Thank you for your work. I would rather see yields and relations-per-second figures than YAFU's estimate, because you can integrate them up to get an estimate for required range and sieving time, whilst YAFU is making a point estimate based on yield and RPS at a particular Q value. I have often seen lower yields for polynomials with extremely large skews, to the point that my testing script filters out skews larger than 250 million; I think this is a defect of the ggnfs sievers. I'm trying 3LPA myself to see if I see the same effect as you.

2017-04-13, 09:04	#262
swellman Jun 2012 3068₁₀ Posts	I will be happy to run the LA for this polynomial, once it is fully sieved. Might take a while on my 32 Gb i7 but I think it will have enough horsepower. Willing to make the attempt.

2017-04-13, 14:37	#263
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 7²×131 Posts	And off it goes ... the queue's really quite long by now, and some of the jobs in it are enormous, I'd expect it to be done by September.

2017-04-13, 15:14	#264
swellman Jun 2012 101111111100₂ Posts	Excellent. Thank you for enqueuing it. The status of the two remaining GNFS currently under consideration: - C195_130_121 - ECM underway by swelllman. <8000 curves remaining. Estimated completion date is 26 April. - C196_135_124 - Analysis by Fivemack complete - it's a GNFS job. Poly search by Fivemack ongoing.