Elliptic Curve Factorization Method (ECM): Theory, Cryptanalysis, and Practical Demonstrations in Google Colab

Abstract. This paper presents an in-depth analysis of the Lenstra factorization algorithm (ECM), one of the most efficient subexponential methods for finding nontrivial divisors of integers. The mathematical foundations of the method, its connection with Bitcoin cryptography (secp256k1), and key complexity parameters are discussed. Particular attention is paid to practical implementation: scripts in Python, SageMath, and PARI/GP, adapted for execution in the Google Colab environment, are developed and analyzed in detail. The scripts demonstrate the calculation of the order of an elliptic curve over a finite field, modeling the stages of the ECM, and a comparison with $p - 1$ Pollard’s algorithm and visualization of the distribution of smooth numbers.

The problem of factoring large integers remains a cornerstone of modern cryptography. The security of many asymmetric systems, particularly RSA, is based on the computational difficulty of factoring the product of two large prime numbers. Among the many algorithms, the elliptic curve factorization method (ECM) , proposed by Hendrik Lenstra in 1985, holds a special place. Its key feature is that the complexity depends solely on the size of the smallest prime divisor. $p$ , and not on the size of the number itself $N$ This makes ECM an indispensable tool for handling tails in number field sieve (NFS) algorithms and for attacks on systems with small prime factors.

In this article, we not only systematize the theoretical foundations of ECM but also provide a series of ready-to-run scripts for Google Colab that clearly illustrate the algorithm’s operation, strengths, and limitations. This will allow researchers and practitioners to quickly reproduce key experiments and gain a deeper understanding of the underlying mechanisms. Elliptic curve factorization (ECM), also known as Lenstra’s method, is a subexponential integer factorization algorithm. It is one of the most powerful tools in cryptanalysis for finding nontrivial divisors, particularly effective when the desired divisor is relatively small but too large for trial division or Pollard’s rho algorithm.

1. Theoretical foundations and mathematical apparatus of ECM

The idea behind the ECM method is a generalization of Pollard’s $p-1$ algorithm. Instead of the multiplicative group $\mathbb{Z}_p^*$, the method uses the group of points of an elliptic curve over a finite field $\mathbb{E}(\mathbb{F}_p)$.

Weierstrass equation

To factorize the number $N$, a random elliptic curve in Weierstrass form is chosen:

$E : y^{2} \equiv x^{3} + a x + b (\mod N)$

where the parameters $a, b \in \mathbb{Z}_N$ are chosen randomly so that the discriminant of the curve $\Delta = -16(4a^3 + 27b^2)$ is relatively prime to $N$, that is, $\text{GCD}(4a^3 + 27b^2, N) = 1$.

The essence of the algorithm

According to Hasse’s theorem, the order of the group of points $N_p = |E(\mathbb{F}_p)|$ lies in the interval:

$p + 1 - 2 \sqrt{p} \leq N_{p} \leq p + 1 + 2 \sqrt{p}$

Unlike Pollard’s p-1 group, where the order of the group is always p-1, in ECM the order of the N_p group depends on the random choice of the curve. If for one curve the N_p group is not B-smooth (that is, it only splits into small prime factors not exceeding the B-bound), we can simply choose a different curve. This gives ECM a significant advantage—the ability to vary the group until a suitable one is found.

Steps of the algorithm

A random elliptic curve $E$ modulo $N$ and a point $P(x_0, y_0)$ on it are selected.
The smoothness boundary $B$ is selected.
The number $k$ is calculated as the product of prime numbers $q \le B$ raised to the corresponding powers (or $k = B!$).
The point $Q = kP$ on the curve is calculated modulo $N$.

When adding points on an elliptic curve, the formula for the slope of the secant or tangent $\lambda$ is used. The denominator $\lambda$ contains the difference between the $x$ or $y$ coordinates. To find the inverse modulo $N$, the extended Euclidean algorithm is used. If the denominator is not relatively prime to $N$ and is not equal to $N$, the GCD algorithm will return a nontrivial divisor of $N$.

2. ECM’s relationship to Bitcoin’s cryptography (secp256k1)

Bitcoin uses a specific secp256k1 elliptic curve over a finite prime field $\mathbb{F}_p$, defined by the equation $y^2 = x^3 + 7$.

Although the Bitcoin protocol itself uses curves for digital signatures (ECDSA/Schnorr) rather than for factorization, understanding the structure of the elliptic curve group directly links ECM and Bitcoin’s security. In Bitcoin cryptography, the order of the base point $n$ is a gigantic prime (close to $p$), making the discrete logarithm problem (ECDLP) intractable for modern computers.

From a cryptanalytic perspective, ECM demonstrates the vulnerability of factorization-based systems (such as RSA) compared to elliptic curve systems. Breaking RSA-2048 using NFS (the best algorithm for large numbers) requires colossal resources. ECM is used to factorize the “tails” remaining after applying a sieve to a number field, or to attack systems with special keys (for example, if one of the RSA prime factors $p$ is such that the order of the random curve $E(\mathbb{F}_p)$ is smooth). Bitcoin’s security relies on the fact that the order of the secp256k1 group has no small factors (it is prime), so methods similar to ECM (based on smoothness) are inapplicable to it.

3. Parameters and complexity

The complexity of the ECM algorithm for finding the smallest prime divisor $p$ of a number $N$ is:

$L_{p} [1 / 2, \sqrt{2}] = \exp ((\sqrt{2} + o (1)) \sqrt{\ln p \ln \ln p})$

The complexity depends only on the size of the desired divisor $p$ , not on the number $N$ itself. This makes ECM ideal for finding divisors up to 50-60 decimal digits (about 160-200 bits).

4. Historical examples and records

The ECM method, proposed by Hendrik Lenstra in 1985, regularly sets records in factorization.

In 1998, Conrad Curry found a 53-digit divisor of $2^{677} – 1$.
In April 2005, a 66-digit divisor of the number $3^{466} + 1$ was found.
In August 2006, Brent Dodson found a 67-digit divisor.
As of September 2013, the largest divisor found using ECM was 83 decimal digits long.

5. Practical implementation and code examples

Python example (simplified concept)

import math

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def ext_euclid(a, b):
    if a == 0:
        return b, 0, 1
    gcd, x1, y1 = ext_euclid(b % a, a)
    x = y1 - (b // a) * x1
    y = x1
    return gcd, x, y

def mod_inverse(a, m):
    g, x, y = ext_euclid(a, m)
    if g != 1:
        return g # Возвращаем делитель вместо ошибки
    return x % m

# Опущена сложная логика сложения точек для краткости,
# но при попытке найти обратный элемент для (x2 - x1) mod N
# алгоритм вернет делитель, если НОД(x2 - x1, N) > 1.

Example on SageMath

# Факторизация с помощью встроенной функции ECM в SageMath
N = 1005973 * 104395303  # Пример составного числа
print(f"Factoring {N}")

# Вызов ECM
factors = ecm.factor(N)
print(f"Factors: {factors}")

Example on PARI/GP

\\ В PARI/GP ECM используется автоматически в функции factor, 
\\ но можно контролировать алгоритмы.
N = 1005973 * 104395303;
F = factor(N);
print(F);

Example on Magma

N := 1005973 * 104395303;
/* В Magma доступен пакет ECM */
facs := ECMFactoring(N);
print facs;

2. Mathematical foundation of ECM

2.1 Elliptic curves and point groups

Let $N$ — a composite number that needs to be factorized. Consider an elliptic curve in Weierstrass form:

$E : y^{2} \equiv x^{3} + a x + b (\mod N),$

Where $a, b \in Z_{N}$ and discriminant $Δ = - 16 (4 a^{3} + 27 b^{2})$ is mutually prime with $N$ . Set of points $(x, y)$ , satisfying the equation, together with the “point at infinity” $O$ forms an Abelian group $E (Z_{N})$ (provided that $N$ — simple; in the composite case we work modulo $N$ , and operations are performed until division by zero occurs).

The key property used in ECM is the group structure $E (F_{p})$ for a prime divisor $p$ numbers $N$ By Hasse’s theorem, the order of the group $N_{p} = | E (F_{p}) |$ satisfies:

$p + 1 - 2 \sqrt{p} \leq N_{p} \leq p + 1 + 2 \sqrt{p} .$

Unlike the multiplicative group $F_{p}^{*}$ , the order of which is always equal to $p - 1$ , order $N_{p}$ can vary widely depending on the curve parameters. It is this variability that gives ECM an advantage over $p - 1$ Pollard’s algorithm: if for one curve $N_{p}$ is not $B$ -smooth, we can choose another curve and get a new order.

2.2 Stages of the algorithm

Initialization. A random curve is selected . $E$ and that’s it $P (x_{0}, y_{0})$ on it by module $N$ .
Smoothness boundary. Specified as an integer. $B$ (For example, $B = 10^{4}$ or $10^{6}$ ).
Construction of the multiplier k. Usually $k = \prod_{q \leq B} q^{⌊ \log_{q} B ⌋}$ or $k = B!$ .
Calculating Q=kP. Point addition formulas are used. For each addition, the slope is calculated. $λ$ , in the denominator of which is the difference in coordinates $x_{2} - x_{1}$ or $2 y_{1}$ .
Checking the divisor. If, when calculating the inverse element modulo $N$ the denominator turns out to be not coprime with $N$ , the extended Euclidean algorithm returns a non-trivial divisor $N$ .

The probability of success in one “cycle” (one curve) is determined by the probability that the order $N_{p}$ is $B$ – smooth. Due to the freedom to choose the curve, this probability can be made quite high through repeated attempts.

3. ECM’s relationship to Bitcoin cryptography and secp256k1

The Bitcoin protocol uses the secp256k1 curve: $y^{2} = x^{3} + 7$ over $F_{p}$ , Where $p = 2^{256} - 2^{32} - 977$ . Base point order $G$ is a prime number $n$ (near $2^{256}$ ), what makes the group $E (F_{p})$ cyclic of prime order. This is fundamentally important for resistance to attacks based on the smoothness of the group order: since $n$ has no small divisors, methods like ECM (which exploit the smoothness of the order) fail. Thus, Bitcoin’s security relies on the fact that the discrete logarithm problem on such a curve (ECDLP) remains computationally intractable.

On the other hand, ECM reveals the vulnerability of systems where the order of the multiplicative group or elliptic curve group is smooth. This is why the smoothness of the orderings must be carefully controlled when choosing the parameters of RSA and ECC.

4. Complexity characteristics

ECM Complexity for Finding a Prime Divisor $p$ numbers $N$ is estimated as

$L_{p} [\frac{1}{2}, \sqrt{2}] = \exp ((\sqrt{2} + o (1)) \sqrt{\ln p \cdot \ln \ln p}) .$

It is a subexponential function, which grows slower than any exponential function. $\ln p$ It is important to emphasize that complexity does not depend on size . $N$ , which makes ECM ideal for finding divisors up to 50–60 decimal digits (about 160–200 bits).

5. Hands-on demos in Google Colab

Below are three scripts that can be run in Google Colab (or locally). They cover key aspects of the theory:

Script 1: Checking the order of an elliptic curve over a prime field and demonstrating Hasse’s theorem.
Script 2: ECM Basic Cycle Simulation – Calculation $k P$ and detection of the divider.
Script 3: Comparison $p - 1$ method and ECM using the example of a number with smooth and non-smooth order.

5.1 Script 1: Group Order and Hasse’s Theorem (Python + SageMath)

# Скрипт для Google Colab (SageMath)
# Устанавливаем SageMath (если используется Colab)
# !pip install sagepython  # в некоторых окружениях

from sage.all import *

def test_hasse(p, a, b):
    """
    Вычисляет порядок E(F_p) для y^2 = x^3 + a x + b
    и проверяет границы Хассе.
    """
    E = EllipticCurve(GF(p), [a, b])
    Np = E.cardinality()
    lower = p + 1 - 2 * sqrt(p)
    upper = p + 1 + 2 * sqrt(p)
    print(f"p = {p}, a = {a}, b = {b}")
    print(f"|E(F_p)| = {Np}")
    print(f"Границы Хассе: [{lower:.2f}, {upper:.2f}]")
    if lower <= Np <= upper:
        print("✅ Теорема Хассе выполняется.")
    else:
        print("❌ Ошибка: порядок вне допустимого интервала.")
    return Np

# Пример: p = 101, кривая y^2 = x^3 + 2x + 3
test_hasse(101, 2, 3)

5.2 Script 2: Basic ECM Simulation with Divider Processing

# Скрипт на чистом Python для Colab
import math, random

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    g, x1, y1 = egcd(b % a, a)
    return g, y1 - (b // a) * x1, x1

def modinv(a, m):
    g, x, _ = egcd(a, m)
    if g != 1:
        return None  # делитель найден
    return x % m

# Упрощённое сложение двух точек на кривой y^2 = x^3 + a*x + b mod N
def add_points(P, Q, a, N):
    x1, y1 = P
    x2, y2 = Q
    if P == Q:
        lam_num = (3 * x1 * x1 + a) % N
        lam_den = (2 * y1) % N
    else:
        lam_num = (y2 - y1) % N
        lam_den = (x2 - x1) % N
    inv = modinv(lam_den, N)
    if inv is None:
        # нашли делитель
        return None, math.gcd(lam_den, N)
    lam = (lam_num * inv) % N
    x3 = (lam * lam - x1 - x2) % N
    y3 = (lam * (x1 - x3) - y1) % N
    return (x3, y3), None

def ecm_step(N, a, b, P, B):
    # вычисляем k = B! (или произведение степеней)
    k = math.factorial(B)  # для демонстрации, но лучше использовать степени простых
    Q = P
    for _ in range(k - 1):
        Q, d = add_points(Q, P, a, N)
        if d is not None and d != N:
            return d
    return None

# Пример: N = 8051 = 83 * 97 (маленький, но для демонстрации)
N = 8051
a, b = 1, 1  # простая кривая
P = (1, 2)   # точка на кривой (проверить, что 4 ≡ 1+1+1 mod N)
B = 20       # малая граница
d = ecm_step(N, a, b, P, B)
print(f"Найденный делитель: {d}")

5.3 Script 3: Comparison $p - 1$ and ECM (SageMath)

# Сравнительный анализ в SageMath
from sage.all import *

def pollard_pm1(N, B):
    # Очень простая версия p-1 метода
    a = 2
    for q in primes(B):
        a = pow(a, q**floor(log(B, q)), N)
    g = gcd(a - 1, N)
    return g if g != 1 and g != N else None

# Сгенерируем N = p * q, где p-1 гладкое, а порядок кривой для ECM — нет.
# Используем p = 1999 (p-1 = 1998 = 2 * 3^3 * 37 — гладкое)
# q = 10007
p = 1999
q = 10007
N = p * q

print(f"Число N = {N} = {p} * {q}")
print("p-1 метод, B=50:", pollard_pm1(N, 50))

# ECM: выберем случайную кривую и точку
E = EllipticCurve(GF(p), [1, 1])  # над полем p, чтобы проверить порядок
ord_p = E.cardinality()
print(f"Порядок E(F_{p}) = {ord_p}, факторизация: {factor(ord_p)}")
# Если порядок негладкий, ECM не сработает с малой границей.
# Для демонстрации можно увеличить B, но это не гарантирует успех.

6. Analysis and conclusions

The provided scripts allow you to clearly see:

How the order of the elliptic curve group obeys Hasse’s theorem;
How can the ECM algorithm find a divisor when an irreversible element occurs during the dot addition process;
Why $p - 1$ the method only works if it is smooth $p - 1$ , while ECM offers a “search” of curves, which gives more chances.

More serious implementations use optimizations: choice $B$ taking into account the size of the divisor, the use of the “extension” method (stage 2), and efficient point representations (projective coordinates). However, the fundamental idea remains unchanged: the variability of the elliptic curve point group makes ECM a flexible and powerful factorization tool.

7. Historical context and records

Since its inception in 1985, the ECM algorithm has repeatedly set records. The largest divisors found are:

Year	Divisor (of decimal digits)	Number
1998	53	$2^{677} - 1$
2005	66	$3^{466} + 1$
2006	67	—
2013	83	—

Modern ECM implementations (e.g., in the GMP-ECM library) are used to handle tails in NFS, which allows for faster factorization of numbers with medium-sized divisors.

Conclusion

Lenstra’s elliptic curve method is a brilliant example of how deep insights from algebraic geometry can be applied to cryptanalysis. Its subexponential complexity, dependence only on the divisor size, and the ability to iterate over curves make it an indispensable tool for information security specialists. The proposed Google Colab scripts not only allow one to reproduce the basic experiments but also serve as a starting point for further research, such as stage 2 implementation, bound optimization, or GPU adaptation.

In the context of Bitcoin and cryptocurrencies, the ECM highlights the importance of choosing curves with a prime group order, which guarantees resistance to smoothness-based attacks. Thus, understanding the ECM is essential not only for breaking RSA but also for the informed design of secure cryptosystems.