The Math Behind RSA #1: Primes and Prime Factorization

This article has a more math-focused version with formal proofs on Folio. Every time you visit an HTTPS website, send a message on Signal, or push to GitHub, RSA (or a close relative) is working behind the scenes. But what actually makes RSA secure? It comes down to one beautifully simple asymmetry: multiplying two primes is trivial; factoring their product is not. This is the first article in a four-part series where we build up the mathematics behind RSA from scratch. No prior number theory knowledge required -- just curiosity and a bit of Python. The Fundamental Asymmetry Try this in your head. Multiply: 127×311=? 127 \times 311 = \text{?} 127×311=? Hard to do mentally, but a computer handles it in nanoseconds. Now go backwards -- factor this number into its two prime components: 39497=?×? 39497 = \text{?} \times \text{?} 39497=?×? Even knowing the answer is two primes, this is significantly harder. You would need to try dividing by candidate primes until something works. And that g