Running GGNFS

[VolMike]

Where can I download an Core2Duo optimized executable gnfs-lasieve4I11e?

[10metreh]

Originally Posted by VolMike

Where can I download an Core2Duo optimized executable gnfs-lasieve4I11e?

For 64 bit, here (SVN 374). The 32-bit version is not Core 2 optimized, but that shouldn't matter too much.

[VolMike]

Originally Posted by 10metreh

For 64 bit, here (SVN 374). The 32-bit version is not Core 2 optimized, but that shouldn't matter too much.

Thank you!

[apocalypse]

I'm trying to learn how to choose good parameters for SNFS factoring with GGNFS.

A few days ago I factored sigma(1009^58) with this .poly

n: 907561549186475406082015134100612123030527144402631698695854550635167463020222007210274477872206851522895894567531159280732905403784954272620605116\
05162904590248563
m: 1113509674956668989037907205610844481
c0: -1009
c5: 1
type: snfs
skew: 1

The SNFS difficulty was ~= 180 and it took about a day as expected.

I then tried to factor sigma(843714919^18) with this .poly

n: 231498350570359790444053914362768188442984190755971784957029458823139020464565741428114480714555150929415898114589486417394036929216614808800508179\
15566263
m: 600602569377802184166813559
c0: -1
c6: 843714919
type: snfs
skew: 0.033

which has SNFS difficulty ~= 170, has been running for 3 days, and only has half as many relations (so far) as the prior run collected in 1 day.

In both cases I used the GGNFS default parameters (running factMsieve.pl), so I'm wondering if there are some experiments I should run to choose better parameters or a better siever (The current run is using 14e and I think the prior run did too). Or perhaps this is a consequence of moving from a quintic with a small coefficient to a sextic with a larger one and I should account for that in my effort estimates.

Thanks!

[axn]

Originally Posted by apocalypse

Or perhaps this is a consequence of moving from a quintic with a small coefficient to a sextic with a larger one and I should account for that in my effort estimates

Considering the smaller m (and hence smaller rational coeffs), have you tried sieving on the algebraic side?

Also, a quintic might be better.

[apocalypse]

Originally Posted by axn

Considering the smaller m (and hence smaller rational coeffs), have you tried sieving on the algebraic side?

Also, a quintic might be better.

I haven't tried sieving on the algebraic side. It looks like I would do that by changing $LATSIEVE_SIDE in factMsieve.pl. Would this change be compatible with the relations collected so far, and would I need to make any other changes, e.g. to the job files? Or should I just wipe what I have and start over?

[henryzz]

The relations are fine but the job files need to be nuked(or edited but that is a fiddle).
I would rename the large relations file to spairs.add and delete all other files except the poly and spairs.add and let the script regenerate the job files and other misc files.
The relations in spairs.add will get added into the new relations file.
You might expect a slightly higher duplication rate but not anything significant.
Make a backup before you do anything!!

[fivemack]

NFS relation-sieving is about finding numbers which factorise nicely; and being small is about the best way to get a number to factorise nicely (half of GNFS polynomial selection is about taking advantage of other ways, the other half about efficiently finding polynomials with small values).

Let's look at how big the numbers are that you're trying to factorise:

You're using 14e, so you're working in a lattice with average lattice-coordinates something around 2^13; you're sieving with special-Q around six million, so get another sqrt(6e6) ~ 2500 factor from that. So you're evaluating the polynomial with coefficients around 10^7 (look at the (X,Y) numbers before the first colon in relation files to see if this is about right)

So the algebraic-side values that need to be smooth are about 10^51 for your sextic (since the initial coefficient is about nine digits and you're multiplying it by the sixth power of something around 10^7), and about 10^38 for the quintic (fifth power, initial coefficient about 10^3); the rational-side values are about 10^43 (36+7) for the quintic and about 10^34 (26+7) for the sextic.

(IE you should probably have sieved the quintic on the rational side; you're on the right side for the sextic but it's a bit big; using x^5-843714919^2 and rational 843714919^4 would give figures ~10^53 (18+35) for the quintic algebraic and ~10^43 (36+7) for the rational, which would be worse than the sextic)

The message here is that large coefficients in polynomials are intrinsically troublesome, sigma(12-digit prime to a small power) is intrinsically harder by NFS than sigma(small prime to a larger power)

[henryzz]

Originally Posted by fivemack

NFS relation-sieving is about finding numbers which factorise nicely; and being small is about the best way to get a number to factorise nicely (half of GNFS polynomial selection is about taking advantage of other ways, the other half about efficiently finding polynomials with small values).

Let's look at how big the numbers are that you're trying to factorise:

You're using 14e, so you're working in a lattice with average lattice-coordinates something around 2^13; you're sieving with special-Q around six million, so get another sqrt(6e6) ~ 2500 factor from that. So you're evaluating the polynomial with coefficients around 10^7 (look at the (X,Y) numbers before the first colon in relation files to see if this is about right)

So the algebraic-side values that need to be smooth are about 10^51 for your sextic (since the initial coefficient is about nine digits and you're multiplying it by the sixth power of something around 10^7), and about 10^38 for the quintic (fifth power, initial coefficient about 10^3); the rational-side values are about 10^43 (36+7) for the quintic and about 10^34 (26+7) for the sextic.

(IE you should probably have sieved the quintic on the rational side; you're on the right side for the sextic but it's a bit big; using x^5-843714919^2 and rational 843714919^4 would give figures ~10^53 (18+35) for the quintic algebraic and ~10^43 (36+7) for the rational, which would be worse than the sextic)

The message here is that large coefficients in polynomials are intrinsically troublesome, sigma(12-digit prime to a small power) is intrinsically harder by NFS than sigma(small prime to a larger power)

I had a suspision that something like that might be going on. That changing side might not help.
Is there a program which will do these calculations for you? It would maybe be nice to include it in factmsieve.py.

[axn]

Originally Posted by fivemack

(IE you should probably have sieved the quintic on the rational side; you're on the right side for the sextic but it's a bit big; using x^5-843714919^2 and rational 843714919^4 would give figures ~10^53 (18+35) for the quintic algebraic and ~10^43 (36+7) for the rational, which would be worse than the sextic)

Ummm... Didn't he sieve the quintic on the rational side? AFAIK, type SNFS does that. Am I understanding this whole thing upside down?

Also, x^5-843714919 is the correct one.

[apocalypse]

Please forgive me if I'm being obtuse, but I don't follow why evaluating f(x) = x^5 - 1009 at x ~= 10^7 gives values around 10^38 instead of 10^35, and likewise why g(x) = x - (~=10^36) gives values around 10^43 instead of 10^36.

Ah, yes. When doing GNFS, everything's working with homogeneous polynomials but that's rarely written out clearly: we write x^5-1009, but we mean f(x,y)=x^5-1009*y^5, and are evaluating it for x and y both around 10^7. Similarly, the rational side is g(x,y) = x - 10^36ish*y, so its values will be around 10^7-ish - 10^36ish * 10^7ish = 10^43ish

Both the quintic and the sextic were sieved on the rational side (ggnfs default)

Oh, OK, I hadn't realised ggnfs did that; I've always called the sievers directly for SNFS jobs. I'm glad that it's got appreciably faster when you switch to the appropriate side.