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

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.