Msieve with GNFS support

[R.D. Silverman]

Originally Posted by jasonp

Right now, yes. The objective is always to choose a polynomial that takes many small values, since these are more likely to yield relations during sieving.

msieve currently chooses polynomials where all the coefficients have about the same (small) size. This makes the selection process pretty simple, but means you have to do the sieving over many different b values to get enough (a,b) relations. These are 'non-skewed' polynomials.

The problem with non-skewed polynomials is that there are not very many good ones, and once you find one there isn't much you can do to make it better (without making the coefficients too big). Professional-level NFS implementations instead find 'skewed' polynomials. In these, some coefficients are much smaller than normal and some are a little bigger than normal. Making some coefficients large means that you can attempt to optimize any polynomials you find, since the larger coefficients give you a little maneuvering room.

They're called skewed polynomials because in order to keep the size of polynomial values small, we need to choose the shape of the sieving region so that the large polynomial coefficients don't matter as much. That means sieving over fewer 'b' values and more 'a' values; the best ratio to choose depends on the polynomial. For example, the polynomial used for RSA-512 in 1999 had a skewing factor of almost 11000, meaning that the range of 'a' values has to be about 11000 times the size of the range of 'b' values. Across such a skewed region, the polynomial will take on many small values. However, if you try too many 'b' values (i.e. too many sieve lines), you leave the region where the polynomial is small, and the relation output will drop, like you saw. In fact, it drops very quickly, since GGNFS chooses polynomials that are very highly skewed, and the GGNFS lattice siever is optimized for very large 'a' values.

When dealing with skewed polynomials, you need a few extremely long sieve lines, instead of many normal-size lines. Unfortunately the siever in msieve uses the latter, when it should be using the former. I plan on making modifications that will detect how long each line should be so that relation output is maximized.

All this is explained in several papers listed in the msieve readme.

jasonp

Please note that the leading edge implementations are lattice sievers,
rather than line sievers. The notion of 'skewness' is not as important.

[michaf]

Out of curiosity,

do you already have some benchmarks available of msieve vs. GGNFS right now?
(As in, is the NFS-implementation in a finished-enough state to even try it?)

[jasonp]

Originally Posted by michaf

Out of curiosity,

do you already have some benchmarks available of msieve vs. GGNFS right now?
(As in, is the NFS-implementation in a finished-enough state to even try it?)

At the 100-some-odd digit size for which tests have actually been run, GGNFS is 10x faster than msieve's GNFS implementation. 2x of that is from choosing better polynomials, and probably the other 5x is from use of a lattice siever. GGNFS also has much more cache-friendly lanczos routines, but that's a third-order effect right now.

Bottom line is that it's too early, I estimate a year of spare-time work is needed before msieve gets competitive.

Moderator(s): Could this and the previous post be moved to the 'msieve with GNFS support' thread?

jasonp

[michaf]

My apologies for not seeing the right thread until now

But good to see things going! I'll be very impressed IF msieve will get competitive! (Actually, I'm impressed already, but that might be because all this math and programming is way out of my league)

Keep up the good work!

[FactorEyes]

Originally Posted by jasonp

My limited experience here is that msieve uses much less memory (~6x less) to construct the matrix, and the resulting matrix is somewhat larger but much lighter than GGNFS run on the same set of relations.

Now that you have my attention...

As a veteran of nearly a dozen ass-whoopings during the GGNFS post-sieve phase, mainly during matrix building and trimming, I'll be trying this out. I have a C134 in the post-sieve ultra-slow matbuild-tpie stage. Will try your routines on it.

[jasonp]

Note to everyone: the current release had skewed polynomial selection code turned on by mistake. I fixed that and updated the tarball and binary on the web page. (The version number hasn't changed, so download again if necessary).

Originally Posted by FactorEyes

Now that you have my attention...

As a veteran of nearly a dozen ass-whoopings during the GGNFS post-sieve phase, mainly during matrix building and trimming, I'll be trying this out. I have a C134 in the post-sieve ultra-slow matbuild-tpie stage. Will try your routines on it.

PM me when it fails :)

jasonp

[Andi47]

I have started a c120 with msieve's NFS. It has found approx. 35k of 7M needed relations in 4:15 hours on a Core 2 Duo @ 2 GHz, which means that sieving would last at least 35 days.

(after 4:26 hours: b=5209, found 36675 relations, need 7171675)

I don't think that I will run this one until the end.

[smh]

Originally Posted by Andi47

I have started a c120 with msieve's NFS. It has found approx. 35k of 7M needed relations in 4:15 hours on a Core 2 Duo @ 2 GHz, which means that sieving would last at least 35 days.

(after 4:26 hours: b=5209, found 36675 relations, need 7171675)

I don't think that I will run this one until the end.

No, Unfortunately it won't.

I can't remember exact details, but i once started a c102 (with GGNFS poly). After 1/2 hour i was hopeful the factorization could finish in 6 hours or so.

After 3 or 4 days i gave up.

I'm confident though that there will be a time when msieve is faster than GGNFS.

[jasonp]

Originally Posted by smh

I'm confident though that there will be a time when msieve is faster than GGNFS.

Thanks for the wishes :) Andi47, the 7M figure is just the number of relations before filtering is attempted for the first time. Your factorization would probably need 10-12 million relations before filtering succeeded.

jasonp

[Andi47]

Originally Posted by jasonp

Thanks for the wishes :) Andi47, the 7M figure is just the number of relations before filtering is attempted for the first time. Your factorization would probably need 10-12 million relations before filtering succeeded.

jasonp

Looks like the crossover between msieve's GNFS and SIQS is currently way beyond 120 digits - if I propably need 10-12 M relations, it would take 50 to 60 days to GNFS a c120...

The second CPU of my Core 2 Duo is currently SIQS'ing a c121 with msieve. I will post here when it is finished.

[BWetter246]

I was wondering if the next version will be GSL free?

brandon