mersenneforum.org Quadratic Sieve - How large should the factor base be?
 Register FAQ Search Today's Posts Mark Forums Read

 2005-04-17, 19:10 #1 hallstei     Apr 2005 1310 Posts Quadratic Sieve - How large should the factor base be? 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..
2005-04-17, 21:06   #2
wblipp

"William"
May 2003
Near Grandkid

2×1,187 Posts

Quote:
 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.

2005-04-18, 01:02   #3
ColdFury

Aug 2002

26×5 Posts

Quote:
 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.

2005-04-18, 01:42   #4
jasonp
Tribal Bullet

Oct 2004

32·5·79 Posts

Quote:
 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

2005-04-19, 08:57   #5
hallstei

Apr 2005

13 Posts

Quote:
 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

2005-04-19, 11:58   #6
jasonp
Tribal Bullet

Oct 2004

32×5×79 Posts

Quote:
 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

 Similar Threads Thread Thread Starter Forum Replies Last Post devarajkandadai Number Theory Discussion Group 0 2018-02-08 05:15 paul0 Factoring 3 2011-09-22 17:12 Random Poster Factoring 4 2010-02-12 03:09 ThiloHarich Factoring 47 2007-01-08 14:12 ThiloHarich Factoring 5 2006-07-14 09:51

All times are UTC. The time now is 05:16.

Tue Feb 7 05:16:11 UTC 2023 up 173 days, 2:44, 1 user, load averages: 1.68, 1.81, 1.48