mersenneforum.org GNFS poly selection
 Register FAQ Search Today's Posts Mark Forums Read

 2012-07-21, 01:38 #2 Dubslow Basketry That Evening!     "Bunslow the Bold" Jun 2011 40
 2012-07-21, 02:01 #3 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2×11×421 Posts I've been fitting E values for a long time and added this to gnfs/poly/poly_skew.c quite a while ago (see the hidden comment, too): Code:  { /* SB: tried L[1/3,c] fit; it is no better than this */ double e0 = (digits >= 121) ? (0.0607 * digits + 2.25): (0.0526 * digits + 3.23); if (degree == 4) e0 = 0.0625 * digits + 1.69; e0 = exp(-log(10) * e0); #ifdef HAVE_CUDA e0 *= 1.15; #endif logprintf(obj, "expecting poly E from %.2le to > %.2le\n", e0, 1.15 * e0); /* seen exceptional polys with +40% but that's */ /* rare. The fit is good for 88..232 digits */ } This should print a line in your msieve.log. This fit is underestimating the top end (because the higher we go, the less satisfactorily we test the poly space; there are probably excellent polys but there's not enough time to sample well). The fit for degree 4 is for the degree 4 E value; that curve is discontinuous. The low end of degree 5 has some silly hook, too (don't ask me why; it is a fit of the observed values from tons of aliquot, from Kamada's site and from B+D experiments and a few data points were taken from the MForum community jobs). E.g. for your c180 the E value is surely good. Crossover from degree 5 to degree 6 is exactly around 205 to 210 digits. You can compare the Murphy E values (as implemented by msieve) for degree 5 and degree 6 polynomials within a fudge factor of 1-1.5, in my experience. I've been running select quite a bit for the c204 with degree 6 and 5 and degree 5 won, recently. However, for RSA704 deg 6 was used and deg 5 poly seived weaker.
2012-07-21, 03:43   #4
jasonp
Tribal Bullet

Oct 2004

67168 Posts

Quote:
 Originally Posted by Dubslow Murphy E: Why do CADO-NFS and Msieve calculate different values for the same poly? And somewhat off topic, how do Msieve/GGNFS compare to CADO-NFS in the other areas besides poly select?
The E-value calculation is a nasty numerical integration; CADO-NFS compues the integral using a midpoint approximation, while msieve uses a fairly sophisticated adaptive numerical integrator. The end effect is that on average E-values reported by msieve are a little bit smaller than E-values reported by CADO-NFS, but the two packages usually give identical results to within (say) 5%.

The sieving in CADO-NFS is worlds better than what msieve has (i.e. it's a lattice sieve). The filtering and square root are quite comparable. I don't know how the linear algebra compares, since the two packages use vastly different algorithms. Paul's work with RSA704 produced a dataset that was a little undersieved, and the CADO filtering code handled it correctly when rerunning the dataset through msieve produced a bad matrix (an internal limit in the filtering code was silently exceeded).

Edit: Greg, others can point out lists of epected final E-values based on input size. Generally if you run the poly selection for a reasonable length of time you can find an E-value 25-35% better than the minimum value in the code. Paul and Thorsten reported that extremely large skew (say 1G) is too much for the siever to deal with, but generally you don't want extremely large skew because on average the polynomial size suffers too much when the skew is extremely large. In general you'll always be able to find a polynomial with good alpha and much better size, whose skew will be less-than-extremely-large.

Last fiddled with by jasonp on 2012-07-21 at 03:53

 2012-07-21, 04:01 #5 Dubslow Basketry That Evening!     "Bunslow the Bold" Jun 2011 40
 2012-07-21, 05:35 #6 frmky     Jul 2003 So Cal 40078 Posts Summary so far... Someone with more power than me can put this in the first post if he is so inclined. Tools: The current best tools are msieve and CADO-NFS. For the former, all parameters are in the source. The latter has suggested parameters for up to 171, 180, 190, and 204 digits. Perhaps interpolation/extrapolation of these will provide parameters for additional values. Is there a sense of the relative speeds and output quality of these two tools? Skew: A skew of 1G is too large. 100-200M is likely ok. A default run of msieve seems to start with a leading coefficient of 1 and that increases very slowly. For larger inputs, this can result in very large skews. What is a recommended starting leading coefficient at larger sizes? Degree: The recommended crossover from degree 5 to degree 6 is somewhere around 205-210 digits. The Murphy E values for degree 5 and degree 6 polynomials are roughly comparable, give or take a factor of 1.5. Murphy E: The Murphy E estimate from msieve is a good starting point, but search long enough and you can expect to do 25% to up to 40% better. Thanks!
2012-07-21, 06:08   #7
LaurV
Romulan Interpreter

Jun 2011
Thailand

2·3·52·61 Posts

Quote:
 Originally Posted by frmky Someone with more power than me can put this in the first post if he is so inclined.
It is easier to understand if the evolution of the discussion is not changed, at least for me, as non-native English speaker and beginner in NFS stuff. If one moves all answers in the first posts and overwrite the questions, it will look like the answers in the following posts (2,3,4) are on the thin air. This is not "reservation" thread, please let the discussion to flow, I am interested on the subject. Questions like these (well, dumber version of them) I have myself and I never asked because I was not able to put them in a reasonable form (well, to ask the right questions you have to have some knowledge about the subject, to know where to start from ).
We may need a "summary" post at the beginning of the thread (as a forum feature, not special for this thread), but overwriting the first post is generally bad for discussions like this. If one OP expects this evolution, then he should create an empty post for summary, and starts the discussion in the second post.

 2012-07-21, 10:09 #8 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 2·2,897 Posts It would be possible to edit the first post leaving what is currently there along with an explanation that the first bit is a summary added later. Another alternative is copying a random post from somewhere on the forum with a prior date to this thread and putting what we want in that also with an explanation. I do agree that it would be worth have this all in one place.
 2012-07-21, 20:32 #9 poily   Nov 2010 2·52 Posts Shi Bai keeps record of known factorization's murphy_e's here, might be useful.
2012-07-22, 18:07   #10
jasonp
Tribal Bullet

Oct 2004

2·3·19·31 Posts

Quote:
 Originally Posted by Dubslow Do you develop for CADO? How does CADO's siever compare to GGNFS? And since Greg asked as well, how do the poly selects compare, or has too little comparison work been done?
No, I'm not on the team there, though I have contributed to GMP-ECM and still do so once in a while. Alex can better comment on how the sievers compare, since I understand he wrote a great deal of the CADO version.

2012-07-22, 22:20   #11
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

132428 Posts

Quote:
 Originally Posted by jasonp No, I'm not on the team there, though I have contributed to GMP-ECM and still do so once in a while. Alex can better comment on how the sievers compare, since I understand he wrote a great deal of the CADO version.
The other thing when the question is answered is: How do they compare in how futureproof they are? What is the largest number they can realistically do? Can that be improved easily?

The ggnfs siever struck me as being rather stretched by M1061. We aren't hugely developing it further and there are some architectural difficulties that will be hit when improving it(17e not available(can this be done with any of the lasieve5 source?) etc). It also isn't portable to windows in it's fastest form.
Does the CADO siever share any of these difficulties in the same way?

 Similar Threads Thread Thread Starter Forum Replies Last Post drone84 Msieve 4 2017-06-28 09:18 firejuggler Aliquot Sequences 1 2011-02-21 06:38 Jeff Gilchrist Msieve 5 2008-12-29 23:07 nuggetprime Factoring 22 2008-08-15 10:01 bsquared Factoring 3 2007-02-28 14:22

All times are UTC. The time now is 01:10.

Fri Jan 22 01:10:18 UTC 2021 up 49 days, 21:21, 0 users, load averages: 3.79, 3.60, 3.32

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.