Introduction

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.

Try It

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">Pick a composite number, then press <b>Run ECM</b>. The algorithm tries random elliptic curves over ℤ/nℤ until a point addition fails — and that failure leaks a factor via gcd. Each row is one curve attempt.</p>
<div class="controls">
  <label>Number to factor:
    <select id="nsel">
      <option value="455839">455839 = 599 × 761</option>
      <option value="1234567897">1234567897 = 17 × 73 × 994817</option>
      <option value="15">15 = 3 × 5</option>
      <option value="77">77 = 7 × 11</option>
      <option value="3233">3233 = 53 × 61 (toy RSA)</option>
      <option value="9073">9073 = 43 × 211</option>
    </select>
  </label>
  <button id="run" type="button">Run ECM</button>
  <button id="clr" type="button" class="ghost">Clear</button>
</div>
<div id="result" class="result"></div>
<table id="log">
  <thead><tr><th>#</th><th>Curve (a)</th><th>Point</th><th>GCD found</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Lenstra ECM demo — pure vanilla JS, BigInt arithmetic.
// We work with BigInt throughout. The algorithm:
//   1. Pick random curve y^2 = x^3 + a*x + b (mod n) via random point (x0,y0,a).
//      b is determined: b = y0^2 - x0^3 - a*x0 (mod n).
//   2. Compute k * P using the group law, where k = B1-smooth number (product of
//      small prime powers fitting in a "stage 1" bound). Here we use k = lcm(1..B).
//   3. During each doubling/addition, the modular inverse may fail (gcd(denom, n) > 1).
//      That gcd is a non-trivial factor of n — success!
//   4. If we finish stage 1 without failure, the curve is "unlucky" — try another.

const B = 30; // stage-1 bound (small for demo speed; real ECM uses B1~1e6)

function bigRand(max) {
  // Random BigInt in [0, max)
  const bits = max.toString(2).length;
  let r;
  do {
    let v = 0n;
    for (let i = 0; i < bits; i += 32)
      v = (v << 32n) | BigInt(Math.floor(Math.random() * 0x100000000));
    r = v & ((1n << BigInt(bits)) - 1n);
  } while (r >= max);
  return r;
}

function mod(a, n) { return ((a % n) + n) % n; }

// Extended GCD: returns [g, x, y] s.t. a*x + b*y = g
function egcd(a, b) {
  if (b === 0n) return [a, 1n, 0n];
  const [g, x1, y1] = egcd(b, mod(a, b));
  return [g, y1, x1 - (a / b) * y1];
}

function gcd(a, b) { a = a < 0n ? -a : a; b = b < 0n ? -b : b; while (b) { [a, b] = [b, a % b]; } return a; }

// Modular inverse of a mod n. Returns null if gcd(a,n) > 1 (signals factor found).
function modinv(a, n) {
  a = mod(a, n);
  const [g, x] = egcd(a, n);
  if (g !== 1n) return { factor: g }; // gcd leaked a factor!
  return mod(x, n);
}

// Point on curve y^2 = x^3 + a*x + b (mod n). null = point at infinity.
function pointAdd(P, Q, a, n) {
  if (P === null) return Q;
  if (Q === null) return P;
  let lam;
  if (P[0] === Q[0]) {
    if (P[1] !== Q[1]) return null; // P = -Q
    // doubling: lam = (3x^2 + a) / (2y)
    const num = mod(3n * P[0] * P[0] + a, n);
    const den = mod(2n * P[1], n);
    const inv = modinv(den, n);
    if (inv && inv.factor) return inv; // factor found!
    lam = mod(num * inv, n);
  } else {
    const num = mod(Q[1] - P[1], n);
    const den = mod(Q[0] - P[0], n);
    const inv = modinv(den, n);
    if (inv && inv.factor) return inv;
    lam = mod(num * inv, n);
  }
  const x = mod(lam * lam - P[0] - Q[0], n);
  const y = mod(lam * (P[0] - x) - P[1], n);
  return [x, y];
}

// Scalar multiplication k*P using double-and-add.
function scalarMul(k, P, a, n) {
  let R = null, Q = P;
  while (k > 0n) {
    if (k & 1n) {
      const res = pointAdd(R, Q, a, n);
      if (res && res.factor) return res;
      R = res;
    }
    const res2 = pointAdd(Q, Q, a, n);
    if (res2 && res2.factor) return res2;
    Q = res2;
    k >>= 1n;
  }
  return R;
}

// Compute k = product of prime powers <= B (lcm(1..B) approximation via primes)
function stageK(B) {
  // Sieve of Eratosthenes for primes <= B
  const sieve = Array(B + 1).fill(true);
  sieve[0] = sieve[1] = false;
  for (let i = 2; i <= B; i++) if (sieve[i]) for (let j = 2*i; j <= B; j += i) sieve[j] = false;
  let k = 1n;
  for (let p = 2; p <= B; p++) {
    if (!sieve[p]) continue;
    let q = p;
    while (q <= B) q *= p;
    q /= p;
    k *= BigInt(q);
  }
  return k;
}

const K = stageK(B);

// Run one ECM attempt on n. Returns {factor} or null.
function ecmOnce(n) {
  const x0 = bigRand(n - 2n) + 1n;
  const y0 = bigRand(n - 2n) + 1n;
  const a  = bigRand(n - 2n) + 1n;
  // b = y0^2 - x0^3 - a*x0 (mod n) — we don't need b explicitly in computation
  const P = [x0, y0];
  const res = scalarMul(K, P, a, n);
  if (res && res.factor) {
    const f = res.factor;
    if (f > 1n && f < n) return { factor: f, a, x0, y0 };
  }
  return { factor: null, a, x0, y0 };
}

const MAX_CURVES = 40;

let running = false;

document.getElementById('run').addEventListener('click', async () => {
  if (running) return;
  running = true;
  const n = BigInt(document.getElementById('nsel').value);
  const tbody = document.querySelector('#log tbody');
  const resultEl = document.getElementById('result');
  tbody.innerHTML = '';
  resultEl.textContent = 'Trying curves…';
  resultEl.className = 'result';

  // Quick check: if n is prime, bail out
  if (n < 4n) { resultEl.textContent = 'n must be composite.'; running = false; return; }
  const trivial = gcd(n, 6n);
  let earlyFactor = null;
  if (trivial > 1n && trivial < n) earlyFactor = trivial;

  if (earlyFactor) {
    resultEl.textContent = fmt('Trivial factor: %earlyFactor% (gcd with 6)', { earlyFactor: earlyFactor });
    resultEl.className = 'result ok';
    running = false;
    return;
  }

  let found = null;
  for (let i = 1; i <= MAX_CURVES && !found; i++) {
    // Yield to browser between iterations
    await new Promise(r => setTimeout(r, 0));
    const res = ecmOnce(n);
    const tr = document.createElement('tr');
    const g = res.factor;
    if (g && g > 1n && g < n) {
      found = g;
      tr.className = 'hit';
      tr.innerHTML = fmt('<td>%i%</td><td>%a%</td><td>(%x0%, %y0%)</td><td>%g%</td><td>✓ Factor found!</td>', { i: i, a: res.a, x0: res.x0, y0: res.y0, g: g });
    } else {
      tr.className = 'miss';
      tr.innerHTML = fmt('<td>%i%</td><td>%a%</td><td>(%x0%, %y0%)</td><td>1 or n</td><td>No luck</td>', { i: i, a: res.a, x0: res.x0, y0: res.y0 });
    }
    tbody.appendChild(tr);
  }

  if (found) {
    const other = n / found;
    resultEl.textContent = `✓  ${n} = ${found} × ${other}`;
    resultEl.className = 'result ok';
    console.log(fmt('ECM factored %n% = %found% × %other%', { n: n, found: found, other: other }));
  } else {
    resultEl.textContent = fmt('No factor found in %MAX_CURVES% curves (try again).', { MAX_CURVES: MAX_CURVES });
    resultEl.className = 'result bad';
  }
  running = false;
});

document.getElementById('clr').addEventListener('click', () => {
  document.querySelector('#log tbody').innerHTML = '';
  document.getElementById('result').textContent = '';
  document.getElementById('result').className = 'result';
});
Result
Console

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.

The Real Complexity

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

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/lenstra-ecm/Content licensed under CC BY-NC 4.0.