ECM

[wildrabbitt]

ECM

I know there's trial factoring, the P-1 method and the Lucas Lehmer test but

when is the ECM used by prime95?

[0PolarBearsHere]

ECM is used to find factors for "small" exponents we already know are composite.

The basic theory can be read at http://www.mersennewiki.org/index.php/ECM

[ATH]

ECM is not used for GIMPS primary mission of finding Mersenne Primes since it is not worth it to run ECM on exponents in the DC range let alone exponents in the "bleeding" edge.

It is only used for trying to find factors of small Fermat numbers up to F29 and small Mersenne numbers.

[GP2]

Originally Posted by ATH

ECM is not used for GIMPS primary mission of finding Mersenne Primes since it is not worth it to run ECM on exponents in the DC range let alone exponents in the "bleeding" edge.

I have an older computer, four cores, no FMA3 just AVX, my only non-cloud machine, sitting in a non air-conditioned room. The fan was running loud on hot days, so I switched it from DC to 4 × ECM. I'm looking for additional factors of very small exponents that already have known factors, taking them to the full set of 640 curves for B1=250,000. It finds them often enough to keep me interested. The famous user TJAOI is also doing ECM testing in this range, but I'm doing depth-first and he does breadth-first searching, so there is little overlap in practice.

P−1 testing is also finding additional factors of small exponents that already have known factors. I started doing this only a few days ago, and I think I'm the only one, because PrimeNet doesn't give any credit for unsuccessful P−1 tests of exponents that already have known factors.

It's mildly amusing and there is always the outside chance of finding a new probably-fully-factored exponent.

The same could be done for exponents in the same range without known factors, except those have already been tested to much larger limits.

Originally Posted by ATH

It is only used for trying to find factors of small Fermat numbers up to F29 and small Mersenne numbers.

In this range only F20 and F24 have no known factors. I wonder if there is something similar to an LL test for Fermat numbers, something that lets you determine if they are composite without finding a factor.

I have a few cloud machines looking for factors of Fermat numbers but it's slow going. The fastest one currently is F13, but it still needs almost two hours per curve, and it's at a level where tens of thousands of curves are needed. F20 needs almost twenty-two hours per curve, and will allocate 10930 MB for stage two if you let it, although it can probably work well with considerably less memory. It also probably needs thousands of curves, with no guarantee of ever finding a factor.

[LaurV]

Originally Posted by GP2

I wonder if there is something similar to an LL test for Fermat numbers, something that lets you determine if they are composite without finding a factor.

Yes, see here. It is/was widely used to find out that the Fermat numbers up to F32 (I think Ernst is/was working F33??) are composite.

[ATH]

Originally Posted by GP2

In this range only F20 and F24 have no known factors. I wonder if there is something similar to an LL test for Fermat numbers, something that lets you determine if they are composite without finding a factor.

Yes, it is called Pepin's Test, and F20 and F24 was already tested composite back in 1987 and 1999, and the next with status unknown F33 is still too large to run this test on. It would be approximately like running an LL test on M8,589,934,592.

[ATH]

Originally Posted by LaurV

Yes, see here. It is/was widely used to find out that the Fermat numbers up to F32 (I think Ernst is/was working F33??) are composite.

Ernst is working up to F29 currently: http://www.mersenneforum.org/showthread.php?t=18748

I don't think anyone have worked on F30+ yet, and I think F33 is still out of reach.

[LaurV]

Whoops, as you said boyar... for whatever reason I had my digits totally messed