20130413, 13:37  #1 
Apr 2013
2 Posts 
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 specialq (p<q and number of specialq'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. 
20130413, 14:18  #2  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
2900_{16} Posts 
Quote:


20130413, 16:05  #3 
Sep 2009
1,973 Posts 

20130413, 16:32  #4 
Apr 2013
2_{8} Posts 
Thanks. But I am implementing the lattice sieve proposed by J. M. Pollard, where specialq'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.10.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.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
More NFS@Home 16e Lattice Sieve V5 wu's needed  pinhodecarlos  NFS@Home  46  20180312 22:43 
SIEVE GAP  pepi37  Other Mathematical Topics  2  20160319 06:55 
Line sieving vs. lattice sieving  JHansen  NFSNET Discussion  9  20100609 19:25 
46k sieve, max. n = 5M  Cruelty  Riesel Prime Search  11  20100310 22:15 
Which sieve to use for n^n1?  Siemelink  Factoring  11  20061108 18:08 