- **Factoring**
(*https://www.mersenneforum.org/forumdisplay.php?f=19*)

- - **Finding B in Quadratic Sieve**
(*https://www.mersenneforum.org/showthread.php?t=16072*)

Finding B in Quadratic SieveI'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? |

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=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. |

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.