Upcoming Work

[R.D. Silverman]

Originally Posted by xilman

I need to check my notes, or fire up the Franke siever again. It appears that my recollection of 130M or so may be incorrect.

The question remains, though: why does your lattice siever take six times the memory of the CWI siever when factoring integers with comparable sized factorbases?

Is it, perhaps, that you keep an entire line in RAM? We sieve in sections, finding that the small overhead incurred is greatly outweighed by the number of machines that can contribute to the sieving. By and large, I'd rather have twice as many machines running at 90% efficiency than have half of my potential pool of sievers not doing anything useful because they don't have enough memory.


Paul

The lattice siever doesn't *use* lines. It sieves over a 2-D array.
Let V1 = {a1, b1}, V2 = {a2, b2} One sieves i * V1 and j * V2
as (i,j) vary. One needs to keep the entire 2-D array in memory.

My lattice siever requires the following storage for one polynomial.
[so double this]

4 bytes per prime
4 bytes per prime for the polynomial root mod that prime
The lattice itself (about 7K x 7K ~ 50M)
Storage for V1 and V2 for each prime. [We compute V1 & V2 during the
first sieve. We save them so we don't have to recompute them for the
resieve]
Storage for the actual prime factors found for a smooth norm during
resieve. i.e. We factor the norms by a second sieve. For each
sieve location that might be smooth following the first sieve, we need
space to store the primes that divide that particular norm.
With ~50M lattice points, and (say) 5% might be smooth, each
divisible by maybe 8 primes, each taking 4 bytes, that gives ~80Mbytes.

Yes, I could probably implement a more compact storage scheme.
But it would be SLOWER.

Since we sieve a big region per special q, relative to the size of a
segment of a sieve line in the line siever, storage for the primes
during resieve takes a LOT of space.



This is *most* of the storage.

There is a relatively small amount (a few megabytes) to store
the potential smooth locations after the first sieve, some sieve starting
points for the primes that we line sieve
(the smallest primes get line sieved within the lattice since they are
guaranteed to take several hits per row], etc. etc. But this storage
is "noise" compared to what I outlined above.

[R.D. Silverman]

Originally Posted by xilman

Something has gone wrong. I posted a lengthy comment, but it seems to have disappeared.

Summary: running with FB primes to 32M should be fine. You won't find as many relations but what you find are as good as any.

The sieving area is close to square in that we expect to have b<40M with |a|<45M. The reciprocal polynomial gives skewness >1 (forget the exact figure, around 1.2) and although I didn't test yields on this occasion, every previous time gave slightly better yields with skew>1 than skew<1. When the skewness is so close to unity it doesn't much matter anyway.

Using half gig RAM sounds excessive. The CWI line siever takes about 80M and Franke's lattice siever about 130M. What are you doing that requires 4-6 times as much memory as the opposition?

I hope this post appears ...


Paul

I give below my lattice sieve yield for the two polynomials.
The lattice used was 6K x 6K [larger would be better for this number
but I did the test on a small memory machine].


FB Index is an index into the factor base indicating
which primes were to be used as special q's. Each row
is the yield of 40 special q's. The entry '10001' means
that the 10001'st prime through the 10040'th prime in the
factor base were used as special q's.

The factor base bound was 31M. The LP bound was 750M.
Clearly, I can improve the yield by increasing these.

Each special q took just under 14 seconds to process on my
1.6GHz Pentium M laptop.


Polynomial: 4x^6 + 1 root = 2^127

FB Index yield.
-------- ----
10001 3228
20001 2328
40001 1906
80001 1453
160001 1021
320001 856
640001 653
1280001 416
1600001 376


Polynomial: x^6 + 4 root = 2^-127

FB Index yield.
-------- ----
10001 3355
20001 2450
40001 2017
80001 1533
160001 1087
320001 895
640001 694
1280001 429
1600001 389


I am *INDEED* surprised. The polynomial you suggested is
about 5% better. This is not what my intuition said to me.
Clearly, I was in error!!!

[xilman]

Originally Posted by R.D. Silverman

The lattice siever doesn't *use* lines. It sieves over a 2-D array.
Let V1 = {a1, b1}, V2 = {a2, b2} One sieves i * V1 and j * V2
as (i,j) vary. One needs to keep the entire 2-D array in memory.

Hang on a minute.

Both sievers sieve over lattice points represented by a 2-D array. The line siever sieves over "lines" in a lattice where the coordinates have been transformed according to {{1,0}, {0,1}} (i.e. the identity transformation) and the lattice siever sieves over "lines" in a lattice where the transformation is cleverly chosen such that all lattice points are divisible by the special-q.

In principle, one could use a 2_D array for the line siever (holding a range of a for each of a range of b) but no-one does so because there is essentially no benefit to it.

Originally Posted by R.D. Silverman

My lattice siever requires the following storage for one polynomial.
[so double this]

4 bytes per prime
4 bytes per prime for the polynomial root mod that prime
The lattice itself (about 7K x 7K ~ 50M)
Storage for V1 and V2 for each prime. [We compute V1 & V2 during the
first sieve. We save them so we don't have to recompute them for the
resieve]
Storage for the actual prime factors found for a smooth norm during
resieve. i.e. We factor the norms by a second sieve. For each
sieve location that might be smooth following the first sieve, we need
space to store the primes that divide that particular norm.
With ~50M lattice points, and (say) 5% might be smooth, each
divisible by maybe 8 primes, each taking 4 bytes, that gives ~80Mbytes.

Yes, I could probably implement a more compact storage scheme.
But it would be SLOWER.

Since we sieve a big region per special q, relative to the size of a
segment of a sieve line in the line siever, storage for the primes
during resieve takes a LOT of space.



This is *most* of the storage.

There is a relatively small amount (a few megabytes) to store
the potential smooth locations after the first sieve, some sieve starting
points for the primes that we line sieve
(the smallest primes get line sieved within the lattice since they are
guaranteed to take several hits per row], etc. etc. But this storage
is "noise" compared to what I outlined above.

Thanks for the details.

Like you, I'm not particularly interested in what you term "noise". It's the bulk storage that allows or disallows particular machines to participate in sieving. As I said earlier, I'd rather have machines sieving SLOWER (your emphasis) than not sieving at all --- as long as the productivity of the entire group of sieving machines is thereby increased.

The CWI linesiever uses ~40M for the primes and roots. It stores diffences between primes in 2-byte data. It also holds a portion of a line which we generally set to about 20M. The remaining 25M or so holds the resieving data (pretty much the same as yours, but that the line length is ~20M in the CWI case and 50M entire lattice for you). Adding these up comes to around 85M, plus inconsequential noise.


Paul

[R.D. Silverman]

Originally Posted by xilman

Hang on a minute.

Both sievers sieve over lattice points represented by a 2-D array. The line siever sieves over "lines" in a lattice where the coordinates have been transformed according to {{1,0}, {0,1}} (i.e. the identity transformation) and the lattice siever sieves over "lines" in a lattice where the transformation is cleverly chosen such that all lattice points are divisible by the special-q.

Yes, but there is NO way to sieve the 2-D array in the lattice siever
one row (or column) at a time.

We sieve i * (a1, b1) + j * (a1,b2). Note that a change in either i
or j changes BOTH the column and the row. This is what makes
cache management in the lattice siever so critical.

I also have the additional storage over a line siever of storing V1 and V2
for each prime.

[xilman]

Originally Posted by R.D. Silverman

Yes, but there is NO way to sieve the 2-D array in the lattice siever
one row (or column) at a time.

Do you have source for the CWI siever?

Peter Montgomery seems to have found a way of doing something which you appear to have claimed is impossible.

If you don't have the source but do have the binary, have you ever wondered what the PB line in the siever's input file means?

Here is a snippet from the documentation.

 PB
        pb00, pb01, pb10, pb11 -- When we sieve over (a, b) pairs,
                the internal (a, b) sieve over multiples of the basis
                vectors (pb00 pb10) and (pb01 pb11).  The parameters
                such as facenter and bnow (above) refer to internal a and b.
                For the relations output (and for computing norms),
                the following a and b are used

                   (a on relations)   (pb00  pb01)  (internal a)
                                    =
                   (b on relations)   (pb10  pb11)  (internal b)

               Usually this line has 1 0 0 1.

It is, of course, entirely possible that I've misunderstood both the documentation and the source.


Paul

[R.D. Silverman]

Originally Posted by xilman

Do you have source for the CWI siever?

Peter Montgomery seems to have found a way of doing something which you appear to have claimed is impossible.

If you don't have the source but do have the binary, have you ever wondered what the PB line in the siever's input file means?

Here is a snippet from the documentation.

 PB
        pb00, pb01, pb10, pb11 -- When we sieve over (a, b) pairs,
                the internal (a, b) sieve over multiples of the basis
                vectors (pb00 pb10) and (pb01 pb11).  The parameters
                such as facenter and bnow (above) refer to internal a and b.
                For the relations output (and for computing norms),
                the following a and b are used

                   (a on relations)   (pb00  pb01)  (internal a)
                                    =
                   (b on relations)   (pb10  pb11)  (internal b)

               Usually this line has 1 0 0 1.

It is, of course, entirely possible that I've misunderstood both the documentation and the source.


Paul

No, I do not have the source. The comments above are not totally clear
to me.

AFAIK, the line siever fixes b, sieves over (a,b) for |a| < M,
then lets b --> b+1. I suspect that the comments above are "hooks"
for a future lattice siever version of the code. I remember Peter telling
me that some of the hooks were already present for a lattice siever.

But I am just guessing.

[Wacky]

I'm just the "new kid on the block", but isn't line sieving just the special case of lattice sieving where q=1 ?

As I understand it, in either case, for integers umin ≤ u ≤ umax, vmin ≤ v ≤vmax, we examine a rectangular space looking for smooth norms.

There is a linear transformation from (u,v) to (a,b).

Now sieving is based on the idea that, because the function (norm) is polynomic in (a,b), if p | f(a0,b0) then p(f(a0+p, b0).

But, since the transform is linear, the property also holds in the (u,v) space.

So it seems to me that any technique which partitions the sieving space for the line siever would have a dual in the general lattice case.

Am I missing something?

(Besides sleep :) )

[R.D. Silverman]

Originally Posted by Wacky

I'm just the "new kid on the block", but isn't line sieving just the special case of lattice sieving where q=1 ?

As I understand it, in either case, for integers umin ≤ u ≤ umax, vmin ≤ v ≤vmax, we examine a rectangular space looking for smooth norms.

There is a linear transformation from (u,v) to (a,b).

Now sieving is based on the idea that, because the function (norm) is polynomic in (a,b), if p | f(a0,b0) then p(f(a0+p, b0).

But, since the transform is linear, the property also holds in the (u,v) space.

So it seems to me that any technique which partitions the sieving space for the line siever would have a dual in the general lattice case.

Am I missing something?

(Besides sleep :) )

Every step/stride that is taken with the lattice siever changes BOTH a and
b.........

[Wacky]

Originally Posted by R.D. Silverman

Every step/stride that is taken with the lattice siever changes BOTH a and b.........

Yes. So ...

The transformation matrix from (u,v) to (a,b) has a rational inverse.

Is it not true that for every p, p|f(u0,v0) implies p|f(u0+k*p,v0) for some k?
And similarly, p|(u0+g(v0), v0+1) for some g ?
In the case of "line sieving", k=1. For a general lattice, it is generally not so simple, but, IIRC, k is the lcm of the denominators of the inverse of the transformation matrix.

[R.D. Silverman]

Originally Posted by Wacky

Yes. So ...

The transformation matrix from (u,v) to (a,b) has a rational inverse.

Is it not true that for every p, p|f(u0,v0) implies p|f(u0+k*p,v0) for some k?
And similarly, p|(u0+g(v0), v0+1) for some g ?
In the case of "line sieving", k=1. For a general lattice, it is generally not so simple, but, IIRC, k is the lcm of the denominators of the inverse of the transformation matrix.

In the lattice siever, the values of u0,v0 will lie OUTSIDE the region being
sieved. Instead, for each prime p we compute a reduced lattice
(a0, b0), (a1, b1) and sieve over (i,j), i,j, small. (say less than 8K) p divides the norm at the point i*(a0, b0) + j*(a1,b1)., NOT at (i,j).

In fact what happens is that there is a doubly reduced lattice over which we
sieve. We select a special q, and find a reduced lattice i* V0 + j* V1
for the locations divisible by q. Call this the (i,j) lattice. Then, within
that lattice, for each prime in the factor base p, we find a p-reduced
lattice within the (i,j) lattice. Call this the (e,f) lattice. We actually sieve
over the (e,f) lattice.

given that:
p|f(u0, v0) it is true that p(u0 + kp, v0), but u0 + kp will lie OUTSIDE
the sieve region for all but the smallest primes.

[Wacky]

Originally Posted by R.D. Silverman

In the lattice siever, the values of u0,v0 will lie OUTSIDE the region being sieved

Bob,
I think that we are having a lack of communication based on the notation.

I intended (u0,v0) to be any point in the (u,v) space such that p|f(). In particular, I would assume that you would find one within the sieving space to which you would assign the index (0,0).

When I have more time, I will attempt to present my thoughts in a more rigorous manner.