mersenneforum.org Finding B in Quadratic Sieve
 Register FAQ Search Today's Posts Mark Forums Read

 2011-09-21, 07:45 #1 paul0   Sep 2011 3×19 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?
 2011-09-21, 12:42 #2 jasonp Tribal Bullet     Oct 2004 67318 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.
2011-09-21, 14:09   #3
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22×5×373 Posts

Quote:
 Originally Posted by jasonp 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.
It is (as implied but not stated by your answer) also implementation
and machine dependent. Note also that the asymptotic bound does
not use the large-prime 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.

 2011-09-22, 17:12 #4 paul0   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 2011-09-22 at 17:13

 Similar Threads Thread Thread Starter Forum Replies Last Post Ilya Gazman Factoring 3 2016-02-22 11:32 Sam Kennedy Factoring 20 2013-01-09 16:50 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 20:38.

Tue Jun 28 20:38:05 UTC 2022 up 75 days, 18:39, 2 users, load averages: 1.08, 1.27, 1.28