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

262418 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

26×37 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

216 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 01:03.


Mon Aug 15 01:03:01 UTC 2022 up 38 days, 19:50, 2 users, load averages: 0.81, 1.02, 1.05

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

โ‰  ยฑ โˆ“ รท ร— ยท โˆ’ โˆš โ€ฐ โŠ— โŠ• โŠ– โŠ˜ โŠ™ โ‰ค โ‰ฅ โ‰ฆ โ‰ง โ‰จ โ‰ฉ โ‰บ โ‰ป โ‰ผ โ‰ฝ โŠ โŠ โŠ‘ โŠ’ ยฒ ยณ ยฐ
โˆ  โˆŸ ยฐ โ‰… ~ โ€– โŸ‚ โซ›
โ‰ก โ‰œ โ‰ˆ โˆ โˆž โ‰ช โ‰ซ โŒŠโŒ‹ โŒˆโŒ‰ โˆ˜ โˆ โˆ โˆ‘ โˆง โˆจ โˆฉ โˆช โจ€ โŠ• โŠ— ๐–• ๐–– ๐–— โŠฒ โŠณ
โˆ… โˆ– โˆ โ†ฆ โ†ฃ โˆฉ โˆช โŠ† โŠ‚ โŠ„ โŠŠ โŠ‡ โŠƒ โŠ… โŠ‹ โŠ– โˆˆ โˆ‰ โˆ‹ โˆŒ โ„• โ„ค โ„š โ„ โ„‚ โ„ต โ„ถ โ„ท โ„ธ ๐“Ÿ
ยฌ โˆจ โˆง โŠ• โ†’ โ† โ‡’ โ‡ โ‡” โˆ€ โˆƒ โˆ„ โˆด โˆต โŠค โŠฅ โŠข โŠจ โซค โŠฃ โ€ฆ โ‹ฏ โ‹ฎ โ‹ฐ โ‹ฑ
โˆซ โˆฌ โˆญ โˆฎ โˆฏ โˆฐ โˆ‡ โˆ† ฮด โˆ‚ โ„ฑ โ„’ โ„“
๐›ข๐›ผ ๐›ฃ๐›ฝ ๐›ค๐›พ ๐›ฅ๐›ฟ ๐›ฆ๐œ€๐œ– ๐›ง๐œ ๐›จ๐œ‚ ๐›ฉ๐œƒ๐œ— ๐›ช๐œ„ ๐›ซ๐œ… ๐›ฌ๐œ† ๐›ญ๐œ‡ ๐›ฎ๐œˆ ๐›ฏ๐œ‰ ๐›ฐ๐œŠ ๐›ฑ๐œ‹ ๐›ฒ๐œŒ ๐›ด๐œŽ๐œ ๐›ต๐œ ๐›ถ๐œ ๐›ท๐œ™๐œ‘ ๐›ธ๐œ’ ๐›น๐œ“ ๐›บ๐œ”