mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2015-11-16, 14:53   #1
paul0
 
Sep 2011

3×19 Posts
Default 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?
paul0 is offline   Reply With Quote
Old 2015-11-16, 15:21   #2
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

18F016 Posts
Default

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 large-prime 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.
fivemack is offline   Reply With Quote
Old 2015-11-16, 15:24   #3
paul0
 
Sep 2011

3·19 Posts
Default

So there is an implicit "match the smooth pairs from both sides" step?
paul0 is offline   Reply With Quote
Old 2015-11-16, 16:06   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by paul0 View Post
So there is an implicit "match the smooth pairs from both sides" step?
I don't know what you mean by "match the smooth pairs".

Initialize the sieve array. You sieve one side and identify which lattice points might be smooth.
Re-initialize 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 sub-lattices 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 special-q? 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 2015-11-16 at 16:13
R.D. Silverman is offline   Reply With Quote
Old 2015-11-16, 16:11   #5
paul0
 
Sep 2011

3×19 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
I don't know what you mean by "match the smooth pairs".
Oh, I was assuming that the two sides are sieved separately, as in two different memory allocations, producing two different sets of smooth pairs. It's clearer to me now. Thanks.
paul0 is offline   Reply With Quote
Old 2015-11-18, 13:58   #6
paul0
 
Sep 2011

3×19 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Give us some data. How long do you take to process a single special-q? 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.
I like to point out that for now, my NFS implementation is a learning (toy) experiment. It won't be made to compete.
paul0 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Sieving and LLR-in in same time pepi37 Software 1 2017-05-15 17:17
mfaktc and CUDALucas side-by-side TObject GPU Computing 2 2012-07-21 01:56
Thanks PG for Sieving, now time to pick a new n? cipher Twin Prime Search 25 2009-08-09 19:32
Optimal Sieving Time jasong Sierpinski/Riesel Base 5 10 2009-01-25 15:56
prime density vs. sieving vs. prp time jasong Math 18 2006-03-31 03:14

All times are UTC. The time now is 15:53.

Mon May 17 15:53:16 UTC 2021 up 39 days, 10:34, 0 users, load averages: 5.54, 4.59, 3.59

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