Is ECM definite???

[petrw1]

According to: http://www.mersenne.org/report_ECM/
1061 shows as DONE the 55 "Digits in factor" range - which is about 185 bits.

Does that mean TF test below 185 bits are redundant (will NOT find a factor)?

I thought I read somewhere that ECM curves do NOT guarantee all possible factors to that range are considered.

[CRGreathouse]

Originally Posted by petrw1

Does that mean TF test below 185 bits are redundant (will NOT find a factor)?

No, it's possible for ECM to miss factors. They usually remove something like 70% of the factors in their range.

[J.F.]

Which is too bad :(...

I have spent quite a lot of hobby time on enumerating 64 bit pseudoprimes. Most of the remaining work (indirectly) is finding small factors of Mersennes. If only I could use for instance ECM results to rule out trial division search ranges - that would save me CPU years of TD work, which would practically reveal no new factor anyway.

[cheesehead]

Originally Posted by petrw1

According to: http://www.mersenne.org/report_ECM/
1061 shows as DONE the 55 "Digits in factor" range - which is about 185 bits.

In ECM work, there is a standard formula for the recommended number of curves to try at any particular B1. That number is shown at the top of each column as "Curves to test". In the columns below it, "Done" means that at least that number of curves have been run with that B1. So, for M1061 (and M1619) 46,500 (or more) curves have been run with B1=11,000,000.

Note that wherever there is a number instead of "Done" on the horizontal line for an exponent, that number is smaller than the number of "Curves to test" for that column.

[philmoore]

Originally Posted by petrw1

According to: http://www.mersenne.org/report_ECM/
1061 shows as DONE the 55 "Digits in factor" range - which is about 185 bits.

Does that mean TF test below 185 bits are redundant (will NOT find a factor)?

I thought I read somewhere that ECM curves do NOT guarantee all possible factors to that range are considered.

Correct, but although there is a small chance that a 50-digit factor has been missed, the chance that a 45-digit factor has been missed are vanishingly small, and TF at this level is not even feasible anyway.

[petrw1]

Originally Posted by philmoore

Correct, but although there is a small chance that a 50-digit factor has been missed, the chance that a 45-digit factor has been missed are vanishingly small, and TF at this level is not even feasible anyway.

In the <1,000,000 exponent range TF only goes to about 17 or 18 digits.
How fast would it take to ECM these numbers to say 20 digits?
Faster than TF? Much?
If so, then in the same way George is now doing P-1 before the last 2 bits of TF, would it make any sense to ECM before TF?
Or can we NOT ECM exponents in the current ranges?

[akruppa]

Briefly put, ECM is a lot slower in stage 1, and does not benefit from the known factor p in prime factors 2kp+1 of Mersenne numbers M_[I]p[/I], whereas trial factoring and P-1 do. P-1 is barely competitive with trial division for the factor sizes we're trying before an LL test, ECM will not be competitive at all.

The problem is mostly that the LL test is just too darn fast - it's not worthwhile to invest an awful lot of time in factoring first, and while ECM is great when you really want the factors, it doesn't make the cut when it comes to weeding out easy composites before an LL test.

Alex