What's ECM?

[aurashift]

Can someone explain what ECM is or point me to an explanation? I'm guessing Elliptical Curve something something.

[science_man_88]

http://www.mersennewiki.org/index.ph...c_curve_method
https://en.wikipedia.org/wiki/Lenstr..._factorization
...

[aurashift]

So um... I kinda get it. sort of. How does it tie in to the mersenne project and why are the exponents handed to ecm so small? Ive got a 40 core that isn't so well suited to LL or DC, and it doesn't really have enough RAM to be good at P-1 (150~GB) so I'm trying to figure out the most helpful job to assign it.

[science_man_88]

Originally Posted by aurashift

So um... I kinda get it. sort of. How does it tie in to the mersenne project and why are the exponents handed to ecm so small? Ive got a 40 core that isn't so well suited to LL or DC, and it doesn't really have enough RAM to be good at P-1 (150~GB) so I'm trying to figure out the most helpful job to assign it.

my first thought is that it's a factoring method and it has a range it's the best in ? but to be honest I only posted links to get you started I don't know enough about it myself.

[aurashift]

hmm. I know elliptic curve cryptography is or was used in phones because it was lightweight, but I don't know how it ties into this project. There isn't an explanation on the web site.

[R.D. Silverman]

Originally Posted by aurashift

hmm. I know elliptic curve cryptography is or was used in phones because it was lightweight, but I don't know how it ties into this project. There isn't an explanation on the web site.

Repeat after me....

Google is my friend.

You clearly have not read anything about what ECM is or does.

[xilman]

Originally Posted by R.D. Silverman

Repeat after me....

Google is my friend.

You clearly have not read anything about what ECM is or does.

Though I use DuckDuckGo for {privacy,ideological} reasons.

[aurashift]

Originally Posted by R.D. Silverman

Repeat after me....

Google is my friend.

You clearly have not read anything about what ECM is or does.

Every post of yours that I've come across you have the aura of someone who is kind of a dick...do you ever sense that?

[VictordeHolland]

Originally Posted by aurashift

So um... I kinda get it. sort of. How does it tie in to the mersenne project and why are the exponents handed to ecm so small? Ive got a 40 core that isn't so well suited to LL or DC, and it doesn't really have enough RAM to be good at P-1 (150~GB) so I'm trying to figure out the most helpful job to assign it.

150GB of RAM for 40 cores is more than enough to run P-1 if you limit it to for instance 3GB per core (it has only a tiny performance penalty). It then does stage 2 in multiple steps, each fitting in 3GB or less.
You could also limit the amount of task simultanuously in stage 2 with "MaxHighMemWorkers=xx" in the local.txt (assuming you are using Prime95).

Factoring exponents by ECM is not helping the projects primary goal of finding the next Mersenne prime. It is done mostly for the fun of finding factors for the smaller exponent.

ECM is efficient for finding factors of small Mersenne exponents where Trial Factoring is not efficient.
TFing a 1M exponent from 71 to 72 bits takes 478GHzdays
ECM on a 1M exponent 280 curves with B1=50,000 only 9.7GHzdays. It has (a very low) probability of missing a 72 bit factor. It has good chance to find factors below 25 digits (remember that is something like >83bits) and even a small chance to find factors with more than 25 digits (with a bit if luck).

The 'biggest problem' with ECM is the increasing memory requirements for the larger numbers and higher B2 values.
I'm currently running ECM (B1=50,000 and B2=5,000,000) in the M1,520,000 - M1,530,000 exponent range and in stage 2 Prime95 is already using 1678MB for each core. For really small exponents (<M10,000) it is better to use GMP-ECM for stage 2, which is faster and uses a larger stage 2 (higher B2).

Usually a number of ECM curves are done with a set of B1 and B2 values before increasing those values if no factor is found.
For instance with GMP-ECM after running 7,557 curves with B1=43,000,000 and default B2 with no factor found, the next step would be to do 17,884 curves with B1=110,000,000 and default B2.

Common abbreviations on the forum:
t50 = equivalent of 7,557 curves completed with B1=43,000,000 (and default B2)
t55 = equivalent of 17,884 curves completed with B1=110,000,000 (and default B2)
t60 = etc....

't50' is a shorthand for the combination of number of curves and the value of B1 that will make the asymptotic probability of missing a 50-digit factor equal to 1/e (i.e. about 37%).

http://mersenneforum.org/showpost.ph...36&postcount=3

It is also true that a t50 means that enough ECM has been done that, if there is a 50 digit factor, you would expect to have found it once. "Expect" is used here in the probability sense, meaning that if you repeated this whole set of ECM runs many times and tallied the number of times you found the factor, the average number of times would be 1. But that average would be composed of sets that found it 0,1,2,3 and even more times. We don't really care about the 2 and 3 times - in most real situations they are hypothetical because we stop looking after finding it once (it's a variant of why are things always in the last place you look.). The binomial distribution could be used to find the probability finding it zero times, but this is in the region where the Poisson distribution is an excellent approximation to the binomial distribution - and that is where 1/e comes from.

http://mersenneforum.org/showpost.ph...55&postcount=4

[aurashift]

Originally Posted by VictordeHolland

150GB of RAM for 40 cores is more than enough to run P-1 if you limit it to for instance 3GB per core (it has only a tiny performance penalty). It then does stage 2 in multiple steps, each fitting in 3GB or less.
You could also limit the amount of task simultanuously in stage 2 with "MaxHighMemWorkers=xx" in the local.txt (assuming you are using Prime95).

Factoring exponents by ECM is not helping the projects primary goal of finding the next Mersenne prime. It is done mostly for the fun of finding factors for the smaller exponent.

ECM is efficient for finding factors of small Mersenne exponents where Trial Factoring is not efficient.
TFing a 1M exponent from 71 to 72 bits takes 478GHzdays
ECM on a 1M exponent 280 curves with B1=50,000 only 9.7GHzdays. It has (a very low) probability of missing a 72 bit factor. It has good chance to find factors below 25 digits (remember that is something like >83bits) and even a small chance to find factors with more than 25 digits (with a bit if luck).

The 'biggest problem' with ECM is the increasing memory requirements for the larger numbers and higher B2 values.
I'm currently running ECM (B1=50,000 and B2=5,000,000) in the M1,520,000 - M1,530,000 exponent range and in stage 2 Prime95 is already using 1678MB for each core. For really small exponents (<M10,000) it is better to use GMP-ECM for stage 2, which is faster and uses a larger stage 2 (higher B2).

Usually a number of ECM curves are done with a set of B1 and B2 values before increasing those values if no factor is found.
For instance with GMP-ECM after running 7,557 curves with B1=43,000,000 and default B2 with no factor found, the next step would be to do 17,884 curves with B1=110,000,000 and default B2.

Common abbreviations on the forum:
t50 = equivalent of 7,557 curves completed with B1=43,000,000 (and default B2)
t55 = equivalent of 17,884 curves completed with B1=110,000,000 (and default B2)
t60 = etc....

http://mersenneforum.org/showpost.ph...36&postcount=3
http://mersenneforum.org/showpost.ph...55&postcount=4

Thank you. That was very helpful, informative, and is appreciated. I'd rather throw hardware behind something that is ultimately more useful, so I'll put the twenty cores I assigned to ECM back on P-1. Perhaps I can even find some more RAM laying around. On observation I think it runs P-1 very fast when it's fed enough RAM (about 30 GBs on the current wavefront last time I checked) to process all the relative primes at once. If not, it does a decent job of carving up the available RAM between the workers without editing the local.txt file.

[R.D. Silverman]

Originally Posted by aurashift

Every post of yours that I've come across you have the aura of someone who is kind of a dick...do you ever sense that?

How would I ever sense what you feel??

You asked for help. Science Man graciously gave two useful links. You clearly failed to read them.
(your follow on post made this clear).

Teachers take a dim view of people who ask for help but refuse to read or put in the effort
needed to learn. You come across as someone who wants everything handed to him.

Indeed, when I called you out on your failure to read what was handed you, you reply with name calling.

Do you have this bad attitude toward all of your teachers?