GNFS parameter selection pearls of wisdom

[henryzz]

I have noticed that fivemack sometimes posts really helpful "pearls of wisdom" about GNFS polynomial selection. I am going to collect them in this thread.

Originally Posted by fivemack

Generally I've found that an optimal parameterisation gets about two relations per Q on average. If getting 4.5 relations per Q, I would usually be tempted to use a smaller siever or a smaller large prime bound.

Originally Posted by fivemack

General rule for siever choice: if you get less than 2000 relations from a range of 1000 Q, use a bigger siever; if you get more than 6000 use a smaller siever.

General rule for relation counting: 0.1 * 2 ^ large prime bound

Originally Posted by fivemack

A rule of thumb which seems reasonable at least up to 140 digits is to pick the small-prime bound such that you can expect to get all your relations by sieving from spb/2 up to spb; small Q are at least slightly higher-yielding than large Q.

If there are any I have missed(I am sure there are), please post them in this thread.

[Andi_HB]

I think this example is right in here.

Originally Posted by fivemack
That's eight experiments (13e vs 14e, 16777215 vs 33554431, lpb=28 vs 29); sieve the same range, presumably 2^25 .. 2^25+1000, for each of them and see what works better.

From Andi47
I calculated a "28-score" to compare the "lp29" results with the "lp28" ones; just yield/2 and sec/rel*2.

example
same siever with lpb 28 and lpb 29 !

d3: rlim = alim = 2^24-1, lp 29, 13e <------------------------ lp 29
total yield: 2603, q=16779001 (0.04205 sec/rel)
"28-score": 1301.5 / 0.08410 <-- calculation to compare lp29 & 28

c3: rlim = alim = 2^24-1, lp 28, 13e <------------------------ lp 28
total yield: 1306, q=16779001 (0.08176 sec/rel) <---- faster


And some examples for GNFS-Numbers and needed Relations (including duplicates)
N= C101, special Q range size = 500000 , number of relations =4434371
N= C102, special Q range size = 550000 , number of relations =4779022
N= C102, special Q range size = 600000 , number of relations =3981204
N= C104, special Q range size = 700000 , number of relations =4403292
N= C109, special Q range size = 1250000 , number of relations=5342536
N= C110, special Q range size = 1300000 , number of relations=5661426
N= C111, special Q range size = 1450000 , number of relations=8236448
N= C117, special Q range size = 1400000 , number of relations=9055892
N= C120, special Q range size = 2100000 , number of relations=8818929
N= C122, special Q range size = 2900000 , number of relations=8680732
N= C123, special Q range size = 3400000 , number of relations=8851963
N= C124, special Q range size = 4000000 , number of relations=9178490
N= C125, special Q range size = 4800000 , number of relations=9245826
N= C133, special Q range size = 10500000 , number of relations=16830320
N= C134, special Q range size = 13500000 , number of relations=17620569

[henryzz]

click quote in the original thread to get the quote things set up properly

[FactorEyes]

This jibes quite well with what I know from my less-experienced perspective. In particular, the cutoff for 15e is so close to 240 digits SNFS that it's scary. 15e may look slower, but there tends to be a lower rate of duplication of relations. My experience here consists of all of 5 numbers -- someone should chime in and correct me if I'm mistaken about this.

6th-degree SNFS polynomials are worth trying under SNFS 200, even down as far as SNFS 190 or so, if the 5th-degree has bigger coefficients.

I have never understood how to compute the number of roots in the lying-over ideal on the algebraic side, which seems to be good knowledge to have, but my reading of the NFS literature was pretty cursory.

Originally Posted by fivemack

I don't have a def-par.txt file, nor do I use the ggnfs scripts for large numbers. I have a couple of perl scripts, but they tend to have comments like 'now put the polynomial into count.gp and copy the results into this array'; not very fire-and-forget.

I start by picking the large-prime bound: I then try various small-prime bounds, and one or two sievers, and do test sieving over small ranges, estimate from those how long the job would take to get enough relations given the large-prime bound, and pick the small-prime bound and siever that gives the quickest runtime. I don't think you can avoid doing something at least that fiddly if you're working outside the bounds of experience.

A rule of thumb which seems reasonable at least up to 140 digits is to pick the small-prime bound such that you can expect to get all your relations by sieving from spb/2 up to spb; small Q are at least slightly higher-yielding than large Q.

However, I'll post a few example points - I've tended to do individual very-large jobs, I don't have a statistically significant collection of jobs above 130 digits.

GNFS 120-130 digits: 27-bit large primes, siever 13e, small primes 6000000 works quite well for me towards the top end of the range, small primes 4000000 works OK towards the lower end.

GNFS, 138 digits: probably 28-bit large primes, 13e and 14e pretty comparable, small prime 10 million works for me

By 150 digits you'll want 29-bit large primes and siever 14e, small prime bound 20 million seems reasonable. Don't change over too early; 28-bit LP was faster than 29-bit LP at the 144-digit point.

I'm currently doing a 159-digit GNFS with 29-bit large primes and siever 15e, small prime bound 50 million.

SNFS

difficulty 180-ish: 28-bit large primes are better than 27-bit; siever 13e; small prime bound around 10 million

crossover 28-29 is somewhere around 200; 30 is too big at difficulty 200.

SNFS 210-240: 30-bit large primes, siever 14e, small prime bound somewhere around 30 million

SNFS 240-270: 31-bit large primes, siever 15e, small prime bound around 100 million for larger numbers

Not much above SNFS 270, you'll want to switch to siever 16e; but the current version of this horribly over-estimates the memory usage (wants ~3.5G per process), and fixing that will be a serious development effort.

[fivemack]

how to compute the number of roots in the lying-over ideal on the algebraic side

In pari, do

length(polrootsmod(polynomial, prime))

There's some quite complicated mechanics behind there - you're factoring the polynomial over GF(p), but this is easy because polynomial GCDs are no harder than normal GCDs and we know that the product (x-i) for i a quadratic residue is g(x)=x^{(p-1)/2}-1, so GCD(f(x),g(x)) is the product of the roots that happen to be quadratic residues, GCD(f(x+1),g(x)) the product of the roots that happen to be one more than quadratic residues ... and carrying on like that ends up splitting the polynomial, though you can also be clever.

[R.D. Silverman]

Originally Posted by FactorEyes

This jibes quite well with what I know from my less-experienced perspective. In particular, the cutoff for 15e is so close to 240 digits SNFS that it's scary. 15e may look slower, but there tends to be a lower rate of duplication of relations. My experience here consists of all of 5 numbers -- someone should chime in and correct me if I'm mistaken about this.

6th-degree SNFS polynomials are worth trying under SNFS 200, even down as far as SNFS 190 or so, if the 5th-degree has bigger coefficients.

I have never understood how to compute the number of roots in the lying-over ideal on the algebraic side, which seems to be good knowledge to have, but my reading of the NFS literature was pretty cursory.

I do not use these sievers. Please reduce my ignorance. What distinguishes
the 13e, 14e, 15e etc. sievers? Is it just the size of the sieve region?

To (partially) answer the question about the number of roots: The way a
prime splits in the field is strongly dependent on the Galois Group. You
need to start by computing it. If, for example, the Galois Group is cyclic,
then every unramified prime that splits will do so completely.

[fivemack]

The 13e / 14e / 15e sievers indeed differ only in the size of the sieve region; I believe that for 15e it's -2^14 to 2^14 in X and 0 to 2^14 in Y, and smaller for smaller e.

Actually computing the Galois group for a general polynomial is a sophisticated task; well beyond the scope of the first undergrad Galois theory course. It's not computationally terribly hard, and the Magma team have implemented it, so the easiest way to get the Galois group for a polynomial is to go to http://magma.maths.usyd.edu.au/calc/ and put

P<x>:=PolynomialRing(Rationals());
GaloisGroup(2*x^6-1);

into the top box; it'll tell you the order of the group and the generators.

Almost all polynomials of degree D have Galois group S_D, the largest possible; however SNFS polynomials tend not to fall into that 'almost all'.

If you just want to count ideals rather than to do analytic estimates about them, pari will do the polynomial factorisations and hence count the ideals in about fifty microseconds for a prime around 10^8; over long ranges, the number of ideals is in my experience very close to the number of rational primes, but if you're doing at-all-careful estimation work it is worth counting the ideals in the intervals you try sieving over rather than assuming that a yield measured over Q .. Q+1000 is necessarily anywhere near to 10^-4 of the yield from Q .. Q+10^7.

[R.D. Silverman]

Originally Posted by fivemack

<snip>

, the number of ideals is in my experience very close to the number of rational primes.

This follows directly from the Chebotarev Density Theorem.

[Andi_HB]

From Batalov
The approximately needet Relations with different lpbr and lpba

minimums appear to be:
46M for 29/29
92M for 30/30
18xM for 31/31

[bsquared]

I re-read this recently, and thought it was in the spirit of this thread (collecting useful tidbits related to NFS factoring for future reference):

http://www.mersenneforum.org/showthread.php?t=12008

[Batalov]

...