New polynomial finder discussion - Page 10

xilman · 2009-10-11, 19:30

Continuing my exploration of the latest ggnfs I came across a variety of polynomial finders, one of which is very familiar --- pol51opt.

There are two, pol51m0[bn], which appear to be developments from the old pol51m I know well. What is the difference between these two in practice? I.e, which is the better in some quantifiable sense.

I also came across polyselect which is completely new to me. Examining it shows that it can handle quartics and sextics as well as the quintics found by the others. It also appears to be more self-contained in that it doesn't seem to require and optimizating second stage.

What are the benefits of polyselect over the other two?

Sorry if these are dumb questions but, to be honest, the ggnfs documentation does not seem to be either transparent or complete. A Google search to try to find answers for myself led me straight to this thread...

Oh yes: one more question. I know how to split the search ranges for pol51m0[bn] so that the search can be parallelized over a number of machines. I've not yet found out how to use polyselect in this way. If it's possible, what's the way to do it?

Paul

frmky · 2009-10-11, 19:50

polyselect is an implementation of Montgomery/Murphy polynomial selection by Chris Monico. It supports 4th and 6th degree polynomials, but is significantly slower. The recent versions of msieve now have a much better implementation that supports degrees 4 and 5, and may support degree 6 (it's not clear from the changes file). Jason has also started a CUDA implementation.

xilman · 2009-10-11, 20:15

Quote:

Originally Posted by frmky

polyselect is an implementation of Montgomery/Murphy polynomial selection by Chris Monico. It supports 4th and 6th degree polynomials, but is significantly slower. The recent versions of msieve now have a much better implementation that supports degrees 4 and 5, and may support degree 6 (it's not clear from the changes file). Jason has also started a CUDA implementation.

Thanks. That's helpful.

The most noticeable difference between pol51m0n and pol51m0b appears to be that the former multiplies the given a5 values by 1e6 and the latter by 1e3. There are significant differences between the sources, the reasons for which are not apparent at a glance.

Experimentation with msieve would seem to be in order. Do you happen to know whether it finds "better" polynomials than pol51m or does it search the same space more efficiently?

Paul

Batalov · 2009-10-11, 20:47

I had hit a snag a while ago, trying to use msieve -np for a gnfs-180, so now I am establishing a point of reference with pol51 (that is a reference for the future selection re-run with msieve; the e-value reference is well established by Tom+forum with 5,421-). With some creative parameter tweaking, I guess, one can spend not a month but a week on it and still get a useable (even if suboptimal) polynomial. In just the first 4-CPU day, I've got a 5.56e-14 poly which looks fine already for this size; probably within 20% of the feasible best. (The 5,421- number was just a bit smaller and had a 6.90e-14 poly but the search was extensive!)

msieve -np worked very well for the gnfs-174 (just finished it, B+D), but somewhere above 177-178 the selection code hits the internal arithmetic limit. Jason said that a 96-bit math will help but it is not on the immediate roadmap. For the gnfs-180, I was able to search just the first range of very low c5s, and the best was only ~3e-14 with no prospect to extend with current msieve binary.

xilman · 2009-10-11, 21:50

Quote:

Originally Posted by xilman

The most noticeable difference between pol51m0n and pol51m0b appears to be that the former multiplies the given a5 values by 1e6 and the latter by 1e3. There are significant differences between the sources, the reasons for which are not apparent at a glance.

Thorsten's original documentation clears up that question. 0n is optimized for very large (>= 10) values for the -p parameter.

Paul

jasonp · 2009-10-12, 03:10

For polynomial degree d, pol51m0b searches through all a5 and all leading rational coefficients that are a product of small primes congruent to 1 mod d, times a small cofactor that is a product of other primes. pol51m0n does the same, but the a5 values it chooses to search are the result of an optimization process that tries to maximize the number of usable '1 mod d' primes for that a5. I don't think anybody uses pol51m0n; by the time it becomes faster to switch over, you can generate better degree-6 polynomials.

The GGNFS polyselect program is a very rough first cut at a poly selection utility; the polynomials it generates really can't compete with the results from pol5.

Msieve uses Kleinjung's improved algorithm to choose polynomials with enormous amounts of skew, as well as a high-performance pol51opt-equivalent that can search the resulting huge search space for rotations that lead to good root properties. I'm pretty confident that the latter is the best code of its kind that's publicly available, but for large problems most of the runtime is spent in the first stage, and there pol51m0b is very tough to beat. I'm still working out the best combination of parameters that maximize the search speed.

Msieve can generate degree 4 polynomials (very good ones), but degree-6 polynomials generate such a huge search space in stage 2 that you'd never finish the search if you tried. Fixing that is on my to-do list for someday.

One big advantage of Kleinjung's improved algorithm is that it's pretty conceptually straightforward, and maps well to special-purpose hardware. I'll announce my CUDA work in another thread, but in the meantime this workshop also has some very interesting polynomial selection talks.

2009-10-11, 19:30	#100
xilman Bamboozled! "𒉺𒌌𒇷𒆷𒀭" May 2003 Down not across 10101000000001₂ Posts	Difference between polynomial finders Continuing my exploration of the latest ggnfs I came across a variety of polynomial finders, one of which is very familiar --- pol51opt. There are two, pol51m0[bn], which appear to be developments from the old pol51m I know well. What is the difference between these two in practice? I.e, which is the better in some quantifiable sense. I also came across polyselect which is completely new to me. Examining it shows that it can handle quartics and sextics as well as the quintics found by the others. It also appears to be more self-contained in that it doesn't seem to require and optimizating second stage. What are the benefits of polyselect over the other two? Sorry if these are dumb questions but, to be honest, the ggnfs documentation does not seem to be either transparent or complete. A Google search to try to find answers for myself led me straight to this thread... Oh yes: one more question. I know how to split the search ranges for pol51m0[bn] so that the search can be parallelized over a number of machines. I've not yet found out how to use polyselect in this way. If it's possible, what's the way to do it? Paul

2009-10-11, 20:47	#103
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3⁶·13 Posts	pol51 still leading for gnfs >~177 I had hit a snag a while ago, trying to use msieve -np for a gnfs-180, so now I am establishing a point of reference with pol51 (that is a reference for the future selection re-run with msieve; the e-value reference is well established by Tom+forum with 5,421-). With some creative parameter tweaking, I guess, one can spend not a month but a week on it and still get a useable (even if suboptimal) polynomial. In just the first 4-CPU day, I've got a 5.56e-14 poly which looks fine already for this size; probably within 20% of the feasible best. (The 5,421- number was just a bit smaller and had a 6.90e-14 poly but the search was extensive!) msieve -np worked very well for the gnfs-174 (just finished it, B+D), but somewhere above 177-178 the selection code hits the internal arithmetic limit. Jason said that a 96-bit math will help but it is not on the immediate roadmap. For the gnfs-180, I was able to search just the first range of very low c5s, and the best was only ~3e-14 with no prospect to extend with current msieve binary. Last fiddled with by jasonp on 2009-10-12 at 03:13 Reason: 48-bit -> 96-bit (72-bit might be enough, FYI)

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
Polynomial algorithm	diep	Factoring	7	2012-09-29 12:09
Question about polynomial finder	jordis	Msieve	1	2009-01-10 17:58
[Need help] about Matrix Polynomial	buan	Homework Help	3	2007-07-17 15:07
Polynomial	R.D. Silverman	NFSNET Discussion	13	2005-09-16 20:07

2009-10-11, 19:50	#101
frmky Jul 2003 So Cal 2×3⁴×13 Posts	polyselect is an implementation of Montgomery/Murphy polynomial selection by Chris Monico. It supports 4th and 6th degree polynomials, but is significantly slower. The recent versions of msieve now have a much better implementation that supports degrees 4 and 5, and may support degree 6 (it's not clear from the changes file). Jason has also started a CUDA implementation.

2009-10-12, 03:10	#105
jasonp Tribal Bullet Oct 2004 3,541 Posts	For polynomial degree d, pol51m0b searches through all a5 and all leading rational coefficients that are a product of small primes congruent to 1 mod d, times a small cofactor that is a product of other primes. pol51m0n does the same, but the a5 values it chooses to search are the result of an optimization process that tries to maximize the number of usable '1 mod d' primes for that a5. I don't think anybody uses pol51m0n; by the time it becomes faster to switch over, you can generate better degree-6 polynomials. The GGNFS polyselect program is a very rough first cut at a poly selection utility; the polynomials it generates really can't compete with the results from pol5. Msieve uses Kleinjung's improved algorithm to choose polynomials with enormous amounts of skew, as well as a high-performance pol51opt-equivalent that can search the resulting huge search space for rotations that lead to good root properties. I'm pretty confident that the latter is the best code of its kind that's publicly available, but for large problems most of the runtime is spent in the first stage, and there pol51m0b is very tough to beat. I'm still working out the best combination of parameters that maximize the search speed. Msieve can generate degree 4 polynomials (very good ones), but degree-6 polynomials generate such a huge search space in stage 2 that you'd never finish the search if you tried. Fixing that is on my to-do list for someday. One big advantage of Kleinjung's improved algorithm is that it's pretty conceptually straightforward, and maps well to special-purpose hardware. I'll announce my CUDA work in another thread, but in the meantime this workshop also has some very interesting polynomial selection talks.