20050417, 19:10  #1 
Apr 2005
13_{10} 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.. 
20050417, 21:06  #2  
"William"
May 2003
Near Grandkid
2×1,187 Posts 
Quote:


20050418, 01:02  #3  
Aug 2002
2^{6}×5 Posts 
Quote:


20050418, 01:42  #4  
Tribal Bullet
Oct 2004
3^{2}·5·79 Posts 
Quote:
The literature doesn't help either; one of the early 2LP QS papers recommends a FB size of ~4000 for a 90digit 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 

20050419, 08:57  #5  
Apr 2005
13 Posts 
Quote:
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 

20050419, 11:58  #6  
Tribal Bullet
Oct 2004
3^{2}×5×79 Posts 
Quote:
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 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
primitive roots when the base is a quadratic algebraic integer  devarajkandadai  Number Theory Discussion Group  0  20180208 05:15 
Finding B in Quadratic Sieve  paul0  Factoring  3  20110922 17:12 
Possible improvement of quadratic sieve  Random Poster  Factoring  4  20100212 03:09 
Factoring in the Quadratic Sieve  ThiloHarich  Factoring  47  20070108 14:12 
Quadratic Sieve in wikipedia.de  ThiloHarich  Factoring  5  20060714 09:51 