ECM change

[Prime95]

I'm reworking the server's algorithm for handing out ECM assignments. The goal is to hand out assignments with the best chance of finding a factor for a fixed CPU effort.

The new algorithm (which may undergo further adjustments) is handing out smaller exponents than before. This isn't of much concern for users unless you've specified multi-threaded workers. Smaller FFT sizes cannot take advantage of multi-threading.

[lycorn]

Speaking of ECM assignments, would it be possible to add a new column to the right of the ECM progress table? Thanks to Ryan Propper's work, several exponents < 10K have now all B1 bounds tested to 800, 000, 000.

[Dylan14]

Another suggestion for ECM work: right now for ECM on Mersennes there are two choices: one for first factors and one for additional factors, and both seem to give curves with B1 = 50k, B2 = 100*B1. Perhaps we should have an additional ECM work type where the server will hand out curves with higher bounds, without having to manually request curves or edit worktodo.txt.

[R.D. Silverman]

Originally Posted by lycorn

Speaking of ECM assignments, would it be possible to add a new column to the right of the ECM progress table? Thanks to Ryan Propper's work, several exponents < 10K have now all B1 bounds tested to 800, 000, 000.

Who put together this table? It says that 360000 curves are needed at B1 = 800M
for t65.



In fact, only ~83000 curves are needed at 800M to achieve t65. 360K curves
is roughly 4.3 x t65. This is massive overkill.

I leave it to others to decide how many curves to run, BUT: after 85K (or so) curves
at 800M, the project should switch to about B1 = 3G or 4G.

[VBCurtis]

Originally Posted by R.D. Silverman

Who put together this table? It says that 360000 curves are needed at B1 = 800Mfor t65.

Prime95 uses B2 = 100 * B1; doesn't that mean many more curves are needed than the usual GMP-ECM bounds?

[alpertron]

Originally Posted by R.D. Silverman

Who put together this table? It says that 360000 curves are needed at B1 = 800M
for t65.



In fact, only ~83000 curves are needed at 800M to achieve t65. 360K curves
is roughly 4.3 x t65. This is massive overkill.

I leave it to others to decide how many curves to run, BUT: after 85K (or so) curves
at 800M, the project should switch to about B1 = 3G or 4G.

The program Prime95 operates with huge numbers. B2 is always set to 100*B1 to prevent memory overflow. That's why the number of curves for Prime95 is greater that the number you indicated above.

[Prime95]

Originally Posted by R.D. Silverman

Who put together this table? It says that 360000 curves are needed at B1 = 800M
for t65.

In fact, only ~83000 curves are needed at 800M to achieve t65. 360K curves
is roughly 4.3 x t65. This is massive overkill.

I leave it to others to decide how many curves to run, BUT: after 85K (or so) curves
at 800M, the project should switch to about B1 = 3G or 4G.

The table came from GMP-ECM (not sure which version) given B2 = B1 * 100.

When results are reported with B2 <> 100*B1, they are converted into the equivalent number of B2=100*B1 curves using a formula given to me by Alex Kruppa.

The table is far from perfect but should give us a rough idea of how much effort has been completed.

[R.D. Silverman]

Originally Posted by alpertron

The program Prime95 operates with huge numbers. B2 is always set to 100*B1 to prevent memory overflow. That's why the number of curves for Prime95 is greater that the number you indicated above.

M1277 is not what I would call a huge number...... Nor is (say) any Mxxx for (say)
xxx < 5000.

YMMV depending on your definition of "huge". Running ECM at B2 = 100 B1 is
horribly inefficient.

[alpertron]

Originally Posted by R.D. Silverman

M1277 is not what I would call a huge number...... Nor is (say) any Mxxx for (say)
xxx < 5000.

YMMV depending on your definition of "huge". Running ECM at B2 = 100 B1 is
horribly inefficient.

If you look at the current assignments at https://www.mersenne.org/primenet/ , there is a lot of assignments of numbers of several million digits (up to about 6 million digits). How can you optimize the step B2 for those numbers?

[R.D. Silverman]

Originally Posted by alpertron

If you look at the current assignments at https://www.mersenne.org/primenet/ , there is a lot of assignments of numbers of several million digits (up to about 6 million digits). How can you optimize the step B2 for those numbers?

The tables under discussion (and for which there was a request to add a column)
do not go nearly that high. They max out at exponents ~15K. (i.e. numbers of ~4K digits
max).

For numbers in the millions of digits convolution methods are clearly out of reach.
For 2^p-1, p< 5K I see no reason not to use convolution based step 2. Save the step 1
result then use GMP-ECM for step 2.

Furthermore, no one is discussing ECM at B1=800M for numbers of the size you suggest.

[alpertron]

The program Prime95 is optimized for huge numbers. Ryan Propper uses GMP-ECM or a similarly step-2 optimized application, and then he sends the results manually to the Primenet server.

It is clear that the should be no need to use Prime95 to discover prime factors of more than 55-60 digits.

Notice that David Bessell found in 2011 the prime factor 7751061099802522589358967058392886922693580423169 of the 17th Fermat number using Prime95. F17 has more than 39400 digits.

He also found the prime factor 37590055514133754286524446080499713 of F19 in 2009. It has more than 157800 digits.