mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2013-04-13, 13:37   #1
binu
 
Apr 2013

216 Posts
Post 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.
binu is offline   Reply With Quote
Old 2013-04-13, 14:18   #2
xilman
Bamboozled!
 
xilman's Avatar
 
May 2003
Down not across

100110011100002 Posts
Default

Quote:
Originally Posted by binu View Post
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.
If you know in advance that a value is divisible by the prime special-q the number is more likely to be smooth.
xilman is offline   Reply With Quote
Old 2013-04-13, 16:05   #3
chris2be8
 
chris2be8's Avatar
 
Sep 2009

1,753 Posts
Default

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

Chris
chris2be8 is offline   Reply With Quote
Old 2013-04-13, 16:32   #4
binu
 
Apr 2013

210 Posts
Default

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.
binu is offline   Reply With Quote
Reply

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 2018-03-12 22:43
SIEVE GAP pepi37 Other Mathematical Topics 2 2016-03-19 06:55
Line sieving vs. lattice sieving JHansen NFSNET Discussion 9 2010-06-09 19:25
46k sieve, max. n = 5M Cruelty Riesel Prime Search 11 2010-03-10 22:15
Which sieve to use for n^n-1? Siemelink Factoring 11 2006-11-08 18:08

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

Wed Apr 1 17:33:58 UTC 2020 up 7 days, 15:07, 1 user, load averages: 2.46, 2.09, 2.07

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

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.