Finding B in Quadratic Sieve

paul0 · 2011-09-21, 07:45

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?

jasonp · 2011-09-21, 12:42

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.

R.D. Silverman · 2011-09-21, 14:09

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.

paul0 · 2011-09-22, 17:12

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.

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-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
Java Quadratic Sieve	Ilya Gazman	Factoring	3	2016-02-22 11:32
Quadratic Sieve by Hand	Sam Kennedy	Factoring	20	2013-01-09 16:50
Possible improvement of quadratic sieve	Random Poster	Factoring	4	2010-02-12 03:09
Factoring in the Quadratic Sieve	ThiloHarich	Factoring	47	2007-01-08 14:12
Quadratic Sieve in wikipedia.de	ThiloHarich	Factoring	5	2006-07-14 09:51

2011-09-21, 12:42	#2
jasonp Tribal Bullet Oct 2004 5×709 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.