Integer Factorization

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.

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">{{hint}}</p>
<div class="row">
  <input id="num" type="text" inputmode="numeric" value="8051" autocomplete="off" />
  <button id="go" type="button">{{btn_factor}}</button>
</div>
<div class="presets">
  <button class="chip" data-n="360" type="button">360 <span>{{preset_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>{{preset_4digit}}</span></button>
  <button class="chip" data-n="560008500011" type="button">560,008,500,011 <span>{{preset_6digit}}</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; }

// Code not found

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.

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.

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.

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.