20151116, 14:53  #1 
Sep 2011
3·19 Posts 
Sieving both sides vs one side at a time
My line siever currently sieves N(a+bθ)*(a+bm), which is the algebraic side and the rational side at the same time. However, it looks like most papers point to sieving the two sides separately. What is the advantage of this? Won't this need extra work, like matching (a,b)pair of both sides, since both sides need to be smooth?

20151116, 15:21  #2 
(loop (#_fork))
Feb 2006
Cambridge, England
2^{4}·3·7·19 Posts 
Are the papers you're looking at specifically referring to the line siever? With lattice sieving you are definitely working on one side or the other.
Also, multiplying the two sides together is going to make largeprime variants more difficult  you'd be factoring larger numbers and looking for rarer events, and you're not able to take so much advantage of the nice filter 'if the residue is < p_max^2, it must be prime and therefore it's likely to be too large a prime. 
20151116, 15:24  #3 
Sep 2011
57_{10} Posts 
So there is an implicit "match the smooth pairs from both sides" step?

20151116, 16:06  #4  
Nov 2003
1D24_{16} Posts 
Quote:
Initialize the sieve array. You sieve one side and identify which lattice points might be smooth. Reinitialize by setting the values of those locations that can't be smooth to oo, then sieve the other side. You then identify which points might be smooth on the second side. Finally, one attempts to factor those candidates that might be smooth on both sides. (i.e. the intersection of the sublattices with just smooth points) Note also that doing one side at a time reduces memory and makes bucket sieving a lot easier. Note also that sieving both sides at the same time will increase paging, because the cache can't hold even one factor base, let alone two, so you will spend a lot of extra time pulling in both factors bases during sieving (as opposed to one at a time). Give us some data. How long do you take to process a single specialq? Specify the size of your factor base and the size of the sieve region. We can then let you know whether your siever competes with others in terms of performance. The time it spends should be directly proportional to the size of the sieve array times loglog(pmax) where pmax is the largest prime in the factor base. The constant will change according to the speed of your processor, size of cache, size of memory and whether you have one, two, or three LP on each side, as well as the cleverness of your code. Last fiddled with by R.D. Silverman on 20151116 at 16:13 

20151116, 16:11  #5 
Sep 2011
3·19 Posts 

20151118, 13:58  #6 
Sep 2011
111001_{2} Posts 
I like to point out that for now, my NFS implementation is a learning (toy) experiment. It won't be made to compete.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Sieving and LLRin in same time  pepi37  Software  1  20170515 17:17 
mfaktc and CUDALucas sidebyside  TObject  GPU Computing  2  20120721 01:56 
Thanks PG for Sieving, now time to pick a new n?  cipher  Twin Prime Search  25  20090809 19:32 
Optimal Sieving Time  jasong  Sierpinski/Riesel Base 5  10  20090125 15:56 
prime density vs. sieving vs. prp time  jasong  Math  18  20060331 03:14 