GGNFS questions and Answers

[R.D. Silverman]

Originally Posted by xilman

For the line siever you just use the recipe you already gave: sieve over a rectangle which has dimensions in the ratio 1:skew

Actually, that's not quite right for two reasons. First, it's the ratio |a_max| / b_max that should be equal to skew --- the real rectangle is twice as wide because a may be negative.

Secondly, the optimal sieving region is not rectangular, as Bob reminds us every now and again. However, the true optimal area has a very complex shape in general and is not known a priori, so everyone uses rectangularly tiled approximations to it. Traditionally a single rectangle is used; the recipe above is appropriate in this case. NFSNET generally uses a "top hat" approximation, which is a wide rectangle at low b and a narrower one at larger b values. I do not know the precise details of how Bob chooses his rectangular tiles in his line siever, but it seems fairly clear that he uses a number of line widths as he progresses to larger b, and that he adapts the widths according to some function of the yield of relations as the sieving progresses.

Paul

Suppose the probability that a point (b,a) yields a relation is G(b,a).
Then, z = G(b,a) is a surface. A picture of this surface can be found in my
paper on SNFS optimization.

If we now take a plane that is parallel to the (b,a) plane at height
lambda above the (b,a) plane and intersect it with the surface G(b,a) we
get a curve. Project this curve straight down onto the (b,a) plane and
this gives us the optimal sieve region. Proving this, and determining
lambda was the main theorem of my paper. A picture of this curve
can also be found in my paper. It "somewhat resembles" a hyperbola
whose asymptotes are the b and a axes.


I tried doing the same thing for the lattice sieve, but now the optimal
boundary is an affine transform of the boundary I discussed above and
needs to be RECOMPUTED every time special-q changes. And it complicates
the sieve procedure. I did not find [based on some VERY crude experiments]
that it was worth doing.

Note that for line sieving, the yield decreases as b increases.

For the lattice siever, for each special q, yield is a function of the size
of that special q and the AREA of the sieve region. As special-q
increases, yield also goes down; but not as quickly as with the line
siever. I am now looking at an approach that still uses parallelograms
for the shape of the sieve region for each special-q, but adjusts its
AREA as q changes. It does seem to have some effect. [Work still in
progress]

[xilman]

Originally Posted by R.D. Silverman

If we now take a plane that is parallel to the (b,a) plane at height
lambda above the (b,a) plane and intersect it with the surface G(b,a) we
get a curve. Project this curve straight down onto the (b,a) plane and
this gives us the optimal sieve region. Proving this, and determining
lambda was the main theorem of my paper. A picture of this curve
can also be found in my paper. It "somewhat resembles" a hyperbola
whose asymptotes are the b and a axes.

I remember reading your pre-publication version of that paper and sending you feedback on it. I don't remember the fine details now and don't have the paper available.

However, I seem to remember that you omitted consideration of the root properties of the polynomials. If my memory is correct, then I suggest that your hyperbola-like curve does not generate the optimum sieving area. It certainly gives a much better area than a simple rectangle.

I've seen several other pictures of sieving yields as a function of position in the (a,b) plane, first in a paper by Marije Elkenbracht-Huizing in Experimental Mathematics (later a chapter in her thesis) and subsequently elsewhere. Arjen Lenstra calls them "chicken foot" surfaces. A contour at any particular yield has fingers (or should that be toes?) along the directions where a/b is a good approximation to a root of the polynomial. We assume, as usual, that one polynomial is linear. Lenstra calls these plots "crown diagrams". He has a way with words ...

It would appear, to me at least, that the optimal shape is not as you describe but rather closer to the crown diagram. Approximating such a shape with rectangular tiles is difficult to do in a computationally efficient manner.


Paul

[VJS]

Thanks for all of the advise, I posted this polynomial since it's one of the more difficult ones I have on my plate. With a degree of 175 as Dr.silverman points out I'm wondering if I should simply use ggnfs. ( I know it's the easy way out mentally, I like a challenge but sometimes I'll settle with success)

With x^5 - 647293 and root 647293^6, factor base sizes of 1 million
primes, and large prime bounds of 500 million, my lattice siever
produces about 14.2 relations/sec on my 1.6GHz laptop.

That's much better than I was getting on a faster machine...

I will increase my factor base (as per your suggestion) and probably run this one manually as opposed to using the script. It's a learning process but I'm getting the hang of it. I seem to have polynomial selection down, and I'm assuming I calculated skew correctly.

If I have additional problems I'll ask again.

[R.D. Silverman]

Originally Posted by xilman

I remember reading your pre-publication version of that paper and sending you feedback on it. I don't remember the fine details now and don't have the paper available.

However, I seem to remember that you omitted consideration of the root properties of the polynomials. If my memory is correct, then I suggest that your hyperbola-like curve does not generate the optimum sieving area. It certainly gives a much better area than a simple rectangle.

I've seen several other pictures of sieving yields as a function of position in the (a,b) plane, first in a paper by Marije Elkenbracht-Huizing in Experimental Mathematics (later a chapter in her thesis) and subsequently elsewhere. Arjen Lenstra calls them "chicken foot" surfaces. A contour at any particular yield has fingers (or should that be toes?) along the directions where a/b is a good approximation to a root of the polynomial. We assume, as usual, that one polynomial is linear. Lenstra calls these plots "crown diagrams". He has a way with words ...

It would appear, to me at least, that the optimal shape is not as you describe but rather closer to the crown diagram. Approximating such a shape with rectangular tiles is difficult to do in a computationally efficient manner.


Paul

I regret that the diagram is crude.

It will depend on the value of lambda.

I denote the sieve bounday by the \
The "chicken feet" are shown by /
Generally, they do not interfere with the optimal boundary. Even though
the 'feet' can extend outside the boundary I have drawn, you do not
want to sieve "along" the feet outside the boundary area

|\
   \|
|    \
|       \                           /     Do not want to sieve here despite the 'ridge'
|           \                 /
|  sieve here     \  /
|                  /            \
|         /                                                \
| /                   sieve here
--------------------------------------------

[R.D. Silverman]

Originally Posted by R.D. Silverman

I regret that the diagram is crude.

It will depend on the value of lambda.

I denote the sieve bounday by the \
The "chicken feet" are shown by /
Generally, they do not interfere with the optimal boundary. Even though
the 'feet' can extend outside the boundary I have drawn, you do not
want to sieve "along" the feet outside the boundary area


|\
\|
| \
| \ / Do not want to sieve here despite the 'ridge'
| \ /
| sieve here \ /
| / \
| / \
| / sieve here
--------------------------------------------

OY! When I submitted this, the software deleted all the extra spaces
between the / and the \. The diagram does not show up at all.

See my paper.

[smh]

Originally Posted by R.D. Silverman

OY! When I submitted this, the software deleted all the extra spaces
between the / and the \. The diagram does not show up at all.

Use de [ CODE ] tags

[smh]

Originally Posted by VJS

Thanks for all of the advise, I posted this polynomial since it's one of the more difficult ones I have on my plate.

If it's a c117 wouldn't GNFS be much faster?

[R.D. Silverman]

Originally Posted by smh

If it's a c117 wouldn't GNFS be much faster?

About the same. The C117 is roughly 1/3 smaller. This is approximately
the break even point for switching to GNFS.

[trilliwig]

Originally Posted by VJS

I have a feeling I should start with a higher alim and q0: But the script always resets these.

If you want to adjust alim or q0, you should add the setting to your .poly file. The .job file is automatically generated and the Perl script won't notice any changes to it.

[VJS]

Thanks Trilliwig,

You pointed me in the direction of the problem. It appears that when the script it intially generates a job file, I check the settings they are generally fine. (At least as far as I know) But if you don't like the generated job file, q0 etc... and you decide to change it using the polyfile you must delete the generated job file. If not the new alim, q0 placed in the poly are ignored and it simply continues with the previous job, future job files also ignore the poly file.

About the same. The C117 is roughly 1/3 smaller. This is approximately
the break even point for switching to GNFS.

Thanks for the confirmation 117 x 3/2 = 175.5 (SNFS difficulty break even). I also find it more interesting to generate my own poly, skipping the poly5 program... SNFS also consumes less disk space if I recall correctly. (not experienced enough yet to make this statement as fact).

---------------------------------

I've been looking through forums for polynomial selection and have found xilliams phi'c program. I think this is one of those, an afternoon in the library can be avoided with 3 months of hard lab work, situations.

It works very well, wow... a proof reader or sorts. I tried a few others however I had a problem using it with a particular expression. Or I'm not implementing the program correctly.

A c113 for (215650177543^11-1)/215650177542

I was thinking a degree 5

c5: 215650177543
c0: 1
m: 215650177543^2

but one might be able to do this one degree 4 or 6.

c?:1
c0: 215650177543
m: 215650177543^2 or ^3 depending on degree

However phi suggested the following poly file:

skew: 1.00
c5: 1
c4: 1
c3: -4
c2: -3
c1: 3
c0: 1
y1: -215650177543
y0: 46504999074327421516850
m: 215650177543
type: snfs

Which would be a difficulty of 113 however running the script specified a difficult of 54-digits!!!. Followed by a crash creating the factor base.

Error: Bad polynomial: f(m): !=0 (mod n)
m=215650177543

If I'm correct the reason why the polynomial didn't work is b/c of the denominator in the expression, ignoring it with phi over simplifies the polynomial?

----------------------------

Is the discussion on polynomial choice selection etc, worthy of discussion here??? Or should I crawl into my hole again, do it on my own etc?

[trilliwig]

Originally Posted by VJS

However phi suggested the following poly file:

skew: 1.00
c5: 1
c4: 1
c3: -4
c2: -3
c1: 3
c0: 1
y1: -215650177543
y0: 46504999074327421516850
m: 215650177543
type: snfs

Which would be a difficulty of 113 however running the script specified a difficult of 54-digits!!!. Followed by a crash creating the factor base.

Error: Bad polynomial: f(m): !=0 (mod n)
m=215650177543

Y1 and Y0 must be capitalized, and the value of m is wrong. It should be -Y0/Y1 (mod n). Since Y1 and Y0 are supplied, GGNFS can figure out the correct value of m on its own and you can leave it out.

Originally Posted by VJS

Is the discussion on polynomial choice selection etc, worthy of discussion here??? Or should I crawl into my hole again, do it on my own etc?

It should be on topic. There are already a number of posts on this forum discussing this. You just have to search for them, which I leave up to you, since I don't have the time at the moment.