20110921, 07:45  #1 
Sep 2011
39_{16} Posts 
Finding B in Quadratic Sieve
I'm coding QS, everything else is done, except for choosing the proper smoothness bound B.
B = exp((1/2 + o(1))(log n log log n)^(1/2)) page 8, http://www.math.leidenuniv.nl/~reinier/ant/sieving.pdf I do not understand the little o notation. What do I substitute for o(1) to calculate for B? 
20110921, 12:42  #2 
Tribal Bullet
Oct 2004
3×1,163 Posts 
o(1) means 'this can't be zero, but we expect it to drop to zero much faster than all the other terms grow'. The temptation to make it zero and keep going is overwhelming.
Incidentally, in practice the asymptotic bound on the factor base size is extremely conservative; you would be better off actually forcing the bound to a given size and choosing that size to optimize the actual runtime of your program. Don't be surprised if the best B goes down as the sieving speed increases. 
20110921, 14:09  #3  
Nov 2003
2^{6}·113 Posts 
Quote:
and machine dependent. Note also that the asymptotic bound does not use the largeprime variation. It assumes that all useful relations factor entirely over the factor base. The optimal B is also dependent on the large prime bound and whether you use one or two large primes. Experiment. Do (say) 1/10% of the estimated sieving using different B's. 

20110922, 17:12  #4 
Sep 2011
3·19 Posts 
Thanks for the replies. Limiting the factor base size works great. I'm still experimenting on the size.
I'll try MPQS, then probably SIQS next. MPQS seems more complicated (than plain QS), though. Last fiddled with by paul0 on 20110922 at 17:13 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Java Quadratic Sieve  Ilya Gazman  Factoring  3  20160222 11:32 
Quadratic Sieve by Hand  Sam Kennedy  Factoring  20  20130109 16:50 
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 