NFS

[frmky]

A quick clarifcation, read factor base _limit_ instead of FB size in the above post. Thought something seemed strange when I reread it.

[smh]

Downloaded GMP but have no idea how to configure and install.

Ahh well, shouldn't try to do things i don't know anything about.

Guess i'll have to wait for a windows implementation :-(

[rogue]

Originally Posted by smh

Downloaded GMP but have no idea how to configure and install.

Ahh well, shouldn't try to do things i don't know anything about.

Guess i'll have to wait for a windows implementation :-(

In the gmp-4.1.3 directory, run the configure script. This will build the Makefiles needed to build GMP. Once configured, run make to build the library. Let us know if that gets you any further.

[smh]

Originally Posted by rogue

In the gmp-4.1.3 directory, run the configure script. This will build the Makefiles needed to build GMP. Once configured, run make to build the library. Let us know if that gets you any further.

Hi Mark,

Easier said than done. I can't find a configure command. I tried autoconf, and that seems to do something, but no makefile appears.

Thanks for the help, but this cygwin seems to be out of my league. I'm already glad that i can get to the directories where i downloaded GMP and GGNFS.

[rogue]

I can help you step by step if you still want to try. Once you get the basics of cygwin, it shouldn't be too difficult build GMP and GGNFS. Send me an e-mail (not a private message) and I'll help.

[smh]

Originally Posted by rogue

I can help you step by step if you still want to try.

I would be interested, but for now i'm happy with the binaries FRMKY sent me.

The hard part now seems to be finding the optimal FB limit. I've already found a factor 5 difference in runtime on a C85

[rogue]

I've been trying to factor some of the smaller composites from the home prime search (a C112 and a C114), but they are notoriously difficult for this implementation of NFS. Maybe my factor base is too small, but trying to figure out the optimal parameters for NFS is not easy. Some of the examples provided use the lattice sieve and others don't. Those that do not use the lattice sieve are much slower.

[xilman]

Originally Posted by rogue

I've been trying to factor some of the smaller composites from the home prime search (a C112 and a C114), but they are notoriously difficult for this implementation of NFS. Maybe my factor base is too small, but trying to figure out the optimal parameters for NFS is not easy.

FInding reasonable sieving parameters for the NFS is actually quite easy, if you know the tricks. it is, however, mind-bogglingly tedious. That's why most people I know tend to follow the herd and use params that are the same or similar to those which have been used for factoring similarly sized integers with the same algorithm (GNFS/SNFS, lattice/line, 1LP/2LP/3LP) in the past. theory can certainl give a guide, but in real life the differences in implementations, hardware types, resources available, and so on play an extremely important role and have to be calibrated directly.

Here's the procedure. First pick a large prime bound (LPB) for each polynomial. This will set how many relations you will need to find and have a strong bearing on the size of the matrix. Set LPB very high and you will find more relations per second of sieving but you will need more of them and the matrix will be larger. A good rule of thumb is that the number of relations needed will be about 0.8 * (pi(LPB1) + pi(LPB2)) where pi(x) is the familiar prime-counting function and I'm assuming two polynomials. Only rarely are more than two used and, very frequently, one of the two will be a linear polynomial.

Next, set the factor base sizes, FB1 and FB2. These will govern very strongly the number of relations found by the sievers. Too low and you won't get enough relations (and you already know roughly how many you need) . Too high and although you get more relations, the time spent sieving will grow too much, as will the matrix size.

Then, set the size and skewness of the sieving area (lattice siever) or the line length (line siever). The bigger the area, the fewer special-q you need (lattice) and the longer the length, the fewer the number of lines (line) to be sieved.

Now comes the tedious bit. With the parameters just selected, perform some trial sieving at a low sampling density. By that, I mean sieve every Nth special-q or every Nth line, where N may be in the range 1000 - 50000 depending on how big a number you are trying to factor.

The trial sieving will tell you how many relations will be found in how many cpu-seconds for a given number of special-q or lines. Note that you may not be able to find enough relations no matter how much sieving is done if the factor bases are too small.

Then go back and alter one of the parameters. If you are using a line siever, the sieving rectangle should have a skewness (maximum a-value divided by maximum b-value, remembering that the a-values are symmetrical about zero) close to the optimum, something which is generally reported by the polynomial finder and/or root finder.

See if the new choice increases or reduces the seiving time taken to find enough relations. When you've got something reasonably close to optimum (two or three trials is usually plenty to get an idea), change one of the other params and sieve again.

Repeat the optimization steps until you are not far off the global optimum. Local minima are very rare, so it's a simple but tedious procedure..

Finally, perform the production sieving. You did pay attention to the advice about factors governing the matrix size, didn't you? It's hard to give precise guidance on how big the matrix will be, not least because the size can vary by a factor of two or more when factoring different numbers with otherwise identical sieving parameters. A big influence on the matrix size is the amount of over-sieving done. If you sieve until you have only just enough relations to complete the factorization, the matrix will be extremely large. Sieve some more and the linear algebra time drops dramatically. The improvment continues with more sieving, but rapidly tails off.


The best lesson to take away from all this is that experience helps enormously. It doesn't matter too much whether it is personal experience (though that's better) or the experience of others. If you know people who've done similar factorizations in the past, ask them for guidance. Read accounts of other factorizations of similar difficulty. There are a few papers around which contain tables of parameters. I know Bob Silverman has written one, because I've fed back comments on it to him, but I don't yet know whether it's been published.


Good luck,

Paul

[R.D. Silverman]

Originally Posted by xilman

FInding reasonable sieving parameters for the NFS is actually quite easy, if you know the tricks. it is, however, mind-bogglingly tedious.

<snip>

Paul

Nice summary. If anyone wants the paper on Optimizing the NFS parameters,
please send me private email at my Draper address.

There is a good rule of thumb for mapping from optimal SNFS to GNFS.
Hint: consider the ratio of the constants in the exponents for their
respective time complexity functions.....

If people don't understand this hint, I will give a full explanation in a few
days. I don't have time right now.

Bob

[xilman]

Originally Posted by Bob Silverman

Nice summary. If anyone wants the paper on Optimizing the NFS parameters,
please send me private email at my Draper address.

Bob

Don Leclair drew my attention to this very recent paper: http://eprint.iacr.org/2004/095.pdf

Lots of very good information there which summarizes gnfs factoring of RSA-100 through RSA-150. All factorizations were done in the same environment and so the figures are directly comparable. Most other information available was garnered from a variety of implementations, algorithms and hardware resources.

Paul