Question about polynomial finder

jordis · 2009-01-10, 11:07

Hi,

To know if we have a good polynomial, the only way to know it, it's to make a test
in a determinate range and see if we found a lot of relations.

But in one thread I read something about Murphy alpha and
size score, the polynomial its better against these values are smaller?

How must be this values to assume than the polynomial is better than others

Thanks

jasonp · 2009-01-10, 17:58

The best test to determine how good a polynomial will be involves actually doing a little sieving with that polynomial. Unfortunately, this is very slow and you cannot afford to test sieve more than maybe 5 polynomials. To rate polynomials by non-sieving means, you have a few options, but all the options reduce to computing a probability that you will find many relations, based on the average size of values of the polynomial.

- Murphy's alpha value measures the contribution of small primes to the average sieve value; the larger the contribution (i.e. the more negative the alpha), then the smaller the size of sieve values that are left over for the rest of the sieving to deal with. The alpha value modifies the next two rating methods.

- Bernstein's scoring function uses a nasty superelliptic integral, computed numercially, to produce a number that is proportional to the number of sieve values that can achieve a given size. Larger values of this number imply more relations found during sieving. This scoring measure is computed very quickly and is accurate, but the big problem with it is that Bernstein's function will count polynomial values that would never be reached by the sieving, so it overestimates the true score by some unknown amount. Msieve currently uses Bernstein's function modified by Murphy's alpha

- Murphy's E function considers everything: the size and shape of the sieving region, Murphy's alpha, and the probability that sieve values will be smooth given the size of the factor base. It's a lot slower than Bernstein's function but much more accurate. The GGNFS tools use Murphy's E function, and v1.40 of msieve will use a rating system that resembles E.

My experiments show that a good Murphy score pretty much requires a good Bernstein score, but the reverse is not necessarily true. The next msieve version uses Bernstein's score to do most of the work of optimizing polynomials, then switches to Murphy's score at the end to finalize the polynomial and choose the best sieving region.

2009-01-10, 11:07	#1
jordis Jan 2009 2³ Posts	Question about polynomial finder Hi, To know if we have a good polynomial, the only way to know it, it's to make a test in a determinate range and see if we found a lot of relations. But in one thread I read something about Murphy alpha and size score, the polynomial its better against these values are smaller? How must be this values to assume than the polynomial is better than others Thanks

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
Choosing the best polynomial	wombatman	Msieve	123	2013-08-27 11:27
Polynomial selection stage question	rawbinary	Msieve	12	2010-08-02 23:41
New polynomial finder discussion	smh	Msieve	104	2009-10-12 03:10
Polynomial	R.D. Silverman	NFSNET Discussion	13	2005-09-16 20:07

2009-01-10, 17:58	#2
jasonp Tribal Bullet Oct 2004 3,541 Posts	The best test to determine how good a polynomial will be involves actually doing a little sieving with that polynomial. Unfortunately, this is very slow and you cannot afford to test sieve more than maybe 5 polynomials. To rate polynomials by non-sieving means, you have a few options, but all the options reduce to computing a probability that you will find many relations, based on the average size of values of the polynomial. - Murphy's alpha value measures the contribution of small primes to the average sieve value; the larger the contribution (i.e. the more negative the alpha), then the smaller the size of sieve values that are left over for the rest of the sieving to deal with. The alpha value modifies the next two rating methods. - Bernstein's scoring function uses a nasty superelliptic integral, computed numercially, to produce a number that is proportional to the number of sieve values that can achieve a given size. Larger values of this number imply more relations found during sieving. This scoring measure is computed very quickly and is accurate, but the big problem with it is that Bernstein's function will count polynomial values that would never be reached by the sieving, so it overestimates the true score by some unknown amount. Msieve currently uses Bernstein's function modified by Murphy's alpha - Murphy's E function considers everything: the size and shape of the sieving region, Murphy's alpha, and the probability that sieve values will be smooth given the size of the factor base. It's a lot slower than Bernstein's function but much more accurate. The GGNFS tools use Murphy's E function, and v1.40 of msieve will use a rating system that resembles E. My experiments show that a good Murphy score pretty much requires a good Bernstein score, but the reverse is not necessarily true. The next msieve version uses Bernstein's score to do most of the work of optimizing polynomials, then switches to Murphy's score at the end to finalize the polynomial and choose the best sieving region.