Estimate of sieve duration for 2^811 - 1

[xilman]

Originally Posted by dsouza123

Longhorn is the new name for Lonestar, so it is maintained by Richard.

As for Fenland, I don't know for sure, but Fenland is near Cambridge so it probably is Paul.

Sure is.

Paul

[junky]

i'd like to know how is going the end of 811, how is the estimated time remaining to fully complete that project.

thanks.

[Wacky]

Originally Posted by junky

i'd like to know how is going the end of 2,811-, how is the estimated time remaining to fully complete that project.

We have about 6.5GB of data that we are trying to reduce to something like 100 bytes. We won't even have a good estimate of how long it will take until we get a matrix built. So far it isn't going too well. The matrix looks like it may be over 10M square. That will take a LONG time to process.

[ET_]

Originally Posted by Wacky

We have about 6.5GB of data that we are trying to reduce to something like 100 bytes. We won't even have a good estimate of how long it will take until we get a matrix built. So far it isn't going too well. The matrix looks like it may be over 10M square. That will take a LONG time to process.

Would it be time-consuming as well to explain how the matrix is built up?

Luigi

[junky]

i know Wacky and Paul are pretty busy at this time, but like ET_, i'd like to know more details on how the huge matrix is build and wanna know more details about it.

Thanks.

[R.D. Silverman]

Originally Posted by junky

i know Wacky and Paul are pretty busy at this time, but like ET_, i'd like to know more details on how the huge matrix is build and wanna know more details about it.

Thanks.

Here are the basics.

Relations are collected of the form

II p_i ^a_i * B1 * B2 = phi(II P_i^b_i * B3 * B4) mod N

where p_i and P_i are primes in the factor bases and B1, B2, B3, B4 are the
large primes. The B's lie outside the factor bases and some/all of them might
equal 1.

To find a square we must find a set of these relations which, when multiplied
together result in every prime in the product having an even exponent.

Thus, if a value of B appears only ONCE it can never be part of a square.
Before the matrix is constructed, the data is filtered. All relations which
have a value of B that appears only once are discarded. Then pairs of
relations having the same B values are combined together. Furthermore
if B appears (say) 3 times, we can combine these 3 relations into two pairs.
etc. This filtering can be done in several ways. I have code that uses
intelligent Gaussian elimination to combine the relations with large primes.
But it is old, flaky, and written in Fortran. The newest CWI filter code
uses graph clique algorithms to combine the relations with matching large primes.

The matrix is then formed by taking the combined relations, reducing the
exponents mod 2 and inserting them as columns into a large bit matrix.
The size of the matrix comes from two sources: the factor base primes
and the combined large primes.

The time to solve the matrix is proportional to N^2 d where N is the number
of columns and d is the average number of bits that are lit in each column.
Note that d/N is *very* small. Typically d might be about 120 while Paul
estimates N ~ 10M for M811.

Note that part of the objective of the filtering process is to reduce N while
keeping the matrix sparse. Combining relations together reduces N, but
increases d.

Hope this helps.

Bob