Choosing the best polynomial - Page 4

VBCurtis · 2013-06-19, 18:18

Jason-
When you say "size bound", do you mean the stage 1 score or the stage 2 score? Should I set the stage 1 norm looser than 40 hits/min?

-Curtis

frmky · 2013-06-19, 19:11

What skews are you getting? I raise the leading coefficient to keep the skew under 200M or so.

VBCurtis · 2013-06-19, 20:45

I get skews in 1-3M range from coeffs in 1e6-1e7.
Edit: The very next flare has skews 15-20M, but much better scores- at least a dozen with a better E than the deg 5 target poly. I'll post the best when this npr run finishes.

jasonp · 2013-06-19, 21:04

VBCurtis: I meant the stage 2 size bound for -nps in my explanation above. It's not clear that reducing the bound in stage 1 actually buys anything, except for dramatically reducing the search space and the rate that hits are found. Whatever hits do get found are not automatically better than hits found with a looser stage 1 bound.

The new free-form interface to the poly selection seems to be working out nicely. I'll also make mods for the next release to only print out intermediate results when set for verbose output.

wombatman · 2013-06-19, 21:56

Quote:

Originally Posted by jasonp

The 'expand failed' errors occur when the stage 1 hit does not correspond to the N. Either the hit is wrong or N is incorrect (either at stage 1 time or at stage 2 time). EDIT: never mind, issue dealt with above.

Also, even for a really nice graphics card you can probably get higher throughput with just a few threads, not 10. I'd try 2 to start with.

The reason we make the size bound loose is that we don't know how much size we will be sacrificing to get a good root score. The best poly might have a great root score but comparatively mediocre size score. To prevent pruning it by accident, the bounds have to be loose. Once all the size scores are computed, it's very unlikely that you'll find a root score to the 1000th best polynomial that is so good as to unseat the other 999 polynomials in front of it.

Thanks for the heads-up on this. While we're talking about optimizing the searches, are there any tips on how to improve the sieving speed aside from simply having more hardware to work with? I don't have a good handle on how the number of relations processed per second is related to, say, the polynomial used in the factor base.

VBCurtis · 2013-06-19, 21:59

After 1 day, best poly so far:

Code:

skew 10348743.68, size 1.431e-015, alpha -9.607, combined = 6.171e-016 rroots = 4
R0 -17738381055959103027423857449147091
R1 35724233944828337
A0 2615316438868178020614768657496385102445672957000
A1 763395058741920398439908696320801376571930
A2 -242323124712140503572056753323363637
A3 -35957929238505728666568925746
A4 2763514909927293816375
A5 81777796377613
A6 2791860

This coeff also produced a 6.12e-16, and another coeff had a poly above 6e-16. Is this good enough to test against the deg 5?

VBCurtis · 2013-06-19, 22:10

Substantially the only part of sieve speed under our control is the efficiency produced by finding a better polynomial. I finished reading Murphy's thesis on polynomial selection last week, and found it very illuminating- I actually feel like I have some clue what each step we're running is doing.

Once you pick a poly, sieving is almost fire-and-forget. That said, it's educational to complete a few factorizations of manageable size before tackling a major project, to get an idea for how much work is involved as well as things that can go wrong. There are some sieve settings that are tweakable, but until you do quite a bit of reading it's a bit like turning unmarked knobs to see what happens, if you change settings that factmsieve defaults to. I don't think the script has default settings for jobs above GNFS-180 digits, but only those with access to a cluster could even consider a job at that size anyway.

Find Jeff Gilchrist's beginner's guide to NFS factoring as a first place to read...

wombatman · 2013-06-19, 23:40

Heh. That was where I started. I guess I'll have to read Murphy's paper myself and try to understand it.

Re: C212 co-factor, I stopped my current (started at 1, was just shy of 1,000,000) run, and I've restarted it with min_coeff=3,000,000 (max is ~3,700,000). Once that's finished, I'll do the -npr and -nps steps. Then we can see if I was able to come up with a better sextic than yours.

VBCurtis · 2013-06-20, 01:44

Another strong one:

Code:

skew 8074595.18, size 1.441e-015, alpha -9.429, combined = 6.203e-016 rroots = 4
R0: -16692897488829055149923474229094408
R1: 41609718449129281
A0: 605831561644026066304786497301430789930838232773
A1: -448614319761223887938593538952153812409372
A2: -175008887858843141369445379147628259
A3: 23538264716350903040547399507
A4: 4613637760164202663126
A5: -223309139179655
A6: 4019640

Batalov · 2013-06-20, 01:56

I found a couple 5.5s... Anyway, initial sieving shows that this range of e_d=6 values is not too convincing yet.
I am using parameters from the RSA-c212 experiment for test sieving:

Code:

rlim: 250000000
alim: 500000000
lpbr: 33
lpba: 33
mfbr: 66
mfba: 96
rlambda: 2.7
alambda: 3.7

Greg's poly seems to be as good or better. However, this is only a start, and there's time to get an (always unexpected) flare up to 8... 9... maybe "11"? ;-)
The RSA-c212 paper reports E = 9.55e-16 (but the CADO-implemented E value is different; the order of magnitude is the same). Let's dig a little deeper!

Batalov · 2013-06-20, 19:03

Good news! RSA-210 is not squareful.

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

2013-06-19, 20:45	#36
VBCurtis "Curtis" Feb 2005 Riverside, CA 4861₁₀ Posts	I get skews in 1-3M range from coeffs in 1e6-1e7. Edit: The very next flare has skews 15-20M, but much better scores- at least a dozen with a better E than the deg 5 target poly. I'll post the best when this npr run finishes. Last fiddled with by VBCurtis on 2013-06-19 at 20:52

2013-06-19, 22:10	#40
VBCurtis "Curtis" Feb 2005 Riverside, CA 4,861 Posts	Substantially the only part of sieve speed under our control is the efficiency produced by finding a better polynomial. I finished reading Murphy's thesis on polynomial selection last week, and found it very illuminating- I actually feel like I have some clue what each step we're running is doing. Once you pick a poly, sieving is almost fire-and-forget. That said, it's educational to complete a few factorizations of manageable size before tackling a major project, to get an idea for how much work is involved as well as things that can go wrong. There are some sieve settings that are tweakable, but until you do quite a bit of reading it's a bit like turning unmarked knobs to see what happens, if you change settings that factmsieve defaults to. I don't think the script has default settings for jobs above GNFS-180 digits, but only those with access to a cluster could even consider a job at that size anyway. Find Jeff Gilchrist's beginner's guide to NFS factoring as a first place to read... Last fiddled with by VBCurtis on 2013-06-19 at 22:11

2013-06-20, 01:56	#43
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3⁶×13 Posts	I found a couple 5.5s... Anyway, initial sieving shows that this range of e_d=6 values is not too convincing yet. I am using parameters from the RSA-c212 experiment for test sieving: Code: rlim: 250000000 alim: 500000000 lpbr: 33 lpba: 33 mfbr: 66 mfba: 96 rlambda: 2.7 alambda: 3.7 Greg's poly seems to be as good or better. However, this is only a start, and there's time to get an (always unexpected) flare up to 8... 9... maybe "11"? ;-) The RSA-c212 paper reports E = 9.55e-16 (but the CADO-implemented E value is different; the order of magnitude is the same). Let's dig a little deeper!

2013-06-20, 19:03	#44
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 9477₁₀ Posts	On the nature of RSA-210 Good news! RSA-210 is not squareful. Well, it's old news, but relevant to RSA-210 factoring ...or not. ;-)

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-19, 18:18	#34
VBCurtis "Curtis" Feb 2005 Riverside, CA 12FD₁₆ Posts	Jason- When you say "size bound", do you mean the stage 1 score or the stage 2 score? Should I set the stage 1 norm looser than 40 hits/min? -Curtis

2013-06-19, 19:11	#35
frmky Jul 2003 So Cal 2×3⁴×13 Posts	What skews are you getting? I raise the leading coefficient to keep the skew under 200M or so.

2013-06-19, 21:04	#37
jasonp Tribal Bullet Oct 2004 3,541 Posts	VBCurtis: I meant the stage 2 size bound for -nps in my explanation above. It's not clear that reducing the bound in stage 1 actually buys anything, except for dramatically reducing the search space and the rate that hits are found. Whatever hits do get found are not automatically better than hits found with a looser stage 1 bound. The new free-form interface to the poly selection seems to be working out nicely. I'll also make mods for the next release to only print out intermediate results when set for verbose output.

2013-06-19, 23:40	#41
wombatman I moo ablest echo power! May 2013 11011101001₂ Posts	Heh. That was where I started. I guess I'll have to read Murphy's paper myself and try to understand it. Re: C212 co-factor, I stopped my current (started at 1, was just shy of 1,000,000) run, and I've restarted it with min_coeff=3,000,000 (max is ~3,700,000). Once that's finished, I'll do the -npr and -nps steps. Then we can see if I was able to come up with a better sextic than yours.