Reserved for MF - Sequence 4788

[VBCurtis]

Originally Posted by charybdis

... But are close to 4G raw relations really necessary? Surely we want to choose parameters so that we don't have a duplication rate near 50%?

Edit: the usual doubling rule probably doesn't hold up around the degree 5/6 boundary does it? The degree 6 curve intercepts the degree 5 curve, so once you switch to degree 6 the number of digits per doubling should go up...

You're quite right- The 2330L Cunningham C207 job took 3300M raw relations to yield 1800M uniques, a terrible ratio. However, my point remains that if we went for bigger LP bounds than 34/35, we *would* risk needing more than 2^32 relations.

I imagine something like 2.8-3.0G raw relations to yield 2.0G uniques for this job? I was adding 15% to the previous job's numbers, forgetting just how bad the unique ratio was.

We don't have much data on deg 6 poly score scaling- pretty much just the CADO group's polys for RSA-220/230/240/250. It hasn't crossed my mind to fit a curve to those scores and test for scaling... Good idea!

[charybdis]

Originally Posted by VBCurtis

However, my point remains that if we went for bigger LP bounds than 34/35, we *would* risk needing more than 2^32 relations.

Indeed. And if msieve is used for postprocessing there's a 2^32 limit there too; duplicates could be removed beforehand, so 35/35 would be possible but maybe not 35/36.

We don't have much data on deg 6 poly score scaling- pretty much just the CADO group's polys for RSA-220/230/240/250. It hasn't crossed my mind to fit a curve to those scores and test for scaling... Good idea!

Be careful with these types of score comparisons. Msieve/cownoise scores are not suitable for this purpose, as I discovered when comparing them with the CADO scores for my c220 polys. Cownoise still puts the polys pretty much in the same order as CADO, but the ratios are larger: for example, CADO scored the best poly 13% higher than the 10th best, but cownoise scored it 22% higher. I'm inclined to trust the CADO ratios more, because it estimated Murphy-E using the sieving parameters I gave it, rather than the standard values used by msieve/cownoise which are far too small for numbers of this size.

So if you want to compare the scores of the RSA polynomials, you'll need to use CADO's "polyselect3" with some appropriate parameters. This is left as an exercise for the reader :)

[bur]

Originally Posted by charybdis

We must have spent at least 2 core-years on polyselect so far, and I've just queued up another ~1.5 core-years, or 1% of the estimated sieving time.

My mistake was I underestimated how quickly core-time racks up. Even my two small searches came to nearly 3 core-months already.

[VBCurtis]

Originally Posted by bur

My mistake was I underestimated how quickly core-time racks up. Even my two small searches came to nearly 3 core-months already.

No mistake, sir- the typical rule of thumb is 5% of expected sieve time for poly-select time. We're at about 2%?

It's just that we found a poly scoring almost exactly what we hoped for. As you and Charybdis point out, finding one good one doesn't rule out finding an even-better one; I support a continued search, and finding additional 3.8's would support the idea that a 3.9 or higher is "out there" to be found. I'm taking a break from the search, but if we become convinced the 3.8 is not a massive outlier I'll return to this in a week or three.

[bur]

By mistake I meant that I'd have guessed we maybe did 3-4 core-months in total.

So I'll continue the poly search at 6e6-7e6, it might at least give some idea how rare 3.5+ polys are.

[bur]

If it's not sure whether larger or smaller P is better and some polynomials will never be found with a specific P, wouldn't it make sense to search the small value ranges again with different P?


If small leading coefficients tend to produce better polys, then going through these ranges with several different P could be worthwhile.

[charybdis]

Originally Posted by bur

If small leading coefficients tend to produce better polys, then going through these ranges with several different P could be worthwhile.

I'm not sure we've got to large enough coefficients that "small leading coefficients tend to produce better polys" is having much of an effect. For degree 5 jobs it would definitely be noticeable at this point, but so far the best 3 CADO polys have come from (pre-sizeopt) leading coeffs around 19e6, 21e6 and 23e6. In addition, basically every polynomial is getting its leading coefficient multiplied up in the optimization process, so there can't be too much harm in having a larger coefficient. In contrast, with large degree 5 searches there are usually a few polys in the top 10 that keep their original leading coefficient.

[bur]

The searches of low value ranges are faster though, right? It might still make sense to go over them again with a different P. On the other hand, P=10e6 and P=12e6 still have a lot of overlap so the time could very well better be spend on a different range.


BTW, there is no random element to the search or is there?

[VBCurtis]

No random element.

I believe altering P can be useful, but I wouldn't repeat coefficient ranges.

Smaller coeff's usually take a little longer to search; that is, 30-31M should run slightly faster than 2-3M.

Smaller P values do run faster.

[bur]

I believe altering P can be useful, but I wouldn't repeat coefficient ranges.

Because the limited time is better spend on doing a fresh range?

Smaller coeff's usually take a little longer to search;

I thought it was the other way around since larger incr is used for larger value ranges to prevent long search times.

[VBCurtis]

Changing P leads to some duplication of search, better to try an entirely new range. You'd need a P value half or double the previous one, and we have reason to think either of those options is suboptimal (though that's a judgement of "per unit time", not a prediction that you wouldn't find a better poly). We don't know what the "Best" P is for a given size of input, but hopefully we're close enough to "best" that halving or doubling P would be less efficient than running a new range with P altered by a little (say, something in a range of 8 to 20M). All the default CADO params files from C195 to C230 use P = 10e6, while only C180/185/190 use 5e6 and C240 uses 20e6. To me, that indicates that not much testing was done on the big sample-params files for "best" P, and we should experiment a little.

As for the second question, my comment was intended to be "for constant param choices", i.e. same incr such as Charybdis searching ~20M while you and I searched at 2 or 3M.