Introduction

Every whole number is built from primes. 12 = 2 × 2 × 3. 30 = 2 × 3 × 5. Splitting a number into its prime building blocks is something you learned in school, and for small numbers it feels effortless.

Now try it the other way. Multiply two large primes — say each a few hundred digits long — and you get an even bigger number almost instantly. But hand someone only that result and ask them to recover the two primes? Suddenly the easy schoolyard task becomes one of the hardest problems we know how to pose.

That asymmetry — easy to multiply, brutally hard to undo — is not a curiosity. It is the quiet foundation of RSA, the encryption that has protected online banking, messaging and commerce for decades. The security of a huge slice of the internet rests on the belief that nobody can factor a big enough number in reasonable time.

Break It Down

Try it. Type a number — or pick one of the presets — and hit Factor. The demo uses trial division: test 2, then 3, then 5, 7, 9… dividing out every factor it finds. Watch the step counter.

<p class="hint">Type a number — or pick a preset — and hit <b>Factor</b>. The demo divides out primes one by one and counts every test it makes. Watch how the <b>step count</b> explodes for a <i>semiprime</i> (a product of two big primes).</p>
<div class="row">
  <input id="num" type="text" inputmode="numeric" value="8051" autocomplete="off" />
  <button id="go" type="button">Factor</button>
</div>
<div class="presets">
  <button class="chip" data-n="360" type="button">360 <span>easy</span></button>
  <button class="chip" data-n="8051" type="button">8051 <span>83 × 97</span></button>
  <button class="chip" data-n="99400891" type="button">99,400,891 <span>4-digit primes</span></button>
  <button class="chip" data-n="560008500011" type="button">560,008,500,011 <span>6-digit primes</span></button>
</div>
<div id="out" class="out"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.row { display: flex; gap: .5rem; margin-bottom: .6rem; }
#num { flex: 1; min-width: 0; font: 700 18px ui-monospace, monospace; padding: .5rem .7rem; border: 1px solid #bbb; border-radius: 8px; color: #1d3557; }
button { font: 600 14px system-ui, sans-serif; padding: .5rem 1rem; border: 1px solid #457b9d; background: #457b9d; color: #fff; border-radius: 8px; cursor: pointer; }
.presets { display: flex; flex-wrap: wrap; gap: .4rem; margin-bottom: .8rem; }
.chip { background: #fff; color: #457b9d; border: 1px solid #cdd9e2; font-weight: 600; padding: .35rem .6rem; }
.chip span { color: #888; font-weight: 500; font-size: .8em; margin-left: .25rem; }
.chip:hover { background: #f0f4f8; }
.out { min-height: 3em; }
.factv { font: 800 22px ui-monospace, monospace; color: #1d3557; word-break: break-word; line-height: 1.35; margin: .2rem 0 .5rem; }
.factv .x { color: #999; font-weight: 600; margin: 0 .15rem; }
.factv .p { color: #2a9d8f; }
.meta { font-size: .92rem; color: #444; line-height: 1.5; }
.meta b { color: #c0392b; }
.steps { font-weight: 800; color: #c0392b; }
.tag { display: inline-block; font-size: .8rem; font-weight: 700; padding: .1rem .5rem; border-radius: 99px; margin-left: .4rem; }
.tag.prime { background: #fde8e8; color: #c0392b; }
.tag.semi { background: #fff4e0; color: #b9770e; }
.tag.smooth { background: #e6f6ec; color: #0a7d33; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Integer factorization by trial division — and a live step counter.
// The point: small numbers fall apart instantly; a semiprime (two big primes multiplied) forces the loop almost all the way to sqrt(n).
const STEP_CAP = 80000000; // safety bound so the browser never freezes

function factor(n) {
  const factors = [];
  let steps = 0;
  let capped = false;
  // divide out 2s first
  while (n % 2 === 0) { factors.push(2); n /= 2; steps++; }
  // then odd candidates up to sqrt(n)
  let d = 3;
  while (d * d <= n) {
    steps++;
    if (steps > STEP_CAP) { capped = true; break; }
    if (n % d === 0) { factors.push(d); n /= d; }
    else { d += 2; }
  }
  if (!capped && n > 1) factors.push(n); // leftover prime
  return { factors, steps, capped, remainder: n };
}

function classify(f) {
  if (f.length === 1) return ['prime', 'prime'];
  if (f.length === 2 && f[0] > 3 && f[1] > 3) return ['semi', 'semiprime'];
  return ['smooth', 'composite'];
}

function group(n) { return n.toLocaleString('en-US'); }

function run() {
  const raw = (document.getElementById('num').value || '').replace(/[ ,]/g, '');
  const out = document.getElementById('out');
  const n = Number(raw);
  if (!Number.isInteger(n) || n < 2 || n > 9e15) {
    out.innerHTML = '<p class="meta"><b>Enter a whole number between 2 and 9,000,000,000,000,000.</b></p>';
    return;
  }
  const res = factor(n);
  if (res.capped) {
    out.innerHTML = fmt('<p class="meta">Still searching after <span class="steps"><span class="steps">%group%</span></span> steps — gave up. Smallest factor (if any) is above %group2%. This is exactly why big semiprimes are hard: trial division would need to climb all the way to the square root.</p>', { group: group(STEP_CAP), group2: group(Math.floor(Math.sqrt(n))) });
    return;
  }
  const [cls, name] = classify(res.factors);
  const eq = res.factors.map(p => '<span class="p">' + group(p) + '</span>').join('<span class="x">×</span>');
  let line;
  if (res.factors.length === 1) line = fmt('<span class="p">%group%</span> is prime', { group: group(n) });
  else line = group(n) + '<span class="x">=</span>' + eq;
  out.innerHTML =
    fmt('<div class="factv">%line%<span class="tag %cls%">%name%</span></div><p class="meta">Found in <span class="steps">%group%</span> %v% %v2%</p>', { line: line, cls: cls, name: name, group: group(res.steps), v: res.steps === 1 ? 'step.' : 'steps.', v2: cls === 'semi'
      ? 'A <b>semiprime</b>: the loop had to climb near √n before the first factor appeared. Add a few digits and the steps multiply.'
      : cls === 'prime'
        ? 'No factor below √n, so it is prime — but we only know that after testing every candidate.'
        : 'Lots of small factors, so it fell apart fast.' });
}

document.getElementById('go').addEventListener('click', run);
document.getElementById('num').addEventListener('keydown', e => { if (e.key === 'Enter') run(); });
document.querySelectorAll('.chip').forEach(c =>
  c.addEventListener('click', () => { document.getElementById('num').value = c.dataset.n; run(); }));
run();
Result
Console

Small numbers fall apart instantly. But the semiprimes — products of two primes close in size — are the cruel case: trial division has to climb almost all the way to the square root before it finds the first factor. Bump the size up a few digits and the steps multiply. Now imagine the number is 600 digits long.

The Hard Truth

Here's where factoring sits on the map:

  • Verifying is trivial. Given the factors, just multiply them back — anyone can check a factorization in an instant.
  • Trial division is exponential in the number of digits. Doubling the digits roughly squares the work.
  • The best classical method, the General Number Field Sieve (GNFS), is far cleverer — but still sub-exponential. Factoring a 2048-bit RSA number this way would take longer than the age of the universe on all the computers on Earth combined.
  • It's curiously placed. Factoring is in NP (easy to check) but is not known to be NP-complete and not known to be in P. Most experts believe it's genuinely hard classically — yet no one has proven it.
  • Then quantum changes everything. In 1994 Peter Shor found an algorithm that factors in polynomial time on a quantum computer. A large enough quantum machine would break RSA outright. The hardware isn't there yet — but the clock is ticking.

So factoring is the rare problem that looks safely hard today while a known future technology threatens to dissolve it. Compare that with P vs NP, where we don't even know if a fast method exists.

Where It Matters

The difficulty of factoring isn't an abstract worry — it's load-bearing:

  • RSA and TLS: the padlock in your browser. Public keys are big numbers whose secret primes only the server knows.
  • Digital signatures: software updates, passports and documents are signed with keys whose safety depends on factoring being hard.
  • Banking and payments: card transactions and online banking ride on the same public-key foundations.
  • Secure messaging and VPNs: key exchange historically leaned on factoring-style hardness.

And because Shor's algorithm looms, the world is already moving. Post-quantum cryptography — especially lattice-based schemes that don't rely on factoring — is being standardized right now, so that "harvest now, decrypt later" attacks fail even when quantum computers arrive.

Conclusion

Integer factorization is a perfect lesson in asymmetry. Multiplying is a one-line operation; undoing it can outlast the universe. We took that gap and built the internet's trust on top of it.

But "hard" is always relative to the machine. Trial division gives way to the number field sieve, and the sieve may give way to Shor's algorithm on hardware that doesn't quite exist yet. Factoring reminds us that security is never a permanent property — it's a bet about what tomorrow's computers can do, and a prompt to keep building the next defense before the old one falls.

Share this article

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

Comments

Loading comments...

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