mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Factoring (https://www.mersenneforum.org/forumdisplay.php?f=19)
-   -   Finding B in Quadratic Sieve (https://www.mersenneforum.org/showthread.php?t=16072)

paul0 2011-09-21 07:45

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, [url]http://www.math.leidenuniv.nl/~reinier/ant/sieving.pdf[/url]

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=jasonp;272253]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.[/QUOTE]

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.


All times are UTC. The time now is 21:33.

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