Tweaking polynomial search for C197

fivemack · 2011-04-28, 13:06

I have a C197 (from 7^374+1) for which I have the possibly-misguided belief that a sufficiently good polynomial will let GNFS beat SNFS. But, first catch your polynomial.

I've been running -np1 and -np2 separately, and using various choices of stage2_norm and final_norm for the second stage

Code:

	params		runtime		npoly	polybest
	3e28/3e-15	00:01:37	3	3.143e-15
	3e28/2.5e-15	00:01:53	109	3.143e-15
	3e28/2e-15	00:02:00	371	3.143e-15
	1e29/3e-15	00:04:25	34	3.544e-15
	1e29/2.5e-15	00:06:14	257	3.544e-15
	1e29/2e-15	00:06:41	779	3.544e-15

which feels as if the final_norm choice really only affects the printout whilst the stage2_norm value does change the search significantly. The good hits are coming from the same msieve.dat.m line, which is the one with smallest norm.

Making an msieve.dat.m file containing only that line and running -np2 on it with 3e29/3e-15 got a 3.629e-15 hit in 55 seconds. Going all the way to stage2_norm=1e30 gave only a 3.249e-15, in 187 seconds; are some internal buckets getting full, and can they be enlarged?

Given this, does it make sense for these very large polynomial searches to have the polynomial rejection and the term to define the depth of the stage-2 search as coupled as they are?

(it would be excellent if there could be some command-line option, say -npx stage1,stage2,final to set stage1, stage2 and final_norm explicitly - recompiling repeatedly is getting a little tiresome, and asking collaborators to rebuild the binary for my particular search is not ideal)

fivemack · 2011-05-01, 21:07

Run 2.0e6 to 2.1e6: -np1 with bound 1e30, then removed everything from msieve.dat.m with norm greater than 1.5e28 before running -np2 with bound 3e29,3e-15.

Best polynomial so far scores 5.121e-15, from the good-but-not-great (23rd-best norm out of 701)

Code:

4.28365e+27 2049840 3018808642241768528471 124442599145567278995770899931421333832

and looks as if it might manage to give relations slightly faster than the obvious SNFS quintic. Second-best is 4.813e-15 from 64th-best-norm

Code:

6.218e+27 2051280 2973521534387954300693 124425122480650663418754398212127288150

But I don't think I've processed all 701 yet, and I'm not doing them in order of norm. I expect to keep searching on one i7/920 + geforce-275 for most of May.

I obtained a Spearman rank-correlation coefficient of about 0.55 between rank-of-norm and rank-of-best-output-from-np2, though it wasn't quite with the parameters I'm using here; I can probably measure that again once the 701 are processed.

I'd appreciate a second opinion on the parameters for the SNFS: obviously it needs to be rational-side sieved, with 3 rational large primes and 2 algebraic, and I don't think I can reduce the lpbr/lpba very far, but I'm sure I've not got the factor base the optimal size. If anyone has better tools for this than repeated hour-long gnfs-lasieve4I16e jobs I would be very pleased to know.

Code:

n: 61173781879800813987062254208969082152381029438415262556799619943895079615422740343994343770534689647933527791161943080608113058309486560791550732809340767016424578028793088881479019117986214217881
c5: 1
c4: -1
c3: -4
c2: 3
c1: 3
c0: -1
skew: 0.523
Y1: 54116956037952111668959660849
Y0: -2928644930813641516032715844013695341634232321209103400802
lpbr: 33
lpba: 33
mfba: 66
mfbr: 96
rlambda: 3.6
alambda: 2.6
alim: 200000000
rlim: 200000000

Batalov · 2011-05-01, 21:23

The fact that the SNFS poly is a quintic gives GNFS a serious chance.
I'll try to have a good look tonight. (Nothing better than sims is known to me.)

P.S. How did you find that interesting skew of 0.523? Interesting!

P.P.S. The SNFS' score estimates come back as
size 2.150e-19, alpha 2.379, combined = 2.723e-15 rroots = 5
which even if (unrealistically) doubled (under the permise that all relations comes from sieving one side) hardly reaches the best current gnfs poly (and the future ones may be better still).

bdodson · 2011-05-01, 21:24

Quote:

Originally Posted by fivemack

Run 2.0e6 to 2.1e6: -np1 with bound 1e30, then removed everything from msieve.dat.m with norm greater than 1.5e28 before running -np2 with bound 3e29,3e-15.

Best polynomial so far scores 5.121e-15, from the good-but-not-great (23rd-best norm out of 701)

Code:

4.28365e+27 2049840 3018808642241768528471 124442599145567278995770899931421333832

and looks as if it might manage to give relations slightly faster than the obvious SNFS quintic. Second-best is 4.813e-15 from 64th-best-norm
...

Count me "in" on this one; RSA768 is nearly infinitely distant. GNFS197 is
where it's at for me. We'd especially like to hear about the cpu-vs-gpu
comparison I've reported on rsa768 --- maybe the gpu polys are mostly
disjoint from the cpu polys; in which case, both ought to be pushed.
But if the gpu polys are just slow versions of the cpu polys, I'd switch
back to primegrid (on an extremely low priority search, but at least not
known to be silly). -BD (end of Spring 2011 here at lehigh.edu)

fivemack · 2011-05-01, 21:36

Quote:

Originally Posted by Batalov

The fact that the SNFS poly is a quintic gives GNFS a serious chance.
I'll try to have a good look tonight. (Nothing better than sims is known to me.)

P.S. How did you find that interesting skew of 0.523? Interesting!

I regret that that 'interesting' skew is a typo: it's 49^(-1/6), left over from also trying the sextic. Unsurprisingly the sextic is a complete waste of time.

fivemack · 2011-05-01, 21:41

Quote:

Originally Posted by bdodson

Count me "in" on this one; RSA768 is nearly infinitely distant. GNFS197 is
where it's at for me.

Superb. I think I've already sent you the instructions (you have to rebuild msieve with changed bounds in gnfs/poly/poly_skew.c but otherwise it's straightforward); tell me where you're searching.

Quote:

We'd especially like to hear about the cpu-vs-gpu
comparison I've reported on rsa768 --- maybe the gpu polys are mostly
disjoint from the cpu polys; in which case, both ought to be pushed.

As you observed over on the rsa768 thread, the GPU yield is a lot lower. I've been running one-ninth of the -np1 jobs on the GPU, basically it takes no CPU time and it seemed sad to leave the GPU idle. I'm just redoing one of those regions on the CPU to see if there's any difference between quality (though the random-section-choice means I can't tell if one would be the subset of another).

R.D. Silverman · 2011-05-01, 22:23

Quote:

Originally Posted by fivemack

Best polynomial so far scores 5.121e-15, from the good-but-not-great (23rd-best norm out of 701)

Code:

4.28365e+27 2049840 3018808642241768528471 124442599145567278995770899931421333832

and looks as if it might manage to give relations slightly faster than the obvious SNFS quintic.

Quintic??? Distinctly sub-optimal. Use a sextic or even septic.

Suppose (a,b) is a typical lattice point ~ (10^6, 10^6) or (10^7, 10^7)

The norms for a quintic are ~(2 x 10^69) (rational) and ~10^30 [very unbalanced] and their product is ~~10^99

With a sextic, the norms are ~ (10^60) and ~ (10^36) [still unbalanced]
but their product is ~3 digits smaller.

With a septic, the norms are ~ (10^53) and ~(10^42) [better balanced]
and their product is about the same size as for a sextic.

For SNFS, the degree is optimal when the norms are as close to equal as
one can get them.

Batalov · 2011-05-02, 00:19

But 374 is divisible by 11...
Quintic has difficulty 287.3
Sextic/septic would have a difficulty 316.1 (which is no contender to gnfs, as Tom noted)

I'd expect a bit of mileage to be in optimizing the skew (not the apparent 1.0), together with lopsided limits (maybe 33/32? same story as with quartics, but milder)

Greg's latest quintics could be an insight; he could tell us if he played the three of them differently for a sport. One is just recently finished (2,979+), two are in post.

P.S. I do expect gnfs to win, though; a sextic gnfs, maybe!

R.D. Silverman · 2011-05-02, 00:38

Quote:

Originally Posted by Batalov

But 374 is divisible by 11...

Oops. I missed that.... Quintic it is then........

fivemack · 2011-05-02, 07:29

With all 701 run, best poly is 5.162e-15 from the second-best input norm

Code:

1.6594e+27 2084880 3093573605153423844953 124021463936855414689024192624060992858

Spearman rank correlation between np1-norm and final-norm is about 0.26 over the 10142 generated polynomials from the 701 input lines. Runtime for the -np2 was about an hour per hundred input lines.

More -np1 is running as I type; will send updates if anything exciting turns up.

Batalov · 2011-05-02, 10:30

I started a toy sextic search (with an ugly hack to the parameter section) and a few initial polys came out; not as good as yours, but not too terrible. Your gnfs poly already sieves better than the (unoptimized) snfs poly; this one, somewhat slower:
# norm 1.445517e-14 alpha -12.854662 e 2.997e-15 rroots 4
skew: 102288795.08
c0: 8210277589906100638592441543552379674802660068170240
c1: -101204230781719259953568475287579043702957336
c2: -22332786741153016672355302153676682370
c3: -95727608932660451457541811987
c4: 1493928679780884701886
c5: -4570937648122
c6: 24024
Y0: -116856806831252621415604098320271
Y1: 5767057836757051057

I'll try to find something better than this.

2011-04-28, 13:06	#1
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 7²·131 Posts	Tweaking polynomial search for C197 I have a C197 (from 7^374+1) for which I have the possibly-misguided belief that a sufficiently good polynomial will let GNFS beat SNFS. But, first catch your polynomial. I've been running -np1 and -np2 separately, and using various choices of stage2_norm and final_norm for the second stage Code: params runtime npoly polybest 3e28/3e-15 00:01:37 3 3.143e-15 3e28/2.5e-15 00:01:53 109 3.143e-15 3e28/2e-15 00:02:00 371 3.143e-15 1e29/3e-15 00:04:25 34 3.544e-15 1e29/2.5e-15 00:06:14 257 3.544e-15 1e29/2e-15 00:06:41 779 3.544e-15 which feels as if the final_norm choice really only affects the printout whilst the stage2_norm value does change the search significantly. The good hits are coming from the same msieve.dat.m line, which is the one with smallest norm. Making an msieve.dat.m file containing only that line and running -np2 on it with 3e29/3e-15 got a 3.629e-15 hit in 55 seconds. Going all the way to stage2_norm=1e30 gave only a 3.249e-15, in 187 seconds; are some internal buckets getting full, and can they be enlarged? Given this, does it make sense for these very large polynomial searches to have the polynomial rejection and the term to define the depth of the stage-2 search as coupled as they are? (it would be excellent if there could be some command-line option, say -npx stage1,stage2,final to set stage1, stage2 and final_norm explicitly - recompiling repeatedly is getting a little tiresome, and asking collaborators to rebuild the binary for my particular search is not ideal) Last fiddled with by fivemack on 2011-05-01 at 21:08

2011-05-01, 21:07	#2
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 7²·131 Posts	Run 2.0e6 to 2.1e6: -np1 with bound 1e30, then removed everything from msieve.dat.m with norm greater than 1.5e28 before running -np2 with bound 3e29,3e-15. Best polynomial so far scores 5.121e-15, from the good-but-not-great (23rd-best norm out of 701) Code: 4.28365e+27 2049840 3018808642241768528471 124442599145567278995770899931421333832 and looks as if it might manage to give relations slightly faster than the obvious SNFS quintic. Second-best is 4.813e-15 from 64th-best-norm Code: 6.218e+27 2051280 2973521534387954300693 124425122480650663418754398212127288150 But I don't think I've processed all 701 yet, and I'm not doing them in order of norm. I expect to keep searching on one i7/920 + geforce-275 for most of May. I obtained a Spearman rank-correlation coefficient of about 0.55 between rank-of-norm and rank-of-best-output-from-np2, though it wasn't quite with the parameters I'm using here; I can probably measure that again once the 701 are processed. I'd appreciate a second opinion on the parameters for the SNFS: obviously it needs to be rational-side sieved, with 3 rational large primes and 2 algebraic, and I don't think I can reduce the lpbr/lpba very far, but I'm sure I've not got the factor base the optimal size. If anyone has better tools for this than repeated hour-long gnfs-lasieve4I16e jobs I would be very pleased to know. Code: n: 61173781879800813987062254208969082152381029438415262556799619943895079615422740343994343770534689647933527791161943080608113058309486560791550732809340767016424578028793088881479019117986214217881 c5: 1 c4: -1 c3: -4 c2: 3 c1: 3 c0: -1 skew: 0.523 Y1: 54116956037952111668959660849 Y0: -2928644930813641516032715844013695341634232321209103400802 lpbr: 33 lpba: 33 mfba: 66 mfbr: 96 rlambda: 3.6 alambda: 2.6 alim: 200000000 rlim: 200000000 Last fiddled with by fivemack on 2011-05-01 at 22:09

2011-05-01, 21:23	#3
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 22405₈ Posts	The fact that the SNFS poly is a quintic gives GNFS a serious chance. I'll try to have a good look tonight. (Nothing better than sims is known to me.) P.S. How did you find that interesting skew of 0.523? Interesting! P.P.S. The SNFS' score estimates come back as size 2.150e-19, alpha 2.379, combined = 2.723e-15 rroots = 5 which even if (unrealistically) doubled (under the permise that all relations comes from sieving one side) hardly reaches the best current gnfs poly (and the future ones may be better still). Last fiddled with by Batalov on 2011-05-01 at 21:30

2011-05-02, 00:19	#8
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 9477₁₀ Posts	But 374 is divisible by 11... Quintic has difficulty 287.3 Sextic/septic would have a difficulty 316.1 (which is no contender to gnfs, as Tom noted) I'd expect a bit of mileage to be in optimizing the skew (not the apparent 1.0), together with lopsided limits (maybe 33/32? same story as with quartics, but milder) Greg's latest quintics could be an insight; he could tell us if he played the three of them differently for a sport. One is just recently finished (2,979+), two are in post. P.S. I do expect gnfs to win, though; a sextic gnfs, maybe! Last fiddled with by Batalov on 2011-05-02 at 00:26 Reason: (P.S.)

2011-05-02, 07:29	#10
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 14423₈ Posts	With all 701 run, best poly is 5.162e-15 from the second-best input norm Code: 1.6594e+27 2084880 3093573605153423844953 124021463936855414689024192624060992858 Spearman rank correlation between np1-norm and final-norm is about 0.26 over the 10142 generated polynomials from the 701 input lines. Runtime for the -np2 was about an hour per hundred input lines. More -np1 is running as I type; will send updates if anything exciting turns up.

2011-05-02, 10:30	#11
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3⁶×13 Posts	I started a toy sextic search (with an ugly hack to the parameter section) and a few initial polys came out; not as good as yours, but not too terrible. Your gnfs poly already sieves better than the (unoptimized) snfs poly; this one, somewhat slower: # norm 1.445517e-14 alpha -12.854662 e 2.997e-15 rroots 4 skew: 102288795.08 c0: 8210277589906100638592441543552379674802660068170240 c1: -101204230781719259953568475287579043702957336 c2: -22332786741153016672355302153676682370 c3: -95727608932660451457541811987 c4: 1493928679780884701886 c5: -4570937648122 c6: 24024 Y0: -116856806831252621415604098320271 Y1: 5767057836757051057 I'll try to find something better than this.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
c176 polynomial search	bdodson	Msieve	45	2010-10-29 19:39
109!+1 polynomial search	fivemack	Factoring	122	2009-02-24 07:03
5^421-1 polynomial search	fivemack	Factoring	61	2008-07-21 11:16
6^383+1 by GNFS (polynomial search; now complete)	fivemack	Factoring	20	2007-12-26 10:36
GNFS polynomial search tools	JHansen	Factoring	0	2004-11-07 12:15