SNFS Polynomial selection help?

[chris2be8]

Originally Posted by bsquared

It all comes down to the size of the norms.

To approximate the norms you need your linear and algebraic polynomials and the size of your sieve region. The linear norm is the absolute max of a - mb, where m is the common root (typically Y0) and a,b are the size of the sieve region. For lasieve4I13e, a would be 2^13 and b would be 2^12 (change as appropriate for different sievers). The algebraic norm, assuming a quintic, would be x*a^5 + y*b^5, where a,b are the same as before and x,y are the coefficients of the ^5 term and the ^0 term. Whichever norm is larger is the one you want to sieve special-q on. If you have a choice of several different polynomials, then pick the one that produces norms of approximately the same size (i.e. quartic vs. sextic). If you are stuck with a poly producing norms that are very skewed, then you can try to go to extra lengths to help the factorization on that side, like increase the factor base bounds and/or using 3LP on that side.

I'm calculating the norms as bsquared said for lasieve4I12e, at 2^12, 2^11. Is this correct? If not how should I choose the point?

I've also noticed that for gnfs polynomials the algebraic norm is dominated by c0. Would there be any value in trying to select a poly with smaller c0 (this assumes I'm calculating it correctly)?

Chris

[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.

[henryzz]

From memory lasieve5f has code for working out the size of the norms. It should be possible to take that out and put it into 4e and 5e.
It would be a nice addition to the siever's output.

[R.D. Silverman]

Originally Posted by henryzz

From memory lasieve5f has code for working out the size of the norms. It should be possible to take that out and put it into 4e and 5e.
It would be a nice addition to the siever's output.

The norm is (-b)^d f(a/b) at lattice point (a,b) for polynomial f

Over the entire lattice, the average norm for polynomial f is

1/area(R) \int \int_R log(| (-b)^d f(a/b)|) da db where R is the (rectangular)
lattice area. If a ranges from [0,M] and b ranges from [-M,M]
then one may take a 'typical' lattice point as [M/2, M/2].

Typically, the area of the lattice is upwards of 32 million.

Of course, if applying special_q to f, the average norm should be
divided by q.

[R.D. Silverman]

Could someone with access to a CA system (I have none at the moment)
please compute the Aurefeullian coefficients for 13^13H - 4^13H?

Here are the details . With H = 2K-1

we have (13^13H - 4^13H)/(13^H - 4^H) = A^2 - B^2

where A = (13^6H + k1 * 13^5H * 4^H + k2* 13^4H * 4^2H + .... + 4^6H)

and B = (13*4)^K (13^5H + j1 * 13^4H * 4^H + j2 * 13^3H * 4^2H + ..... + 4^5H)

Note that the coeffients will be symmetric (i.e. be the same when put
in reverse order)

Grinding through the equations by hand is highly tedious and error-prone.

[Batalov]

Well, for N^(13H)-1 and H = 2K+1,

#gp
(19:47) gp > factor(13^13*N^26-1)
%1 =
[13*N^2 - 1 1]
[4826809*N^12 - 4826809*N^11 + 2599051*N^10 - 1113879*N^9 + 428415*N^8 - 142805*N^7 + 41743*N^6 - 10985*N^5 + 2535*N^4 - 507*N^3 + 91*N^2 - 13*N + 1 1]
[4826809*N^12 + 4826809*N^11 + 2599051*N^10 + 1113879*N^9 + 428415*N^8 + 142805*N^7 + 41743*N^6 + 10985*N^5 + 2535*N^4 + 507*N^3 + 91*N^2 + 13*N + 1 1]

# Now, N=13*x+1/x
(20:00) gp > lindep([(4826809*N^12 - 4826809*N^11 + 2599051*N^10 - 1113879*N^9 + 428415*N^8 - 142805*N^7 + 41743*N^6 ->
%12 = [1, -1, 13, -13, -338, 676, 2197, -2197]~

So it would be 
[1, -13, 13, 338, -676, -2197, 2197] for L
[1, 13, 13, -338, -676, 2197, 2197] for M
with appropriate Y1/Y0

[R.D. Silverman]

Originally Posted by Batalov

Well, for N^(13H)-1 and H = 2K+1,

#gp
(19:47) gp > factor(13^13*N^26-1)
%1 =
[13*N^2 - 1 1]
[4826809*N^12 - 4826809*N^11 + 2599051*N^10 - 1113879*N^9 + 428415*N^8 - 142805*N^7 + 41743*N^6 - 10985*N^5 + 2535*N^4 - 507*N^3 + 91*N^2 - 13*N + 1 1]
[4826809*N^12 + 4826809*N^11 + 2599051*N^10 + 1113879*N^9 + 428415*N^8 + 142805*N^7 + 41743*N^6 + 10985*N^5 + 2535*N^4 + 507*N^3 + 91*N^2 + 13*N + 1 1]

# Now, N=13*x+1/x
(20:00) gp > lindep([(4826809*N^12 - 4826809*N^11 + 2599051*N^10 - 1113879*N^9 + 428415*N^8 - 142805*N^7 + 41743*N^6 ->
%12 = [1, -1, 13, -13, -338, 676, 2197, -2197]~

So it would be 
[1, -13, 13, 338, -676, -2197, 2197] for L
[1, 13, 13, -338, -676, 2197, 2197] for M
with appropriate Y1/Y0

The notation eludes me. L = A - B and M = A+B (presumably)
where A and B are given by my original notation. I do not see how
A and B map to the list of coefficients that you give for L and M.
y1/y0 is (presumably) 13/4 [again, by my notation] and I assume
y1/y0 = N from above. Please clarify.

I am also unfamiliar with the Pari lindep fxn. Please elucidate. The call to
lindep seems to have unbalanced parens. What is the -> notation?

Also, in %12 there are 8 elements in each list. Yet the 2nd element
got dropped in the map between %12 and your specification for L and
M. Please explain.

Also, As I noted in my post, the coefficients for A,B will be symmetric.

Call me: confused. I do not understand the notation.

[R.D. Silverman]

Originally Posted by R.D. Silverman

The notation eludes me. L = A - B and M = A+B (presumably)
where A and B are given by my original notation. I do not see how
A and B map to the list of coefficients that you give for L and M.
y1/y0 is (presumably) 13/4 [again, by my notation] and I assume
y1/y0 = N from above. Please clarify.

I am also unfamiliar with the Pari lindep fxn. Please elucidate. The call to
lindep seems to have unbalanced parens. What is the -> notation?

Also, in %12 there are 8 elements in each list. Yet the 2nd element
got dropped in the map between %12 and your specification for L and
M. Please explain.

Also, As I noted in my post, the coefficients for A,B will be symmetric.

Call me: confused. I do not understand the notation.

Something else does not make sense to me.

L is given as having the coefficients [1, -13, 13, 338, -676, -2197, 2197]
These are presumably coefficients of the degree 6 polynomial for L.

This presumably will be 13^6H, - 13*13^5H + 13*13^4H + 338 * 13^3H + ...+ 2197) for ( 13^13H-1 = (13^H-1) L * M) i.e. N = (13/1).

Yet the first two terms ALWAYS sum to zero... Something seems wrong.

[Batalov]

Yes, it was an incomplete quote. I don't have a real computer right now, so I used the Windows pari executable and then pasted everything I typed there. The Windows pari executable window has a rather miserable line editor and adds either "<--" at the left of the line (if you are editing on the far right), or "->" at the right of the line (if you are editing on the beginning). So it was sort of "fill in the blanks, if you know what I mean", which was a weak case.

Here's the complete session (no omissions), recreated on the remote computer and emailed back to myself (and this time I didn't forget that the 4^13)

Here we go, for 13^(13H)-4^(13H) and H = 2K+1, there's a form like
13^13*N^26-4^13 and N=(13/4)^H. Pari has built in Aurifeullian calculator, the rest is just the transformation for the reciprocal sextic.

~> gp
                        GP/PARI CALCULATOR Version 2.3.5 (released)

? factor(13^13*N^26-4^13)
%1 =
[13*N^2 - 4 1]
[4826809*N^12 - 9653618*N^11 + 10396204*N^10 - 8911032*N^9 + 6854640*N^8 - 4569760*N^7 + 2671552*N^6 - 1406080*N^5 + 648960*N^4 - 259584*N^3 + 93184*N^2 - 26624*N + 4096 1]
[4826809*N^12 + 9653618*N^11 + 10396204*N^10 + 8911032*N^9 + 6854640*N^8 + 4569760*N^7 + 2671552*N^6 + 1406080*N^5 + 648960*N^4 + 259584*N^3 + 93184*N^2 + 26624*N + 4096 1]
? x=13*N+4/N
%2 = (13*N^2 + 4)/N
? lindep([(4826809*N^12 - 9653618*N^11 + 10396204*N^10 - 8911032*N^9 + 6854640*N^8 - 4569760*N^7 + 2671552*N^6 - 1406080*N^5 + 648960*N^4 - 259584*N^3 + 93184*N^2 - 26624*N + 4096)/N^6,1,x,x^2,x^3,x^4,x^5,x^6])
  *** lindep: incorrect type in gtofp.
#ok, didn't work this time. Will just walk step by step:
  
? (4826809*N^12 - 9653618*N^11 + 10396204*N^10 - 8911032*N^9 + 6854640*N^8 - 4569760*N^7 + 2671552*N^6 - 1406080*N^5 + 648960*N^4 - 259584*N^3 + 93184*N^2 - 26624*N + 4096)/N^6-(x^6)
%3 = (-9653618*N^10 + 1485172*N^9 - 8911032*N^8 - 4569760*N^6 - 140608*N^5 - 1406080*N^4 - 259584*N^2 + 13312*N - 26624)/N^5
? (4826809*N^12 - 9653618*N^11 + 10396204*N^10 - 8911032*N^9 + 6854640*N^8 - 4569760*N^7 + 2671552*N^6 - 1406080*N^5 + 648960*N^4 - 259584*N^3 + 93184*N^2 - 26624*N + 4096)/N^6-(x^6-26624/4^5*x^5)
%5 = (1485172*N^8 + 5940688*N^7 + 4569760*N^5 - 140608*N^4 + 1406080*N^3 + 173056*N + 13312)/N^4
? (4826809*N^12 - 9653618*N^11 + 10396204*N^10 - 8911032*N^9 + 6854640*N^8 - 4569760*N^7 + 2671552*N^6 - 1406080*N^5 + 648960*N^4 - 259584*N^3 + 93184*N^2 - 26624*N + 4096)/N^6-(x^6-26624/4^5*x^5-13312/4^4*x^4)
%6 = (2970344*N^8 + 5940688*N^7 + 1827904*N^6 + 4569760*N^5 + 703040*N^4 + 1406080*N^3 + 173056*N^2 + 173056*N + 26624)/N^4
? (4826809*N^12 - 9653618*N^11 + 10396204*N^10 - 8911032*N^9 + 6854640*N^8 - 4569760*N^7 + 2671552*N^6 - 1406080*N^5 + 648960*N^4 - 259584*N^3 + 93184*N^2 - 26624*N + 4096)/N^6-(x^6-26624/4^5*x^5+13312/4^4*x^4)
%7 = (5940688*N^6 - 1827904*N^5 + 4569760*N^4 - 984256*N^3 + 1406080*N^2 - 173056*N + 173056)/N^3
? (4826809*N^12 - 9653618*N^11 + 10396204*N^10 - 8911032*N^9 + 6854640*N^8 - 4569760*N^7 + 2671552*N^6 - 1406080*N^5 + 648960*N^4 - 259584*N^3 + 93184*N^2 - 26624*N + 4096)/N^6-(x^6-26624/4^5*x^5+13312/4^4*x^4+173056/4^3*x^3)
%8 = (-1827904*N^4 - 913952*N^3 - 984256*N^2 - 281216*N - 173056)/N^2
? (4826809*N^12 - 9653618*N^11 + 10396204*N^10 - 8911032*N^9 + 6854640*N^8 - 4569760*N^7 + 2671552*N^6 - 1406080*N^5 + 648960*N^4 - 259584*N^3 + 93184*N^2 - 26624*N + 4096)/N^6-(x^6-26624/4^5*x^5+13312/4^4*x^4+173056/4^3*x^3- 173056/4^2*x^2)
%9 = (-913952*N^2 + 140608*N - 281216)/N
? (4826809*N^12 - 9653618*N^11 + 10396204*N^10 - 8911032*N^9 + 6854640*N^8 - 4569760*N^7 + 2671552*N^6 - 1406080*N^5 + 648960*N^4 - 259584*N^3 + 93184*N^2 - 26624*N + 4096)/N^6-(x^6-26624/4^5*x^5+13312/4^4*x^4+173056/4^3*x^3- 173056/4^2*x^2-281216/4*x)
%10 = 140608
? (4826809*N^12 - 9653618*N^11 + 10396204*N^10 - 8911032*N^9 + 6854640*N^8 - 4569760*N^7 + 2671552*N^6 - 1406080*N^5 + 648960*N^4 - 259584*N^3 + 93184*N^2 - 26624*N + 4096)/N^6-(x^6-26624/4^5*x^5+13312/4^4*x^4+173056/4^3*x^3- 173056/4^2*x^2-281216/4*x+140608)
%11 = 0
? \q
Goodbye!

~> gp
                                                                     GP/PARI CALCULATOR Version 2.3.5 (released)

? x^6-26624/4^5*x^5+13312/4^4*x^4+173056/4^3*x^3- 173056/4^2*x^2-281216/4*x+140608
%1 = x^6 - 26*x^5 + 52*x^4 + 2704*x^3 - 10816*x^2 - 70304*x + 140608
?

(I left a typo in it, when I used the wrong sign...)
So, for L side, the polynomial would be x^6 - 26*x^5 + 52*x^4 + 2704*x^3 - 10816*x^2 - 70304*x + 140608
For M side, flip signs for all odd degrees.

Now what is x? For factoring 13^221-4^221, N=(13/4)^8, and
x = 13*N+4/N
x = Y1/Y0 = 8650415936561207117/53459728531456

[Batalov]

P.S. I think lindep doesn't want to work on polynomials but when we will give it a numeric value (any!), it will chew on it and will reply right away.

A new session, with a slight change:

? N = 1001; x=13*N+4/N;
? lindep([(4826809*N^12 - 9653618*N^11 + 10396204*N^10 - 8911032*N^9 + 6854640*N^8 - 4569760*N^7 + 2671552*N^6 - 1406080*N^5 + 648960*N^4 - 259584*N^3 + 93184*N^2 - 26624*N + 4096)/N^6,1,x,x^2,x^3,x^4,x^5,x^6]) 
%4 = [-1, 140608, -70304, -10816, 2704, 52, -26, 1]~
? ?lindep
lindep(x,{flag=0}): integral linear dependencies between components of x. flag is optional, and can be 0: default, guess a suitable accuracy, or positive: accuracy to use for the computation, in decimal digits.

I forgot that it needs a numeric vector on input.
The first value of the return (-1) is just the weight for the input polynomial; the rest is the answer (in [1,x,x^2,x^3,x^4,x^5,x^6])

[R.D. Silverman]

Originally Posted by Batalov

P.S. I think lindep doesn't want to work on polynomials but when we will give it a numeric value (any!), it will chew on it and will reply right away.

A new session, with a slight change:

? N = 1001; x=13*N+4/N;
? lindep([(4826809*N^12 - 9653618*N^11 + 10396204*N^10 - 8911032*N^9 + 6854640*N^8 - 4569760*N^7 + 2671552*N^6 - 1406080*N^5 + 648960*N^4 - 259584*N^3 + 93184*N^2 - 26624*N + 4096)/N^6,1,x,x^2,x^3,x^4,x^5,x^6]) 
%4 = [-1, 140608, -70304, -10816, 2704, 52, -26, 1]~
? ?lindep
lindep(x,{flag=0}): integral linear dependencies between components of x. flag is optional, and can be 0: default, guess a suitable accuracy, or positive: accuracy to use for the computation, in decimal digits.

I forgot that it needs a numeric vector on input.
The first value of the return (-1) is just the weight for the input polynomial; the rest is the answer (in [1,x,x^2,x^3,x^4,x^5,x^6])

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.