Lenstra's ECM

Factor the number 455839. You could try every prime up to its square root — that is trial division, and it works fine for small numbers. But what if the number has 100 digits? Trial division would take longer than the age of the universe.

In 1987, the mathematician Hendrik Lenstra Jr. published an algorithm that finds prime factors far more efficiently by doing arithmetic on elliptic curves — the same exotic objects that now underpin much of modern cryptography. The trick is that elliptic-curve arithmetic can fail in a very revealing way: when it does, a factor of your number falls out almost as a side effect.

ECM (Elliptic Curve Method) is the world's best algorithm for finding medium-sized factors (up to about 50–60 digits). For integers where no small factor exists, harder algorithms like the General Number Field Sieve take over. ECM is a key component of virtually every serious factoring effort today.

Choose a composite number and watch ECM hunt for a factor. The algorithm picks a random elliptic curve, does arithmetic modulo your number, and waits for a greatest common divisor to escape from 1. When the GCD hits a non-trivial value, it is a factor.

<p class="hint">{{hint}}</p>
<div class="controls">
  <label>{{label_number}}
    <select id="nsel">
      <option value="455839">{{opt_455839}}</option>
      <option value="1234567897">{{opt_1234567897}}</option>
      <option value="15">{{opt_15}}</option>
      <option value="77">{{opt_77}}</option>
      <option value="3233">{{opt_3233}}</option>
      <option value="9073">{{opt_9073}}</option>
    </select>
  </label>
  <button id="run" type="button">{{btn_run}}</button>
  <button id="clr" type="button" class="ghost">{{btn_clear}}</button>
</div>
<div id="result" class="result"></div>
<table id="log">
  <thead><tr><th>{{th_num}}</th><th>{{th_curve}}</th><th>{{th_point}}</th><th>{{th_gcd}}</th><th>{{th_outcome}}</th></tr></thead>
  <tbody></tbody>
</table>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: .93rem; }
.hint { color: #444; margin: 0 0 .6rem; line-height: 1.45; font-size: .88rem; }
.controls { display: flex; gap: .5rem; flex-wrap: wrap; align-items: center; margin-bottom: .6rem; }
label { font-size: .88rem; display: flex; gap: .35rem; align-items: center; }
select { font: inherit; padding: .25rem .4rem; border: 1px solid #aaa; border-radius: 6px; background: #fff; }
button { font: 600 13px system-ui; padding: .38rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.result { font-weight: 700; font-size: 1.05rem; min-height: 1.5em; margin-bottom: .4rem; }
.result.ok { color: #0a7d33; }
.result.bad { color: #c92f3c; }
table { width: 100%; border-collapse: collapse; font-size: .82rem; }
th { background: #e8eef3; padding: .3rem .45rem; text-align: left; border-bottom: 2px solid #cdd9e3; }
td { padding: .25rem .45rem; border-bottom: 1px solid #e2e7ec; }
tr.hit td { background: #d4f0dc; font-weight: 600; }
tr.miss td { color: #888; }

// Code not found

Notice: the same number may require many curve attempts before one leaks a factor. Each new curve is an independent lottery ticket. The expected number of curves depends only on the size of the smallest prime factor — not on the size of the number itself. That is ECM's magic: small factors are found quickly no matter how large the surrounding number is.

How fast is ECM, really? The answer depends on what you are looking for, not just the size of the number.

• Trial division finds a factor $p$ in $O(\sqrt{p})$ steps — doubling the size of $p$ squares the work.
• Pollard's rho does better: $O(p^{1/4})$ steps — but still exponential in the number of digits of $p$.
• Lenstra's ECM runs in $L_p[1/2, \sqrt{2}]$ expected steps, where $L_p[s, c] = e^{c(\ln p)^s (\ln \ln p)^{1-s}}$. This is sub-exponential in the size of $p$ — it blows away both trial division and Pollard's rho for factors of 20 digits or more.
• The catch: ECM's complexity depends on $p$, the factor, not on $n$, the number being factored. Once factors exceed about 60 digits, the General Number Field Sieve (which has complexity sub-exponential in $n$) is preferred.

Integer factoring itself has no proven lower bound beyond trivial. No polynomial-time algorithm is known, and if one existed it would break RSA cryptography. The existence of ECM shows that factoring is at least not as hard as brute force — but where it truly sits in the complexity landscape remains an open question tied directly to P vs NP.

ECM is not just an academic curiosity — it shapes the real world of cryptography and number theory:

• Cryptographic key validation: before deploying an RSA key, security libraries run ECM to confirm its factors are large enough that no medium-size shortcut exists.
• Factoring records: ECM holds records for the largest factors found as part of big factoring projects (like GIMPS and NFS@Home). Finding a 60-digit factor of a 200-digit number is ECM's specialty.
• Primality proving: ECM generates large primes used in Atkin–Morain ECPP (Elliptic Curve Primality Proving), the algorithm behind most cryptographic prime certificates.
• Breaking weak keys: auditing TLS certificates and PGP keys for weak primes is done with ECM at scale.
• Pure mathematics: ECM contributed to factoring specific Fermat numbers and Cunningham numbers that had resisted effort for decades.

Understand ECM and you understand why cryptographers insist on 2048-bit RSA keys — a key whose factors have fewer than 60 digits is vulnerable in ways that mere key length does not reveal.

Lenstra's ECM inverts the usual idea of what an algorithm should do. Most algorithms are designed to never fail. ECM deliberately aims for a controlled failure — an arithmetic crash in modular elliptic-curve arithmetic — and reads the factor right out of the wreckage.

The elegance is that you can try as many curves as you like, and each one is an independent chance to expose the factor. Fail a thousand times and try curve 1001; the factor does not move, but your odds keep improving. It is randomness used not as a last resort but as the very engine of discovery.

If you want to understand why factoring is hard for large factors but surprisingly tractable for medium ones, ECM is the clearest window into that distinction. And the next time you generate an RSA key, remember: somewhere under the hood, a curve is being tried.