Go Back > Factoring Projects > CADO-NFS

Thread Tools
Old 2019-11-28, 14:09   #1
Nov 2019

1 Posts
Default Sieve implementation questions (CADO/lasieve)

I'm very interested in implementation of algorithms of computer algebra and am currently studying sieving algorithm.

I have read several papers about sieving (including Franke-Kleinjung about vector sieveing),
but there is still a question of implementation.

More precisely, I'm interesting in the question how does lasieve use such a small amount of RAM (about 400MB for 640-bit modulus with CADO parameters \(I15\) and factor base bound \( limFB = 1.3 * 10^8\)).

As I get some of the sieving algorithm aspects (such like L1-cache hack, etc), the main idea is to sieve firstly medium ideals (i.e. \( (p,r) \) such that \(I < p < limFB\)) and save their
hits into some array (denote it by \(T\)).

Simple estimation of \(|T|\) (number of elements) is given by the formula
\(|T| \approx I*J*(log(log(limFB)) - log(log(I)))\),
so for CADO parameters for 640bit modulus (\(I=2^15\), \(limFB = 1.3 * 10^8\)) we get estimation
\( |T| \approx 314 * 10^6 \).

If we use 4 Bytes for one hit we get an estimated memory usage of about 1.2 GB of RAM (and here we don't take into account that we also need to store factor bases).

My question is: how can we split sieving process for saving RAM? And more precisely how does lasieve use so little memory (about 400MB, as I mentioned earlier)?
I didn't find the answer to this question in open source papers.
Obvious way, of course, is to split sieving rectangle \([-I/2, I/2] \times [1, J] \) geometrically into two \( [-I/2, I/2] \times [1, J/2] \) and \( [-I/2, I/2] \times [J/2, J] \) (this approach is mentioned in Franke-Kleinjung "Continued fractions and lattice sieving").

At the same time, I found in lasieve cweb commentaries that there is also an approach to split sieving area by the oddness type (i.e. to consider only points \((x,y)\) in the sieving area such that \(x\) and \(y\) are not divisible by 2 at the same time). This approach gives reduction of RAM by 2*2=4 times (and probably we also save some time: we sieve only 3 subareas and ignore the 4th where both coordinates are even).
My question here is: Am I right that this approach is useful? Is it used, for example, in lasieve or CADO?

I am also interested in the following. For the second splitting approach we also need to find a starting point in the sieving area for every medium ideal (and this point must be with the corresponding remainder of dividing by 2).
Is there any fast algorithms to find this starting points?
What happens if instead of 2 we use 6 = 2 * 3 (and consider only \((x,y)\) such that \(x\) and \(y\) are coprime mod 6)? It seems like we can reduces RAM by 6*6=36 times (but we also spend more time finding starting points).
olorin is offline   Reply With Quote

Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
64-bit gnfs-lasieve* mklasson Factoring 81 2012-05-06 21:30
Quadratic sieve method implementation.. abhiiitkgp Homework Help 4 2011-10-31 13:22
Nonstandard lasieve binaries fivemack Factoring 8 2010-04-27 18:59
Bug in 64-bit lasieve Shaopu Lin Factoring 3 2009-11-18 18:42
Questions on coding my FFT&LLR implementation nuggetprime Programming 56 2008-10-27 22:45

All times are UTC. The time now is 07:57.

Sun Oct 17 07:57:22 UTC 2021 up 86 days, 2:26, 0 users, load averages: 1.21, 1.48, 1.40

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.