SNFS Polynomial selection help?

[chris2be8]

Originally Posted by fivemack

I think bsquared's calculation is forgetting the special-Q part of the sieving. a and b are much more like 2^13*sqrt(Q) than like 2^13, where Q is somewhere between 2^23 and 2^27 for the sort of sizes we're looking at; this explains why c0 appears to be dominating the norm so much.

For skewed polynomials it's more like a=2^13*sqrt(Q)*sqrt(skew) and b=2^13*sqrt(Q)/sqrt(skew) ; the large c0 is precisely because of the skew.

Thanks, that's the missing factor. Since factMsieve.pl sieves from alim/2 or rlim/2 upwards assuming Q will average alim or rlim should be enough to work out which side it's best to sieve on.

But I was originally planning to adjust alim and rlim (and lpba/r, mfba/r.and a/rlambda) according to the norms on each side. I'll have to think how to do it (possibly by assuming a default a/rlim, then adjusting according to the norms).

Chris

[Batalov]

Originally Posted by R.D. Silverman

Much obliged for your help.. As it happens, I did the whole thing by hand
(error prone! yech! not recommended!)

In the original format I suggested, the answer is:

13^13H - 4^4H = (13^H - 4^H) (A+B)(A-B)

with A = (13^6H + 7*13^5H*4^H + 15*13^4H*4^2H + 19*52^3H +
15*13^2H*4^4H + 7*13^H * 4^5H + 4^6H)

B = 2^H * 13^k * (1,3,5,5,2, 1)

I have simply given the coefficients for the homogeneous polynomial for
B.

Your help was appreciated.

Sure thing. It was fun to do a small homework.

Andrey Kulsha had the polynomials collected in one place, but I forgot at the time where the link was, and it was fun to recreate it from scratch Pari, though I thought that the most tedious part was to get to the degree-6 poly (for practical use in an NFS project). For that part, I definitely would not want to use paper and pencil.

[xilman]

Originally Posted by chris2be8

Thanks, that's the missing factor. Since factMsieve.pl sieves from alim/2 or rlim/2 upwards assuming Q will average alim or rlim should be enough to work out which side it's best to sieve on.

But I was originally planning to adjust alim and rlim (and lpba/r, mfba/r.and a/rlambda) according to the norms on each side. I'll have to think how to do it (possibly by assuming a default a/rlim, then adjusting according to the norms).

Chris

FWIW, I take the view that if it takes me longer to compute which side to do the sieving and then verifying it with trials than it wastes by just going with what factMsieve.pl decides, then I chicken out. Computation is cheap; thought is often better used elsewhere.

There are a number of scenarios where, in the words of the old adage, a week's computation saves an hour in the library. However, when dealing with relatively simple problems that have been solved and encapsulated in clever software it's often cost-effective to exploit the work of the authors of that software.

At the moment and specifically for the GCW project, the only experimentation I do is to choose between a sextic and quintic based on the Murphy-e value because that takes at most 5 minutes and the result varies between candidates. Taking several hours to evaluate which factorization will take 120 hours and which 125 hours is just not cost-effective IMAO.

YMMV,

Paul

[chris2be8]

I'm trying to make factMsieve.pl do a better job selecting parms for SNFS polys, they vary quite a lot in degree, coefficients etc. Choosing which side to sieve on will be a good start. Choosing parms for each side according to the norms on that side will come later. Ultimately it should sieve the first range and see how good a yield it gets, then automatically adjust parms if necessary.

But don't hold your breath waiting for it all.

Chris

[fivemack]

Doing a bit of sieving and using that to set alim is what my aliquot.py script has been doing for GNFS since I wrote it; I suppose I have fairly good estimates as to where to start, and for SNFS you have more of a risk of starting in a completely wrong place and needing to do two or three trials to converge to something sensible.