3,599+ status and discussion

[fivemack]

Experimentally, the distribution of the maximum absolute value M of the entries of qflll(m) for m a matrix of your form is interesting; there's a reasonably sharp spike and then a long tail, and the tail is fit very well by p(M<t) ~ t^-2.

The M1039 write-up says that they threw out special-Q where the reduced matrix had too-large coefficients, which makes sense given how common and how useless such matrices appear to be.

A simple fit for x going from 10^8 to 2^13*10^8 in powers of two, looking at 10^5 matrices for each x, gives (I'm confident to the number of significant figures I give)

25th-percentile = 0.81*x^0.500
median= 1.00 * x^0.500
75th-percentile = 1.34 * x^0.501
90th-percentile = 2.1*x^0.501
99th-percentile = 6*x^0.50

mean = 1.3 * x^0.500

Reduction of 2x2 matrices is essentially representation by continued fractions, and I think it's well-understood; I'd be tempted to look in volume 1 or 2 of the recent edition of Knuth's Art of Computer Programming, in the section where he writes about GCD algorithms.

[fivemack]

The section of this thread after #29 is no longer to do with 3,499+; is there any way that the moderators could be implored to move #39 and follow-ups to, say, a thread called 'Modelling lattice-sieving yields' in the Factoring forum?

[R.D. Silverman]

Originally Posted by fivemack

Experimentally, the distribution of the maximum absolute value M of the entries of qflll(m) for m a matrix of your form is interesting; there's a reasonably sharp spike and then a long tail, and the tail is fit very well by p(M<t) ~ t^-2.

The M1039 write-up says that they threw out special-Q where the reduced matrix had too-large coefficients, which makes sense given how common and how useless such matrices appear to be.

Experimentally, yes. The reduced coefficients seem to fit an
exponential/Erlang, or possibly a gamma distribution.

My sieve code has always thrown out 'bad' reduced lattices, but I define
bad as anything with a large *condition number*. It is not just that large
coefficients give poor yield, but so do highly skewed lattices. Checking
the condition number handles both problems.

[fivemack]

Ah yes, condition number is almost certainly the right way to recognise bad lattices.

I'm pretty sure that the distribution is too tail-heavy to be any of the exponential-based ones, though I can't get it to fit very clearly to any of the distributions in the 'heavy-tailed distributions' Wikipedia article either. The PDF dropping off for large x as almost exactly x^-3 must be telling me something, but I'm not sure what; it doesn't appear to match the distribution for random matrices of a given determinant.

[R.D. Silverman]

Originally Posted by fivemack

The PDF dropping off for large x as almost exactly x^-3 must be telling me something, but I'm not sure what; it doesn't appear to match the distribution for random matrices of a given determinant.

Of course not. Not all matrices of determinant p are affine transforms
of the original lattice..

[fivemack]

Well, that was odd. I'd really expect that, since I'm sieving over the same region at each stage, #relations would be an increasing function of SP - I'm sieving further, I'm leaving all the other parameters the same, I really ought to be getting more relations.

SP	SZ	Relations	Secs / relation
50	14	2956	1.51067
50	15	6123	1.86277
60	14	3209	1.55215
60	15	6742	1.79827
70	14	3417	1.6059
70	15	7085	1.80086
80	14	3610	1.66312
80	15	7045	1.87672
90	14	3755	1.73279
90,15 failed to start, giving an out-of-memory error

On further investigation, I am only losing relations as I go from a small-prime bound of 70M to 80M in gnfs-lasieve4I15e. Maybe this is why gnfs-lasieve4I15e doesn't ship as standard with ggnfs

[bdodson]

Originally Posted by Andi47

What is the ECM status of this one? (I don't want to run ECM on it once somebody is sieving it, but before then I could do a few curves)

M821 = 2,821- C208, along with all of the other Cunninghams with
fewer than 234-digits, is either at 3*t50 or at 4*t50, depending upon
whether it's come up yet on the que for the 4th t50. As I was saying,
if/when this one becomes a near-term sieving target, I'd expect to
finish a version of t55; which in recent practice (the base-2s with 787)
has meant 6*t50 --- so adding 2 or 3 t50's, depending upon how many
have already been done. So far, I've been discounting curves with
B1 = 43M (p50-optimal), and running either B1 = 110M or B1 = 260M
for the new curves. I haven't heard of anyone that'd be sieving M821
anytime soon.

On the remaining numbers below 768-bits, Alex's 7,269- in particular,
I'm not clear whether (t55-4*t50) more curves are indicated. The numbers
in c190-c233 are qued on the Opteron/quadcore beowulf, so scheduling
an extra two t50's would be easy --- especially if that would make the
sieving more likely to happen (sooner). Of course, in Alex's case, he
could probably slip in the extra curves over-night on the grid he's using,
if he were so inclined. -Bruce

PS - I suppose that'd be "below 768-bits" or "degree 5 or 6
with difficulty below 220". Comparing Tom's "1110 CPU-hours"
for sieving 10,309- for example; c. 8hrs on 230 cores of the
quads for a t50 gives 2*8*200 for the extra two t50's
(in t55-4*t50) = c. 3200 CPU-hours. That doesn't sound
good; those curves would_have/were better spent on harder
numbers.

[Andi47]

Originally Posted by bdodson

M821 = 2,821- C208, along with all of the other Cunninghams with
fewer than 234-digits, is either at 3*t50 or at 4*t50, depending upon
whether it's come up yet on the que for the 4th t50. As I was saying,
if/when this one becomes a near-term sieving target, I'd expect to
finish a version of t55; which in recent practice (the base-2s with 787)
has meant 6*t50 --- so adding 2 or 3 t50's, depending upon how many
have already been done. So far, I've been discounting curves with
B1 = 43M (p50-optimal), and running either B1 = 110M or B1 = 260M
for the new curves. I haven't heard of anyone that'd be sieving M821
anytime soon.

Thanks for the info. I have done 5 curves with B1 = 44M and sheduled 100 curves with B1 = 110M (85 of them already done). I can do more curves on either 110M or 260M if wanted

P.S.: How actual is this page? It says that 4968 curves are done on M821 at B1 = 44M - according to your post it must be rather ~21000 curves? And for M1061 AFIK t55 is finished and a few thousand curves have been done at B1=260M, see this thread.

[bdodson]

Originally Posted by Andi47

I can do more curves on either 110M or 260M if wanted

P.S.: How actual is this page? It says that 4968 curves are done on M821 at B1 = 44M - according to your post it must be rather ~21000 curves? And for M1061 AFIK t55 is finished and a few thousand curves have been done at B1=260M, see this thread.

I had an exchange with Mischa in one of the base-2 discussions; and
believe I recall that the counts on his page are personal curves, not
the sum of curves over what other people did. Same for my counts.
I checked M821, and found that my 4th t50 finished Wednesday
(by coincidence, in order, from an old input file). So that's 620 curves
with B1 = 110M (my initial t45), then 5835 curves with B1 = 260M.
That's

evalf(620/17900+5835/8000) = 0.764*t55, same as in what I

reported for the new NFSNET number M787 (which started sieving
yesterday). Two more c. t50's will raise the B1 = 260M's to
8835 curves, which gives the 1.139*t55 from the thread, loc.cit.

On M1061, I'm still saying what I've been saying since finding that
the first kilobit snfs was M1039; namely that so many curves have been
run that additional curves aren't really part of ecm-factoring; but rather
ecm-pretesting, as in the description of the M1039 sieving. If you're
having trouble with the distinction, observe Aoki being _dissapointed_
at having found the 2nd largest (at the time) ecm factor of p64 ---

...Unfortunately, after trying 11784 curves for Step 1 and 11214 curves for Step 2 a factor was found.

since it meant that the work done on setting-up R311 = 11...1 (that's 311)
= (10^311-1)/(10-1) for sieving had been wasted.

Spending the curves on other large numbers has a much better chance
of finding a factor --- the fewer curves run previously, the better. Of
course, they're your cycles; and we have George's description of the
forum objective of "having fun". I may even take my own advice and
take a 2nd pass through the c251-c366's; perhaps after New Years.
-Bruce

[Andi47]

Originally Posted by Andi47

Thanks for the info. I have done 5 curves with B1 = 44M and sheduled 100 curves with B1 = 110M (85 of them already done).

100 curves at B1 = 110M as mentioned above are now ready. I will do a few more curves at B1 = 260M.