mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Factoring (https://www.mersenneforum.org/forumdisplay.php?f=19)
-   -   Advantage of lattice sieve over line sieve (https://www.mersenneforum.org/showthread.php?t=18086)

binu 2013-04-13 13:37

Advantage of lattice sieve over line sieve
 
In line sieve, we sieve for a particular small prime p for only once; and in lattice sieve, we sieve for that p for every special-q (p<q and number of special-q's may be very large). So, what is the gain in the latter one? Definitely, I am missing something. Can anyone please elaborate the gains/advantage of lattice sieve in details, and also on the choice of the parameters C and D.

Thanks in advance.

xilman 2013-04-13 14:18

[QUOTE=binu;336946]In line sieve, we sieve for a particular small prime p for only once; and in lattice sieve, we sieve for that p for every special-q (p<q and number of special-q's may be very large). So, what is the gain in the latter one? Definitely, I am missing something. Can anyone please elaborate the gains/advantage of lattice sieve in details, and also on the choice of the parameters C and D.

Thanks in advance.[/QUOTE]If you know in advance that a value is divisible by the prime special-q the number is more likely to be smooth.

chris2be8 2013-04-13 16:05

There's a discussion at [URL]http://mersenneforum.org/showthread.php?t=2524[/URL]

Chris

binu 2013-04-13 16:32

Thanks. But I am implementing the lattice sieve proposed by J. M. Pollard, where special-q's are taken as medium primes (B_0<q<B_1; B_1 being the bound on the factor base primes and B_0 varies between 0.1-0.5 fraction of B_1). Then we sieve for EVERY q in that range. Instead if we line sieve for all primes <B_1 (where every prime is used only once) and then report the smooth candidates, won't it consume less time? It is not clear to me. :sad: I need help.


All times are UTC. The time now is 02:50.

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