[QUOTE=fivemack;188157]Putting ...
into worktodo.ini and running
[code]
msieve-svn/trunk/msieve -v -np 319000,320000
[/code]
does just produce the ' rational leading coefficient is too large ' message.

I would have expected the polynomial to come from whatever Kleinjung has been developing most recently, which is likely to have something in common with the msieve polynomial selection. Jason's comment about murphy scores was because msieve at the time had very wrong parameters for expected-Murphy due to a misunderstanding.
[/QUOTE]

Thanks. Degree 5; still; OK. I was having trouble following; which
was about things subsequently fixed, which is still an issue. So Murphy
in msieve _is_ fixed, but we're still on the -np error.

[QUOTE]
That group always seem to use rather large large-prime bounds; I didn't see any signs that I was being grotesquely sub-optimal when I did a 180-digit GNFS job with 32-bit primes, which is why I'm reasonably confident that even 187-digit GNFS could use 32-bit primes and msieve post-processing.[/QUOTE]

That's encouraging, for c187. Perhaps they're more interested in
performance and improvements for 34-bit large primes than factors
of C18x's. Is it plausible that they wanted a big matrix to test, and
chose parameters expected to produce a large matrix? And with
marginal difference in sieving time? Certainly the matrix is large!

-Bruce

[QUOTE=bdodson;188183]Thanks. Degree 5; still; ... Perhaps they're
more interested in performance and improvements for 34-bit large primes
than factors of C18x's. -Bruce[/QUOTE]

Just noticed two updates to PaulZ's page with Thorsten's May 2005 report
on the rsa200 factorization:
[code]
[private communication from 7 Sep 2008: the polynomial used had degree 5.]

[below is the polynomial used, sent by Thorsten Kleinjung, 17 Feb 2009]

27997833911221327870829467638722601621070446786955428537560009929326128400107609345671052955360856061822351910951365788637105954482006576775098580557613579098734950144178863178946295187237869221823983
#skewness 2766778.76 norm 3.83e+27 alpha -6.76 Murphy_E 3.89e-15
X5 374029011720
X4 2711065637795630118
X3 19400071943177513865892714
X2 -33803470609202413094680462360399
X1 -120887311888241287002580512992469303610
X0 38767203000799321189782959529938771195170960
Y1 12722245648421103686881
Y0 -37570227807001155896638712233675454511
M
15240406298121496354551687149477757579964572007055177494848989490034525458250363151996418176514037886590177794384616498567367206741835552043570701523997401432185870335410144421338529115688465539646714
0 200000000 3.8 35 100
0 300B000000 3.7 35 100 [/code]

So this would be one of those large c5's? And, again, with the
35-bit _very_ large large primes; degree 5, rather than deg 6. -bd

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

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 [URL="http://sourceforge.net/projects/msieve/"]msieve[/URL] 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 [URL="http://msieve.svn.sourceforge.net/viewvc/msieve/branches/msieve-gpu/"]implementation[/URL].

[QUOTE=frmky;192515]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 [URL="http://sourceforge.net/projects/msieve/"]msieve[/URL] 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 [URL="http://msieve.svn.sourceforge.net/viewvc/msieve/branches/msieve-gpu/"]implementation[/URL].[/QUOTE]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

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.

[QUOTE=xilman;192516]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.[/QUOTE]Thorsten's original documentation clears up that question. 0n is optimized for very large (>= 10) values for the -p parameter.

Paul

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 [url="http://www.cits.rub.de/itsc/conferences/factoring_workshop.html"]this workshop[/url] also has some very interesting polynomial selection talks.