Choosing the best polynomial - Page 6

Batalov · 2013-06-23, 00:45

That's not to say that yours is not a decent poly.

We just need better still. (mine was about the same quality as yours, Curtis' is better, but so far, Greg's 5th degree poly appears to be the best - by trial sieving)

Just need to get lucky and break through to 7 or 8e-16.

wombatman · 2013-06-23, 04:27

Sounds good. I'm running the selection on the higher level (coefficients > 3,000,000) right now, so hopefully it'll produce a higher quality one.

VBCurtis · 2013-06-23, 04:52

I think I've had 3 polys at 6.17 to 6.23, but no true breakthrough. I have a few dozen candidates with stage 2 norms under 1e26, and playing with "stage2_norm=nnn" during the npr step does produce different lists of polys- some with better E, some worse.

Unless Greg tells me otherwise, I plan to run this task through Monday, and report my best few polys in hopes one of them sieves better than Greg's.
-Curtis

frmky · 2013-06-23, 05:56

That's fine. Sieving should start Wednesday evening.

Gimarel · 2013-06-23, 07:30

Quote:

Originally Posted by frmky

Sieving will start in just over 1 week from now. Here's the poly to beat:

Code:

# norm 5.079440e-21 alpha -8.178263 e 5.467e-16 rroots 3
skew: 136255886.66
c0: -210094660617235158281167281704470116399745308858195
c1: -5842228122167264862994127665572361751647881
c2: 78251666050988046826383875909123732
c3: 722037651605897444552776163
c4: -3262149587172057175
c5: 10092433680
Y0: -24382392754967924964120573553565948210138
Y1: 559803788355463651

Here's a better degree 5 poly:

Code:

# norm 6.901456e-21 alpha -8.730724 e 6.698e-16 rroots 5
skew: 467678179.33
c0: -3284279535568729396126163309993052897424378270506000
c1: 54667536234204939669253229335771621161861128
c2: 64568605293429371615091462318228199
c3: -665377540748204239459284372
c4: -417085435356256116
c5: 1004683680
Y0: -38678500954256917675860008667250087585457
Y1: 202753882042232221123

The score is still 6.124e-16 with skew 136255886.66.

xilman · 2013-06-23, 10:34

My present work is factoring C21x integers by SNFS. This is close to the quintic/sextic boundary. A case in point is N= GC(6,269) which has just started. There are four obvious polynomials, two for N and two for 6N (note that 269+1 is divisible by both 6 and 5).

Generating the polynomials is easy in this case. What is harder is telling which is the best. Trial sieving indicates that the quintics are better than the sextics and 6N is very slightly easier than N.

Question: how to persuade msieve to report the Murphy E value for an SNFS polynomial? It should be straightforward but I haven't yet worked it out. Reporting the skew would also be nice but that is easily done by hand.

Paul

jasonp · 2013-06-23, 14:53

I usually just make a .fb file and then ask for polynomial selection; that will termiate immediately with the polynomial that you specified, and in the meantime the E-value is reported.

The skew is never calculated to maximize the E-value, it will only take the skew you give it.

chris2be8 · 2013-06-23, 16:33

Quote:

Originally Posted by Batalov

Good news! RSA-210 is not squareful.

Well, it's old news, but relevant to RSA-210 factoring ...or not. ;-)

I've read the paper but it does not sound useful for factoring. If you've checked the number in not an exact power then a squareful number would have to be of form a^2.b^3 or similar. And it's very unlikely a target number would have that form (except a challenge number set by someone might be built so this algorithm will work, but nothing else will).

A more interesting question is that if you ran their algorithm against a number of form a^2.b would it always just say the number is not squareful or would it sometimes find a^2? That could be useful.

Chris

xilman · 2013-06-23, 17:08

Quote:

Originally Posted by jasonp

I usually just make a .fb file and then ask for polynomial selection; that will termiate immediately with the polynomial that you specified, and in the meantime the E-value is reported.

Thanks. I knew it had to be straightforward because the square root phase reports the E-value.

Paul

Batalov · 2013-06-23, 20:39

I've used line sieve mode to get the parameters reported (and would kill shortly), but asking for a poly selection is an even better idea!

Interestingly, older versions of msieve (<=1.51) report ~7.5e-16 e value. Was the calculation implementation changed? Is it more comparable to CADO's implementation? /just curious/

Batalov · 2013-06-23, 20:46

"20% of sieving saved is 20% sieving urned." ;-)

2013-06-23, 10:34	#61
xilman Bamboozled! "𒉺𒌌𒇷𒆷𒀭" May 2003 Down not across 10,753 Posts	Choosing best SNFS poly file My present work is factoring C21x integers by SNFS. This is close to the quintic/sextic boundary. A case in point is N= GC(6,269) which has just started. There are four obvious polynomials, two for N and two for 6N (note that 269+1 is divisible by both 6 and 5). Generating the polynomials is easy in this case. What is harder is telling which is the best. Trial sieving indicates that the quintics are better than the sextics and 6N is very slightly easier than N. Question: how to persuade msieve to report the Murphy E value for an SNFS polynomial? It should be straightforward but I haven't yet worked it out. Reporting the skew would also be nice but that is easily done by hand. Paul

2013-06-23, 14:53	#62
jasonp Tribal Bullet Oct 2004 3,541 Posts	I usually just make a .fb file and then ask for polynomial selection; that will termiate immediately with the polynomial that you specified, and in the meantime the E-value is reported. The skew is never calculated to maximize the E-value, it will only take the skew you give it. Last fiddled with by jasonp on 2013-06-23 at 14:57

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Polynomial Discriminant is n^k for an n-1 degree polynomial	carpetpool	Miscellaneous Math	14	2017-02-18 19:46
Help choosing motherboard please.	Flatlander	GPU Computing	4	2011-01-26 08:15
Choosing the best CPU for sieving	siew	Factoring	14	2010-02-27 10:07
MPQS: choosing a good polynomial	ThiloHarich	Factoring	4	2006-09-05 07:51
Choosing amount of memory	azhad	Software	2	2004-10-16 16:41

2013-06-23, 00:45	#56
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 10010100000101₂ Posts	That's not to say that yours is not a decent poly. We just need better still. (mine was about the same quality as yours, Curtis' is better, but so far, Greg's 5th degree poly appears to be the best - by trial sieving) Just need to get lucky and break through to 7 or 8e-16.

2013-06-23, 04:27	#57
wombatman I moo ablest echo power! May 2013 3351₈ Posts	Sounds good. I'm running the selection on the higher level (coefficients > 3,000,000) right now, so hopefully it'll produce a higher quality one.

2013-06-23, 04:52	#58
VBCurtis "Curtis" Feb 2005 Riverside, CA 4,861 Posts	I think I've had 3 polys at 6.17 to 6.23, but no true breakthrough. I have a few dozen candidates with stage 2 norms under 1e26, and playing with "stage2_norm=nnn" during the npr step does produce different lists of polys- some with better E, some worse. Unless Greg tells me otherwise, I plan to run this task through Monday, and report my best few polys in hopes one of them sieves better than Greg's. -Curtis

2013-06-23, 05:56	#59
frmky Jul 2003 So Cal 4072₈ Posts	That's fine. Sieving should start Wednesday evening.

2013-06-23, 20:39	#65
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3⁶·13 Posts	I've used line sieve mode to get the parameters reported (and would kill shortly), but asking for a poly selection is an even better idea! Interestingly, older versions of msieve (<=1.51) report ~7.5e-16 e value. Was the calculation implementation changed? Is it more comparable to CADO's implementation? /just curious/

2013-06-23, 20:46	#66
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3⁶×13 Posts	"20% of sieving saved is 20% sieving urned." ;-)