mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2011-09-21, 07:45   #1
paul0
 
Sep 2011

628 Posts
Default 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?
paul0 is offline   Reply With Quote
Old 2011-09-21, 12:42   #2
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3,529 Posts
Default

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.
jasonp is offline   Reply With Quote
Old 2011-09-21, 14:09   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by jasonp View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2011-09-22, 17:12   #4
paul0
 
Sep 2011

2×52 Posts
Default

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
paul0 is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 19:17.

Sat Sep 19 19:17:47 UTC 2020 up 9 days, 16:28, 1 user, load averages: 1.34, 1.49, 1.46

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.