# The Elliptic Curve Method for Integer Factorization (ECM)#

Sage includes GMP-ECM, which is a highly optimized implementation of Lenstra’s elliptic curve factorization method. See https://gitlab.inria.fr/zimmerma/ecm for more about GMP-ECM. This file provides a Cython interface to the GMP-ECM library.

AUTHORS:

• Robert L Miller (2008-01-21): library interface (clone of ecmfactor.c)

• Jeroen Demeyer (2012-03-29): signal handling, documentation

• Paul Zimmermann (2011-05-22) – added input/output of sigma

EXAMPLES:

```sage: from sage.libs.libecm import ecmfactor
sage: result = ecmfactor(999, 0.00)
sage: result
True
sage: result in [3, 9, 27, 37, 111, 333, 999] or result
True
sage: result = ecmfactor(999, 0.00, verbose=True)
Performing one curve with B1=0
Found factor in step 1: ...
sage: result
True
sage: result in [3, 9, 27, 37, 111, 333, 999] or result
True
sage: ecmfactor(2^128+1,1000,sigma=227140902)
(True, 5704689200685129054721, 227140902)
```
sage.libs.libecm.ecmfactor(number, B1, verbose=False, sigma=0)#

Try to find a factor of a positive integer using ECM (Elliptic Curve Method). This function tries one elliptic curve.

INPUT:

• `number` – positive integer to be factored

• `B1` – bound for step 1 of ECM

• `verbose` (default: False) – print some debugging information

OUTPUT:

Either `(False, None)` if no factor was found, or `(True, f)` if the factor `f` was found.

EXAMPLES:

```sage: from sage.libs.libecm import ecmfactor
```

This number has a small factor which is easy to find for ECM:

```sage: N = 2^167 - 1
sage: factor(N)
2349023 * 79638304766856507377778616296087448490695649
sage: ecmfactor(N, 2e5)
(True, 2349023, ...)
```

If a factor was found, we can reproduce the factorization with the same sigma value:

```sage: N = 2^167 - 1
sage: ecmfactor(N, 2e5, sigma=1473308225)
(True, 2349023, 1473308225)
```

With a smaller B1 bound, we may or may not succeed:

```sage: ecmfactor(N, 1e2)  # random
(False, None)
```

The following number is a Mersenne prime, so we don’t expect to find any factors (there is an extremely small chance that we get the input number back as factorization):

```sage: N = 2^127 - 1
sage: N.is_prime()
True
sage: ecmfactor(N, 1e3)
(False, None)
```

If we have several small prime factors, it is possible to find a product of primes as factor:

```sage: N = 2^179 - 1
sage: factor(N)
359 * 1433 * 1489459109360039866456940197095433721664951999121
sage: ecmfactor(N, 1e3)  # random
(True, 514447, 3475102204)
```

We can ask for verbose output:

```sage: N = 12^97 - 1
sage: factor(N)
11 * 43570062353753446053455610056679740005056966111842089407838902783209959981593077811330507328327968191581
sage: ecmfactor(N, 100, verbose=True)
Performing one curve with B1=100
Found factor in step 1: 11
(True, 11, ...)
sage: ecmfactor(N/11, 100, verbose=True)
Performing one curve with B1=100
Found no factor.
(False, None)
```