Elliptic curve factorization (statement)

Setup. Choose a random elliptic curve $E$ over $\mathbb{Z}/n\mathbb{Z}$ and a point $P$. Compute $kP$ via repeated doubling/addition.

Factorization. At some step, a denominator is not invertible mod $n$, meaning $\gcd(\text{denominator},n)$ is a nontrivial factor of $n$.

Efficiency. ECM is particularly efficient for finding small factors; complexity depends on the size of the smallest factor, not $n$.

Conclusion. ECM is a major modern factorization algorithm, well-suited to finding medium-size factors.