Msieve with GNFS support

Version 1.12 is still limited to 125 digits, I understand that you want to increase to 155. This will be done in the next release, or that I do not do so?

[smh]

Originally Posted by jasonp

Now available.

I started my first NFS factorization with msieve last night. Can i just upgrade in the middle of sieving, or better wait till this one completes?

BTW, it's only a c102, so dont get to exited ;-)
I haven't checked, but it seems quite a bit slower than GGNFS, and probably slower than using the QS in miseve.

[jasonp]

Originally Posted by smh

I started my first NFS factorization with msieve last night. Can i just upgrade in the middle of sieving, or better wait till this one completes?

BTW, it's only a c102, so dont get to exited ;-)
I haven't checked, but it seems quite a bit slower than GGNFS, and probably slower than using the QS in miseve.

It should be safe to upgrade. And yes, without the NFS code being much more sophisticated the crossover point between QS and NFS will be above 110 digits.

[BotXXX]

First of all, jasonp thanks for all the good work on msieve. It is one briljant piece of software. Very easy to use and to setup.

And just as a test i started a few days ago with msieve 1.13 and the original RSA-100 number. In the days between i upgraded to msieve 1.14 and somewhere this weekend the machine finished with finding the two factors.

For anyone interested, please have a look at the attached log file. Machine was a Pentium 4 3Ghz with 512 MB RAM and running a heavy WinXP with daily usage.

[smh]

Thats 11 to 12 days for a c100.

I started a c102 around the same time, but canceled the run this morning.
After sieving a bit over 600000 lines i had about 4.09M relations. (all data still available).

I did ~10 minutes of polynomial search using GGNFS and restarted msieve with that polynomial.

Results look much more promising.
After 72 minutes: b = 1804, found 737262 relations

I'll post results if the factorization completes.

[jasonp]

Originally Posted by BotXXX

First of all, jasonp thanks for all the good work on msieve. It is one briljant piece of software. Very easy to use and to setup.

You're welcome, and congrats on the completed factorization. According to the logs, things took longer than they had to because the polynomial found was not very good, and the filtering wanted too many excess relations. I'll have to revisit both of those in the near future.

You should also use version 1.15 now, it has many fixes to the linear algebra and square root. In fact, if you still have the intermediate results it would be nice to restart the factorization using msieve 1.15

jasonp

[jasonp]

Originally Posted by smh

Thats 11 to 12 days for a c100.

I started a c102 around the same time, but canceled the run this morning.
After sieving a bit over 600000 lines i had about 4.09M relations. (all data still available).

I did ~10 minutes of polynomial search using GGNFS and restarted msieve with that polynomial.

Results look much more promising.
After 72 minutes: b = 1804, found 737262 relations

This is a nice experiment; I suspect the relation rate will decrease over time faster than with a non-skewed polynomial, but with enough skew in the GGNFS poly you can hopefully find the relations you need before that happens.

jasonp

[smh]

Originally Posted by jasonp

This is a nice experiment; I suspect the relation rate will decrease over time faster than with a non-skewed polynomial, but with enough skew in the GGNFS poly you can hopefully find the relations you need before that happens.

jasonp

I gave up on this number with msieve GNFS after 4 days. Finding relations slowed down to a crawl.

I might give it a try with a beter poly, but will probably try a bit smaller number.

For now, i factor the number with GGNFS in a couple of hours.

I hope you'll be able to get big improvements.

[jasonp]

Originally Posted by smh

I gave up on this number with msieve GNFS after 4 days. Finding relations slowed down to a crawl.

I might give it a try with a beter poly, but will probably try a bit smaller number.

For now, i factor the number with GGNFS in a couple of hours.

I hope you'll be able to get big improvements.

Big improvements are likely. Using a GGNFS polynomial really means you have to finish all of the sieving in the first few thousand lines, and the current code uses hardwired limits that don't let that happen.

jasonp

[smh]

Originally Posted by jasonp

Using a GGNFS polynomial .......

Is a GGNFS polynomial different than the one found with msieve?

[jasonp]

Originally Posted by smh

Is a GGNFS polynomial different than the one found with msieve?

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