Quadratic Sieve - How large should the factor base be?

[hallstei]

I am currently implementing the quadratic sieve, and was wondering how large the factor base should be.

I currently use a factor base the size of the number of bits in the number to be factored, but that doesn't seem to work too well..

[wblipp]

Originally Posted by hallstei

I am currently implementing the quadratic sieve, and was wondering.

Are you aware of the wonderful and recent quadratic sieve program Msieve? There are few good reasons to write a new QS program when this one is available. See the thread Feedback for a New MPQS Utility Sought for more information, including download links.

[ColdFury]

There are few good reasons to write a new QS program when this one is available.

Lots of people write their own implementation because its a good way to learn the nuts and bolts of the algorithm. Its one thing to read how it works, its another to work out all the details and make it work. I did a similar thing a couple years ago to help learn it.

[jasonp]

Originally Posted by hallstei

I am currently implementing the quadratic sieve, and was wondering how large the factor base should be.

I currently use a factor base the size of the number of bits in the number to be factored, but that doesn't seem to work too well..

The "best" factor base size is a function of the implementation, the size of the input, and the exact number being factored. Asymptotically you can show using a little calculus that making the largest factor base prime ~exp(0.5*log(n)*log(log(n))) is optimal, where n is being factored and log is a natural logarithm. Rigorously using this value will give you a factor base far larger than is common for QS programs.

The literature doesn't help either; one of the early 2LP QS papers recommends a FB size of ~4000 for a 90-digit factorization, where msieve uses a FB of over 60000 for numbers that size! I suppose the size of 4000 is fine if you have a cray...

Most programs just tabulate values that appear to be optimal across a wide range of emprical tests. Some programs attempt to give an overall formula and then tailor it to the number being factored; for example, the Miracl factoring utility sets the number of FB entries to (digits^4)/4096, adds some fudge, then finds that many primes given the exact value of n. The good news is that QS seems pretty forgiving of a bad choice of FB size, unless the chosen size is grossly too large or too small (yours is definitely too small, though for inputs < ~100 bits it's okay if you're using multiple polynomials).

BTW, msieve started off as a learning tool as well. There's just something about QS that made me want to optimize the dickens out of it

jasonp

[hallstei]

Originally Posted by jasonp

The "best" factor base size is a function of the implementation, the size of the input, and the exact number being factored. Asymptotically you can show using a little calculus that making the largest factor base prime ~exp(0.5*log(n)*log(log(n))) is optimal, where n is being factored and log is a natural logarithm. Rigorously using this value will give you a factor base far larger than is common for QS programs.

The literature doesn't help either; one of the early 2LP QS papers recommends a FB size of ~4000 for a 90-digit factorization, where msieve uses a FB of over 60000 for numbers that size! I suppose the size of 4000 is fine if you have a cray...

Most programs just tabulate values that appear to be optimal across a wide range of emprical tests. Some programs attempt to give an overall formula and then tailor it to the number being factored; for example, the Miracl factoring utility sets the number of FB entries to (digits^4)/4096, adds some fudge, then finds that many primes given the exact value of n. The good news is that QS seems pretty forgiving of a bad choice of FB size, unless the chosen size is grossly too large or too small (yours is definitely too small, though for inputs < ~100 bits it's okay if you're using multiple polynomials).

BTW, msieve started off as a learning tool as well. There's just something about QS that made me want to optimize the dickens out of it

jasonp

That is right, I implement this program just to learn the algorithm. Thanks for the feedback, Jason! I'm now trying bit size^2, to see how that works out.

The main obstacle for me at the moment seems to be the 'block Lanczos' algorithm which, it appears, is THE method for finding a perfect square from the relations. From what I have found on the Internet it seems extremely complex and mathematically difficult. Anyone know where I can find a good explanation of this algorithm?

Cheers,

Hallstein

[jasonp]

Originally Posted by hallstei

The main obstacle for me at the moment seems to be the 'block Lanczos' algorithm which, it appears, is THE method for finding a perfect square from the relations. From what I have found on the Internet it seems extremely complex and mathematically difficult. Anyone know where I can find a good explanation of this algorithm?

There isn't one. If you want to build a block Lanczos solver, you basically have to find someone else's code, have Montgomery's original paper in your lap, and keep debugging until both codes can find a nullspace of the same matrix.

Another possibility is Gauss elimination; with one large prime, GE can solve matrices from factorizations up to ~70 digits without much trouble. There's a huge literature on sparse GE, though most of it is not written with factoring in mind. Older versions of msieve used GE, and I can send the source for it if that will help.

jasonp