mersenneforum.org - View Single Post - Advantage of lattice sieve over line sieve

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.

I need help.

2013-04-13, 16:32	#4
binu Apr 2013 2 Posts	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. I need help.