5^421-1 sieving (reservations closed)

[jasonp]

Thanks. The portion of the dataset with three large primes is smaller than I expected, possibly because the SQUFOF code fails more often when inputs are 61 or 62 bits in size, and also because the large polynomial skew means the average polynomial size is very small unless b is larger, so that there is less opportunity to switch to 3LP. I would think the 3LP yield would go way up if we were only line sieving, but I'm happy to contribute 0.5% of the total relations :)

[bsquared]

288-308 is done, except for a few 100kQ near the beginning of the range. Upload will commence soon... I'll get the stragglers in later - probably a couple more days.

judging strictly by filesize, this range has about 4.5% fewer relations than the last 20M range (and the missing few 100kQ accounts for ~2% of this reduction, so ~2.5% less). Doesn't seem like we're running too strongly into diminishing returns yet, but this is based only on filesize, for now.

reserving 308 - 328. Unless you think I should start to concentrate on < 90M ?

[fivemack]

I've not yet run the yield experiment that I wanted to do on the smaller Q-values, I'll do it over Thursday night - I'm rushing to get 100-120 done by the weekend. So probably sensible to reserve 308-328 at the moment.

[fivemack]

OK, I've done the yield experiment

(algebraic side, alim=Q0, sieve from Q0 to Q0+10k on K8/2200)

40M 13476 0.57880s/r
50M 12888 0.56763s/r
60M 13466 0.57731s/r
70M 13473 0.56660s/r
80M 12310 0.55891s/r

so it looks as if the yield is not dropping off catastrophically even at 40M. My model for duplications isn't working very well, but it looks as if the rate isn't going to be cataclysmic.

[fivemack]

We have just hit the 200MQ mark, so I did a filtering run today. Log attached.

Unexpectedly good news: we have a matrix.

The less-good news: it is a matrix of unspeakable vastness, another hundred million Q would be very useful to make it into something slightly more practical.

weight of 22989546 cycles is about 1609444441 (70.01/cycle)

I am leaving the machine running overnight to get the actual matrix size - I hope overnight is long enough, it is swapping quite significantly, msieve.dat.mat is only growing at about 20kb/second, and top tells me

Mem:   8194260k total,  8148544k used,    45716k free,     3932k buffers
Swap: 15623172k total,  8418716k used,  7204456k free,   903288k cached
...
24844 fivemack  20   0 10.3g 4.9g  568 D    1 62.3 585:19.41 msieve

[jasonp]

Originally Posted by fivemack

Unexpectedly good news: we have a matrix.

The less-good news: it is a matrix of unspeakable vastness, another hundred million Q would be very useful to make it into something slightly more practical.

Agreed, but the matrix you have is not incredibly bad. Greg successfully solved a matrix only a little smaller than the current one. Still, if the machine is swapping just trying to build the matrix, the odds for an in-memory matrix version under 8GB don't look good.

[bdodson]

Originally Posted by fivemack

...
The less-good news: it is a matrix of unspeakable vastness, another hundred million Q would be very useful to make it into something slightly more practical.

weight of 22989546 cycles is about 1609444441 (70.01/cycle)

...

This sounds familiar. From my 200M nonduplicate relns for 5,389+ I got

weight of 21054112 cycles is about 1474032635 (70.01/cycle)

The matrix was showing 7.2Gb in "top", from a msieve report of
"memory use: 6466.7 MB" with

saving the first 48 matrix rows for later
matrix is 21013127 x 21013375 (6088.4 MB) with weight 1512170490
  (71.96/col)
sparse part has weight 1385905099 (65.95/col)

I forget if this is quite as bad as the matrix Richard did for Greg's
number (12,241- iirc), but it is surely more close to that than to
my objective of staying below the difficulty of the 7,311+.

Speaking of which, the 7,311+ matrix finished right on schedule
yesterday. I've had three sqrt misses so far, which shouldn't be
anything to be worried about.

I am worried, though. This is the first number past the Franke/ggnfs
bound at 255 digits. A bound that is also used in the release version
of msieve. I don't feel nervous about the dependencies (presuming
we know our linear algebra); but the sqrt is more definitely out in
algebraic numbers. Has anyone checked to see whether there's
anything that's tricky in adding some chars to get to 258-digits?

The start of my three dependices looks OK:

reading relations for dependency 1
read 8592781 cycles
cycles contain 28502626 unique relations
read 28502626 relations
multiplying 40463902 relations
multiply complete, coefficients have about 1069.65 million bits
--

reading relations for dependency 2
read 8588925 cycles
cycles contain 28488491 unique relations
read 28488491 relations
multiplying 40440670 relations
multiply complete, coefficients have about 1069.03 million bits
--

reading relations for dependency 3
read 8589852 cycles
cycles contain 28497102 unique relations
read 28497102 relations
multiplying 40458880 relations
multiply complete, coefficients have about 1069.52 million bits

These look plausible; more cycles, more relns, larger coef. What
looks unusual is the modulus:

initial square root is modulo 62851
--
initial square root is modulo 62473  [and]
--
initial square root is modulo 62761

Those are way smaller than the modulus for any of
my other numbers. For 3,536 c252 there was

modulo 174873547
modulo 174444847
modulo 175552543

For 3,547 c242; "modulo 629128447" and for 10,257-

modulo 20904019
modulo 20629429
modulo 20847061
modulo 20797981  [and]
-----------------
modulo 14003203
modulo 14019199
modulo 14026189

for 10,257+. Has anyone seen such a small modulus (five digits)
for another hard numbers? Perhaps a place in the sqrt code where
there might be an overflow, for adding extra digits to the sizes of the
intended numbers?

Of course, if one of the next two or three dependencies runs
OK with a five digit modulus (by which I mean "runs OK _and_
finds a factor!") I won't be nervous any more. Just checking.

-Bruce (doing some more sieving on 5,389+, 600M-800M to start;
looking for maybe another 40M unique?)

PS - no; the matrix I'm thinking of was

matrix is 18720804 x 18721052 (5170.3 MB)  with weight 1285924286 (68.69/col)
Sat Mar 22 03:40:43 2008  sparse part has weight 1168145840 (62.40/col)

My recollection (surely flawed, but anyway ...) is that this 12,241- matrix is
still the hardest among NFSNET and Childers/Dodson numbers. So 21.0M^2
is way out of bounds.

[R.D. Silverman]

Originally Posted by bdodson

Speaking of which, the 7,311+ matrix finished right on schedule
yesterday. I've had three sqrt misses so far, which shouldn't be
anything to be worried about.

I am worried, though.

Perhaps you might consider switching to the CWI sqrt code?
I suspect that if your sqrt really does fail, converting the relations
(and dependency info) to CWI format would be less work that
re-running the matrix. I understand that msieve-->cwi format code
already exists.

????

[R.D. Silverman]

Originally Posted by bdodson

<snip>
Of course, if one of the next two or three dependencies runs
OK with a five digit modulus (by which I mean "runs OK _and_
finds a factor!") I won't be nervous any more. Just checking.

Are you getting just trivial dependencies, or is it the case that
x^2 != y^2 mod N? If the latter, I suspect that you are in
trouble.

Do you have any code that adds up the exponents in the dependencies
and confirms that they sum to 0 mod 2?

[jasonp]

Bruce: thanks for the figures on the big matrices. The small prime used in the square root is calculated to produce a modulus that, after being squared a bunch of times, is a few thousand bits larger than the expected size of the largest coefficient of the square root. My understanding of the math is that any starting prime, no matter how small, will allow the Newton iteration to converge as long as the square root is not a multiple root. In fact, for number fields that are irreducible modulo all primes, the code picks a starting prime a little larger than ~50, finds the square root mod that prime by enumeration, and performs the Newton iteration as if nothing was different. That produces convergence about 2/3 of the time.

Also, the size of multiple-precision numbers is limited to 27*32 bits, which adds a few guard digits above 255 digits

Bob: there is a lot of checking for dependencies, separate from checking the dependency vectors (which does happen):
- powers of primes and all algebraic ideals are verified to be even
- the number of total relations and free relations is verified to be even
- when the relation product is computed, the code verifies that the product coefficients mod (a 31-bit prime for which alg. poly is irreducible) equal the result of all relations reduced mod the same prime then multiplied together
- the computed square roots are distinct, and equal the same value mod N when squared

Any of these not working causes the dependency to be abandoned, so that if there's no error message then I'm prepared to believe the dependency worked fine (or failed in a way that would still pass all those tests).

This could also be a case where the number has three factors, and unfortunately in this case msieve will not display anything until all three are found.

PS: Using the CWI square root code requires all 1-word integers not exceed 2^30, and the current dataset might not allow that

[Batalov]

For what it's worth, I've seen "small" moduli before (for 7,384+); had the same feeling; everything finished fine. Of course it was a much smaller matrix ~5M.