Associate
Okay, enjoy your holiday/work trip
Just so you know your audience, I have absolutely no idea what "it is very difficult to get right maximum "q" because we are getting less relations than expected" means
First sorry for the late reply.
Let me try to explain this in a simple manner
:--------------------------------------------------------------------------
2. Sieving for Relations
The sieving step is not the theoretically most complex part of the algorithm of factorization, but it is the most time consuming part because it iterates over a large domain with some expensive calculations like division and modulo, although some of these can be avoided by using logarithms.
In general optimization of the sieving step will give the biggest reduction in actual running time of the algorithm. It is easy to use a large amount of memory in this step, and one should be aware of this and try to reuse arrays and use the smallest possible data types. The factor bases can for record factorizations contain millions of elements, so one should try to obtain the best on-disk/in-memory tradeoff.
The purpose of the sieving step is to find usable relations, i.e. elements (a, b) with the following properties
• gcd(a, b) = 1
• a + bm is smooth over the rational factor base
• b^deg(f)*f(a/b) is smooth over the algebraic factor base
Finding elements with these properties can be done by various sieving methods like the classical line sieving or the faster lattice sieving, the latter being used at NFS@Home.
The lattice sieving was proposed by John Pollard in "Lattice sieving, Lecture Notes in Mathematics 1554 (1991), 43–49.". The factor bases are split into smaller sets and then the elements which are divisible by a large prime q are sieved. The sizes of the factor bases have to be determined empirically, and are dependent on the precision of the sieving code, if all smooth elements are found or if one skips some by using special-q methods.
One advantage the lattice siever has is the following. The yield rate for the line siever decreases over time because the norms get bigger as the sieve region moves away from the origin. The lattice siever brings the sieve region "back to the origin" when special-q's are changed. This might be its biggest advantage (if there is one).
--------------------------------------------------------------------------
So we were finding less elements per region than we were expecting to be able to build the matrix for the post-processing phase.
Carlos
