Factoring humongous Cunningham numbers

[xilman]

Originally Posted by R.D. Silverman

Noone has accurate data.

I have some inaccurate data.

When shut down the ECMnet server had records of a complete t45 and roughly half of a t50.

Bob is correct though: one of the known unknowns is how much extra work had been done other than through the client/server. It must be substantial because Bob himself found a goodly number of factors ranging from 34 digits in 2007 to 59 digits 6.5 years later.

A fair guess is that at least a t50 has been completed.

[R.D. Silverman]

Originally Posted by xilman

I have some inaccurate data.

When shut down the ECMnet server had records of a complete t45 and roughly half of a t50.

Bob is correct though: one of the known unknowns is how much extra work had been done other than through the client/server. It must be substantial because Bob himself found a goodly number of factors ranging from 34 digits in 2007 to 59 digits 6.5 years later.

A fair guess is that at least a t50 has been completed.

I ran 1000 curves on each composite with B1 = 500M.

However, I must ask in response to this question:

Why does it matter (exactly how much ecm has been done)???

Both jyb and I are plowing through them with SNFS. It doesn't matter to us how much has been done.
Why does it matter to the OP?

[xilman]

Originally Posted by R.D. Silverman

I ran 1000 curves on each composite with B1 = 500M.

However, I must ask in response to this question:

Why does it matter (exactly how much ecm has been done)???

Both jyb and I are plowing through them with SNFS. It doesn't matter to us how much has been done.
Why does it matter to the OP?

It doesn't matter to me, either, because I've no intention of running ECM on any of them.

The OP has to answer for himself but I could guess that he's trying to get an estimate of an appropriate B1 for starting his own ECM work.

[R.D. Silverman]

Originally Posted by xilman

It doesn't matter to me, either, because I've no intention of running ECM on any of them.

The OP has to answer for himself but I could guess that he's trying to get an estimate of an appropriate B1 for starting his own ECM work.

It (further ECM) would be a waste of time.

[pinhodecarlos]

Your posts clear my mind. I was in doubt where to allocate my resources, to ecmserver or to NFS@Home.

[jyb]

Originally Posted by xilman

I have some inaccurate data.

When shut down the ECMnet server had records of a complete t45 and roughly half of a t50.

Bob is correct though: one of the known unknowns is how much extra work had been done other than through the client/server. It must be substantial because Bob himself found a goodly number of factors ranging from 34 digits in 2007 to 59 digits 6.5 years later.

A fair guess is that at least a t50 has been completed.

I have some slightly more accurate data. Before the ECMnet server was shut down--and in its later existence I may have been the only client--it got through a complete t50 and several hundred curves with B1 = 11e7. Given Bob's 1000 curves at B1 = 500e6, I would estimate that the composites have all completed roughly a quarter of a t55 (call it maybe a t51.5).

[jyb]

Originally Posted by R.D. Silverman

I ran 1000 curves on each composite with B1 = 500M.

However, I must ask in response to this question:

Why does it matter (exactly how much ecm has been done)???

Both jyb and I are plowing through them with SNFS. It doesn't matter to us how much has been done.
Why does it matter to the OP?

Yes, we are plowing through them with SNFS, but note that we are currently only working on numbers at the low end of difficulty. The known ECM work these numbers have already had makes them ready for SNFS according to the standard 2/9 rule of thumb. Once we've polished off another dozen or so composites, we'll be getting to some which have not had sufficient ECM, again according to that rule of thumb. So yes, it does matter to me how much ECM has been done.

Originally Posted by R.D. Silverman

It (further ECM) would be a waste of time.

You've said this before, notably as part of the discussion here. But you never did answer the questions I posed there, regarding why more ECM is pointless. So I'll boil it down and ask again: do you believe that the 2/9 rule of thumb is not an appropriate way of assessing when a number has received sufficient ECM to begin SNFS? If so, why, and what better metric can you suggest?

As an aside I'll note that ECM pretesting did recently find a 52-digit factor of a number with SNFS difficulty 247, thereby saving a lot of computation, as described here. And yes, I know that we're talking about probability and expected values over many composites/factors here, so one example should not guide our policy; but that one example did make an impression on me vis-a-vis the value of ECM pretesting.

[R.D. Silverman]

Originally Posted by jyb

Yes, we are plowing through them with SNFS, but note that we are currently only working on numbers at the low end of difficulty. The known ECM work these numbers have already had makes them ready for SNFS according to the standard 2/9 rule of thumb. Once we've polished off another dozen or so composites, we'll be getting to some which have not had sufficient ECM, again according to that rule of thumb. So yes, it does matter to me how much ECM has been done.

Why? What matters is how much time is saved *in expectation". Small ECM factors will be quite rare.

You've said this before, notably as part of the discussion here. But you never did answer the questions I posed there, regarding why more ECM is pointless. So I'll boil it down and ask again: do you believe that the 2/9 rule of thumb is not an appropriate way of assessing when a number has received sufficient ECM to begin SNFS? If so, why, and what better metric can you suggest?

The 2/9 rule is a decent approximation. However, its value should be reduced as the numbers get larger.
This should be clear from Dickman's function. This "2/9" value should be a slow decreasing function of N (the composite).
I have never analyzed the exact nature of this function, so I can not say how accurate it is for (say) 100, 150, 200, 250, ....
digits etc.

As the composites get larger once one has done an "initial ECM pass" to say the 50 digit level, the probability that
there is a factor within ECM reach gets SMALLER.

There is no "general rule" that applies uniformly to composites of all sizes. Instead, use the Bayseian methods
I gave in my paper.

As an aside I'll note that ECM pretesting did recently find a 52-digit factor of a number with SNFS difficulty 247, thereby saving a lot of computation, as described here. And yes, I know that we're talking about probability and expected values over many composites/factors here, so one example should not guide our policy; but that one example did make an impression on me vis-a-vis the value of ECM pretesting.

"one example did make an impression on me".

This suggests that your understanding of statistics is inadequate.

Furthermore "saving a lot of computation" is an exaggeration. How much time was spent on ECM? How much
time would SNFS have taken? Subtract. There is your actual savings. But the EXPECTED savings is much
less because such small factors will be RARE.

Stop FIXATING on this 2/9 "rule".

[R.D. Silverman]

Originally Posted by R.D. Silverman

Why? What matters is how much time is saved *in expectation". Small ECM factors will be quite rare.




The 2/9 rule is a decent approximation. However, its value should be reduced as the numbers get larger.
This should be clear from Dickman's function. This "2/9" value should be a slow decreasing function of N (the composite).
I have never analyzed the exact nature of this function, so I can not say how accurate it is for (say) 100, 150, 200, 250, ....
digits etc.

As the composites get larger once one has done an "initial ECM pass" to say the 50 digit level, the probability that
there is a factor within ECM reach gets SMALLER.

There is no "general rule" that applies uniformly to composites of all sizes. Instead, use the Bayseian methods
I gave in my paper.



"one example did make an impression on me".

This suggests that your understanding of statistics is inadequate.

Furthermore "saving a lot of computation" is an exaggeration. How much time was spent on ECM? How much
time would SNFS have taken? Subtract. There is your actual savings. But the EXPECTED savings is much
less because such small factors will be RARE.

Stop FIXATING on this 2/9 "rule".

Let me also add:

People get fixated on the ECM successes. They (perhaps) forget about all of the lost time spent when a factor
was NOT found.

However, SNFS succeeds with certainty. If one spends time to run SNFS, the time is never "lost".

Suppose you spend time T with SNFS and get 3 factorizations.

Suppose you spend the same time T with ECM and are able to test (say) 50 candidates to (say) t55.

Unless you expect to find at least 3 factors with ECM, then you have wasted that time. One needs to assess
the proability of succes at level t55 given the amount of effort already spent. If one failed at t50,
it becomes less likely that one will succeed at t55, especially as the composites get larger.

When one has already made a reasonable ECM effort (YMMV regarding 'reasonable') it is better to succeed
with certainty via SNFS than waste further time with ECM. The exception to this guideline is of course the
case where one lacks the resources to run SNFS. The alternative then becomes "run ECM or do nothing".

[xilman]

Originally Posted by R.D. Silverman

Why? What matters is how much time is saved *in expectation".

I would say the matter is much more subtle than that. Your metric completely ignores factors which may be of great practical importance.

For example, I have some systems which are quite incapable of running SNFS on the remaining HCN candidates because they do not have enough memory and/or mass storage. Although relatively slow they have (an admittedly small) chance of finding p5x or p6x factors by ECM.

Another system has a GPU which is eminently suitable for running many ECM curves in parallel but completely unsuitable for NFS sieving and subsequent phases.

Raw cycle counts are not the only thing of importance, despite CS people concentrating on them because counts are relatively easy to analyze mathematically.

[R.D. Silverman]

Originally Posted by xilman

I would say the matter is much more subtle than that. Your metric completely ignores factors which may be of great practical importance.

For example, I have some systems which are quite incapable of running SNFS on the remaining HCN candidates because they do not have enough memory and/or mass storage. Although relatively slow they have (an admittedly small) chance of finding p5x or p6x factors by ECM.

Another system has a GPU which is eminently suitable for running many ECM curves in parallel but completely unsuitable for NFS sieving and subsequent phases.

Raw cycle counts are not the only thing of importance, despite CS people concentrating on them because counts are relatively easy to analyze mathematically.

I must be imagining things. I could have sworn that I wrote:

"The exception to this guideline is of course the
case where one lacks the resources to run SNFS. The alternative then becomes "run ECM or do nothing". "