DEV Community: zuka3

The Math Behind RSA #4: Breaking RSA and the Rise of Elliptic Curve Cryptography

zuka3 — Mon, 30 Mar 2026 01:53:50 +0000

This article has a more math-focused version with formal proofs on Folio.

In the previous three parts, we built RSA from the ground up: modular arithmetic, Euler's theorem, and a working Python implementation. Now we tear it all down. This final article explores why RSA is showing its age, how elliptic curve cryptography (ECC) offers a compelling alternative, and what the quantum future holds.

Part I: Attacks on RSA

The Factoring Arms Race

RSA's security rests on a single assumption: factoring the product of two large primes is computationally hard. But "hard" is a moving target.

Trial Division — The naive approach tests every integer up to $n\sqrt{n}$ . For a 2048-bit modulus, that means checking roughly $2^{1024}$ candidates. Completely infeasible.

Fermat's Factorization — If $p$ and $q$ are close together, we can write $n = a^2 - b^2 = (a+b)(a-b)$ and search for $a$ near $n\sqrt{n}$ . This is why good RSA implementations ensure $∣ p - q ∣$ is large.

Quadratic Sieve (QS) — Introduced in 1981, QS was the fastest general-purpose factoring algorithm for decades. Its sub-exponential runtime is approximately:

L_n!\left[\tfrac{1}{2},\, 1\right] = e^{(1+o(1))\sqrt{\ln n \cdot \ln \ln n}}

General Number Field Sieve (GNFS) — The current champion, with heuristic complexity:

L_n!\left[\tfrac{1}{3},\, \left(\tfrac{64}{9}\right)^{1/3}\right] = e^{\left(\left(\frac{64}{9}\right)^{1/3}+o(1)\right)(\ln n)^{1/3}(\ln \ln n)^{2/3}}

In 2020, a team factored RSA-250 (829 bits) using GNFS. The trend is clear: factoring records keep falling.

Year	Record	Bits
1999	RSA-155	512
2005	RSA-200	663
2009	RSA-768	768
2020	RSA-250	829

Side-Channel Attacks

Even with a large key, the implementation can leak secrets:

Timing attacks: Measuring how long decryption takes can reveal bits of the private key. If a 1 bit in the exponent triggers an extra multiplication, the time difference is measurable.
Power analysis: Monitoring a hardware device's power consumption during RSA operations can expose the exponent bit by bit.
Fault injection: Inducing a computational error during signing and comparing the faulty signature with a correct one can factor $n$ directly (Boneh-DeMillo-Lipton attack).

Padding Oracle Attacks

Raw textbook RSA ( $m^e \bmod n$ ) is deterministic — the same plaintext always produces the same ciphertext. This enables:

Bleichenbacher's attack (1998): Against PKCS#1 v1.5 padding. By sending thousands of crafted ciphertexts and observing which ones the server accepts as "correctly padded," an attacker can decrypt any message. This motivated the move to OAEP padding.
Chosen-ciphertext malleability: Given $m^e \bmod n$ , an attacker computes $\cdot s^e \bmod n$ , which decrypts to $\cdot s \bmod n$ .

Part II: The Key Length Problem

As factoring algorithms improve, RSA keys must grow. Here is what NIST recommends for equivalent security levels:

Security (bits)	RSA key size	ECC key size	Ratio
80	1024	160	6.4x
112	2048	224	9.1x
128	3072	256	12x
192	7680	384	20x
256	15360	512	30x

At the 256-bit security level, RSA needs a 15,360-bit key. That is 1,920 bytes just for the modulus. Key generation, signing, and decryption all slow to a crawl. This is the fundamental scaling problem that drives the shift to elliptic curves.

Part III: Introduction to Elliptic Curves

An elliptic curve over a field $Fp\mathbb{F}_p$ (where $p$ is a large prime) is the set of points $(x, y)$ satisfying:

y^2 \equiv x^3 + ax + b \pmod{p}

together with a special "point at infinity" $O\mathcal{O}$ , provided the discriminant $4a3+27b2≢0(modp)4a^3 + 27b^2 \not\equiv 0 \pmod{p}$ (which ensures no singularities).

Group Structure

The remarkable fact: the points on an elliptic curve form an abelian group under a geometric addition law.

Identity: The point at infinity $O\mathcal{O}$ serves as the identity element.
Inverse: The inverse of $(x, y)$ is $(x, - y)$ .
Addition: For two distinct points $P = (x_1, y_1)$ and $Q = (x_2, y_2)$ , the sum $R = P + Q = (x_3, y_3)$ is computed by drawing a line through $P$ and $Q$ , finding the third intersection with the curve, and reflecting over the x-axis.

The formulas (mod $p$ ):

\lambda = \frac{y_2 - y_1}{x_2 - x_1}, \quad x_3 = \lambda^2 - x_1 - x_2, \quad y_3 = \lambda(x_1 - x_3) - y_1

For point doubling ( $P = Q$ ):

\lambda = \frac{3x_1^2 + a}{2y_1}

Part IV: Python Implementation

Let's implement elliptic curve arithmetic from scratch.

class EllipticCurve:
    """An elliptic curve y^2 = x^3 + ax + b over F_p."""

    def __init__(self, a, b, p):
        self.a = a
        self.b = b
        self.p = p
        assert (4 * a**3 + 27 * b**2) % p != 0, "Singular curve"

    def is_on_curve(self, point):
        if point is None:  # Point at infinity
            return True
        x, y = point
        return (y * y - (x**3 + self.a * x + self.b)) % self.p == 0

    def point_add(self, P, Q):
        """Add two points on the curve."""
        if P is None:
            return Q
        if Q is None:
            return P

        x1, y1 = P
        x2, y2 = Q

        if x1 == x2 and (y1 + y2) % self.p == 0:
            return None  # P + (-P) = O

        if P == Q:
            # Point doubling
            lam = (3 * x1 * x1 + self.a) * pow(2 * y1, -1, self.p) % self.p
        else:
            # Point addition
            lam = (y2 - y1) * pow(x2 - x1, -1, self.p) % self.p

        x3 = (lam * lam - x1 - x2) % self.p
        y3 = (lam * (x1 - x3) - y1) % self.p
        return (x3, y3)

    def scalar_mult(self, k, P):
        """Compute k * P using double-and-add."""
        result = None  # Point at infinity
        addend = P

        while k:
            if k & 1:
                result = self.point_add(result, addend)
            addend = self.point_add(addend, addend)
            k >>= 1

        return result

The scalar_mult method uses the double-and-add algorithm — the elliptic curve analog of fast modular exponentiation. Computing $\cdot P$ takes $O(log⁡k)O(\log k)$ group operations.

A Quick Test

# secp256k1 parameters (used in Bitcoin)
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a = 0
b = 7
G = (
    0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,
    0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8,
)

curve = EllipticCurve(a, b, p)
assert curve.is_on_curve(G)

# Compute 2G
G2 = curve.scalar_mult(2, G)
print(f"2G = ({hex(G2[0])}, {hex(G2[1])})")
assert curve.is_on_curve(G2)

Part V: ECDH Key Exchange

Elliptic Curve Diffie-Hellman lets two parties agree on a shared secret over an insecure channel. It is the ECC counterpart to classical Diffie-Hellman.

import secrets

def ecdh_keygen(curve, G, n):
    """Generate an ECDH key pair."""
    private_key = secrets.randbelow(n - 1) + 1  # random in [1, n-1]
    public_key = curve.scalar_mult(private_key, G)
    return private_key, public_key

# Curve order for secp256k1
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

# Alice generates her key pair
alice_priv, alice_pub = ecdh_keygen(curve, G, n)

# Bob generates his key pair
bob_priv, bob_pub = ecdh_keygen(curve, G, n)

# Both compute the shared secret
shared_alice = curve.scalar_mult(alice_priv, bob_pub)   # alice_priv * bob_pub
shared_bob   = curve.scalar_mult(bob_priv, alice_pub)   # bob_priv * alice_pub

assert shared_alice == shared_bob
print("Shared secret established!")
print(f"  x = {hex(shared_alice[0])}")

Alice computes $\cdot (bG) = abG$ . Bob computes $\cdot (aG) = abG$ . They arrive at the same point. An eavesdropper sees $a G$ and $b G$ but cannot compute $ab G$ without solving the Elliptic Curve Discrete Logarithm Problem (ECDLP).

Part VI: Why ECDLP Is Harder Than Factoring

The best known classical algorithms for the two problems scale very differently:

	Integer Factoring (RSA)	ECDLP (ECC)
Best algorithm	GNFS	Pollard's rho
Complexity class	Sub-exponential	Fully exponential
Time ( $n$ -bit key)	$e^{O(n^{1/3} \log^{2/3} n)}$	$O(2^{n/2})$
128-bit security	3072-bit key	256-bit key
Index calculus	Applies	No known analog

The critical difference is that index calculus methods — the family of techniques behind QS and GNFS — have no known efficient analog for elliptic curves over prime fields. Transferring the discrete logarithm from an elliptic curve to a finite field where index calculus works requires solving the ECDLP itself (outside of special weak-curve cases).

This means that for elliptic curves, we are stuck with generic algorithms like Pollard's rho, which run in $O(n)O(\sqrt{n})$ where $n$ is the group order. A 256-bit curve provides roughly 128 bits of security — matching AES-128 — with dramatically smaller keys.

Part VII: The Quantum Threat

Shor's Algorithm

In 1994, Peter Shor showed that a sufficiently large quantum computer can factor integers and compute discrete logarithms in polynomial time:

O((\log n)^2 (\log \log n)(\log \log \log n))

This breaks both RSA and ECC. The algorithm works by reducing factoring to period-finding, which quantum computers solve efficiently via the Quantum Fourier Transform. For ECC, a variant of Shor's algorithm solves the ECDLP with similar efficiency.

Current status: As of 2025, the largest number factored by a quantum computer using Shor's algorithm is 21. We are far from threatening RSA-2048. But the field is advancing rapidly, and the "harvest now, decrypt later" threat is real — adversaries can store encrypted traffic today and decrypt it once quantum computers mature.

Post-Quantum Cryptography

NIST finalized its first post-quantum standards in 2024:

ML-KEM (CRYSTALS-Kyber): A lattice-based key encapsulation mechanism. Its security rests on the hardness of the Module Learning With Errors (MLWE) problem.
ML-DSA (CRYSTALS-Dilithium): A lattice-based digital signature scheme.
SLH-DSA (SPHINCS+): A hash-based signature scheme — conservative, stateless, and relying only on hash function security.

The core idea behind lattice-based cryptography: given a "noisy" system of linear equations over a lattice, finding the secret vector is believed hard even for quantum computers.

\mathbf{b} = \mathbf{A}\mathbf{s} + \mathbf{e} \pmod{q}

where $e\mathbf{e}$ is a small error vector. Without the error, this is simple linear algebra. With it, the problem becomes intractable.

Part VIII: RSA vs ECC — Full Comparison

Feature	RSA	ECC
Hard problem	Integer factoring	ECDLP
Key size (128-bit security)	3072 bits	256 bits
Signature size	3072 bits	512 bits
Key generation speed	Slow (primality testing)	Fast
Signing speed	Moderate	Fast
Verification speed	Fast (small $e$ )	Moderate
Bandwidth efficiency	Poor	Excellent
Quantum resistance	None	None
Standardization maturity	Decades	~15 years in TLS
Patent concerns	Expired	Mostly resolved
IoT / embedded suitability	Poor	Excellent

The bottom line: for new systems, ECC is the default choice. RSA remains widespread in legacy systems and in contexts where its simplicity and fast verification are valued (e.g., certificate chains). Neither survives a quantum computer, so the long-term future belongs to post-quantum schemes.

Folio: The Full Mathematical Treatment

I wrote this series on Dev.to for the code-focused approach, but for the rigorous math — formal proofs, theorem environments, cross-references — I've published a more detailed version on Folio's number theory series. There you'll find complete proofs of Euler's theorem, the Chinese Remainder Theorem, formal security reductions, and the algebraic geometry behind elliptic curves — all typeset with proper LaTeX.

Series Summary

Over four articles, we've traced the full arc of public-key cryptography:

#1 — Modular Arithmetic: The foundation. We built intuition for congruences, modular inverses, and the structure of $Z/nZ\mathbb{Z}/n\mathbb{Z}$ .
#2 — Euler's Theorem and Key Generation: We proved why RSA works — that $med≡m(modn)m^{ed} \equiv m \pmod{n}$ — and implemented key generation in Python.
#3 — Encryption, Signatures, and Attacks: We built a complete RSA system with OAEP padding, digital signatures, and explored common implementation pitfalls.
#4 — Breaking RSA and Elliptic Curves (this article): We examined RSA's weaknesses, implemented elliptic curve cryptography from scratch, and looked ahead to the post-quantum era.

The story of RSA is ultimately a story about the relationship between mathematics and computation. What is "hard" today may not be tomorrow. The algorithms we trust are only as strong as the problems they hide behind — and finding those problems, understanding their difficulty, and building systems around them is one of the most fascinating intersections of pure math and engineering.

Thanks for reading the series. If you have questions or spot errors, drop a comment below.

Enjoyed this series? Follow me for more articles on the mathematics of computer science. The full version with formal proofs is available on Folio.

The Math Behind RSA #3: Implementing RSA from Scratch in Python

zuka3 — Thu, 26 Mar 2026 01:48:56 +0000

This article has a more math-focused version with formal proofs on Folio.

In the first two parts of this series, we built up the number theory toolkit: modular arithmetic, Euler's totient function, the extended Euclidean algorithm, and Fermat's little theorem. Now it's time to put all of that to work and implement RSA from scratch in Python.

By the end of this article you will have a working RSA implementation, understand why each mathematical piece is needed, and see a formal proof that decryption actually recovers the original message.

RSA in Three Steps

The entire RSA cryptosystem reduces to three operations:

Key Generation -- produce a public key $(n, e)$ and a private key $(n, d)$ .
Encryption -- given plaintext $m$ , compute ciphertext $m^e \bmod n$ .
Decryption -- given ciphertext $c$ , recover $c^d \bmod n$ .

The security rests on one assumption: given $n = pq$ , it is computationally infeasible to factor $n$ back into $p$ and $q$ when the primes are large enough.

Recap: Helper Functions from Parts #1 and #2

We need three building blocks that we derived in earlier articles. Here they are as Python functions.

Greatest Common Divisor

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

Extended Euclidean Algorithm

Returns $(g, x, y)$ such that $\gcd(a, b)$ .

def extended_gcd(a, b):
    if a == 0:
        return b, 0, 1
    g, x1, y1 = extended_gcd(b % a, a)
    return g, y1 - (b // a) * x1, x1

Modular Inverse

Using the extended GCD, we can find $ϕ(n)e^{-1} \bmod \phi(n)$ :

def mod_inverse(e, phi):
    g, x, _ = extended_gcd(e % phi, phi)
    if g != 1:
        raise ValueError("Modular inverse does not exist")
    return x % phi

Miller-Rabin Primality Test

We need a way to find large primes. Miller-Rabin is probabilistic but extremely reliable with enough rounds:

import random

def is_prime(n, rounds=40):
    if n < 2:
        return False
    if n < 4:
        return True
    if n % 2 == 0:
        return False
    # Write n-1 as 2^r * d
    r, d = 0, n - 1
    while d % 2 == 0:
        r += 1
        d //= 2
    for _ in range(rounds):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

def generate_prime(bits):
    while True:
        p = random.getrandbits(bits) | (1 << (bits - 1)) | 1
        if is_prime(p):
            return p

Key Generation

def generate_keypair(bits=1024):
    p = generate_prime(bits // 2)
    q = generate_prime(bits // 2)
    n = p * q
    phi = (p - 1) * (q - 1)

    e = 65537
    assert gcd(e, phi) == 1, "e and phi(n) are not coprime; regenerate primes"

    d = mod_inverse(e, phi)

    return {
        "public": (n, e),
        "private": (n, d),
        "_p": p,
        "_q": q,
    }

Why e = 65537?

The public exponent $e$ must satisfy $\phi(n)$ and $gcd⁡(e,ϕ(n))=1\gcd(e, \phi(n)) = 1$ . In theory, any such $e$ works. In practice, nearly every RSA implementation uses $e = 65537 = 2^{16} + 1$ for two reasons:

Speed -- its binary representation 10000000000000001 has only two set bits, making modular exponentiation via square-and-multiply very fast (just 17 squarings and 1 multiplication).
Security -- small exponents like $e = 3$ are vulnerable to certain attacks (e.g. Coppersmith's attack on low public exponents) when messages are short or padding is absent.

Encryption and Decryption

With the keys in hand, encryption and decryption are each a single modular exponentiation:

def encrypt(plaintext_int, public_key):
    n, e = public_key
    if plaintext_int >= n:
        raise ValueError("Message must be less than n")
    return pow(plaintext_int, e, n)

def decrypt(ciphertext_int, private_key):
    n, d = private_key
    return pow(ciphertext_int, d, n)

Python's built-in pow(base, exp, mod) uses fast modular exponentiation internally, so this is efficient even for 2048-bit numbers.

Quick Test

keys = generate_keypair(512)  # small for demo purposes
pub, priv = keys["public"], keys["private"]

message = 42
cipher = encrypt(message, pub)
plain = decrypt(cipher, priv)

assert plain == message
print(f"Original:  {message}")
print(f"Encrypted: {cipher}")
print(f"Decrypted: {plain}")

Proof of Correctness

Why does decrypting an encrypted message give back the original? This is where Euler's theorem from Part #2 pays off.

Claim. For any $m$ with $\le m < n$ , we have $med≡m(modn)m^{ed} \equiv m \pmod{n}$ .

Proof. By construction, $\equiv 1 \pmod{\phi(n)}$ , so there exists an integer $k$ such that:

k\,\phi(n)

Case 1: $gcd⁡(m,n)=1\gcd(m, n) = 1$ . Euler's theorem gives us $mϕ(n)≡1(modn)m^{\phi(n)} \equiv 1 \pmod{n}$ . Therefore:

m^{ed} = m^{1 + k\,\phi(n)} = m \cdot (m^{\phi(n)})^k \equiv m \cdot 1^k = m \pmod{n}

Case 2: $gcd⁡(m,n)≠1\gcd(m, n) \ne 1$ . Since $n = pq$ with distinct primes $p, q$ , if $gcd⁡(m,n)≠1\gcd(m, n) \ne 1$ then $\mid m$ or $\mid m$ (but not both, since $m < n$ ). Suppose $\mid m$ . Then $med≡0≡m(modp)m^{ed} \equiv 0 \equiv m \pmod{p}$ . Meanwhile, $gcd⁡(m,q)=1\gcd(m, q) = 1$ , so by Fermat's little theorem, $mq−1≡1(modq)m^{q-1} \equiv 1 \pmod{q}$ . Since $\mid \phi(n)$ , the same argument gives $med≡m(modq)m^{ed} \equiv m \pmod{q}$ . Combining via the Chinese Remainder Theorem:

m^{ed} \equiv m \pmod{n} \qquad \blacksquare

CRT Optimization: 4x Speedup

In production RSA, the private key holder knows $p$ and $q$ . Instead of computing $nc^d \bmod n$ directly (which operates on a number with $b$ bits), we can split the computation using the Chinese Remainder Theorem and work with numbers of $b /2$ bits:

def decrypt_crt(ciphertext, p, q, d):
    dp = d % (p - 1)
    dq = d % (q - 1)
    q_inv = mod_inverse(q, p)

    m1 = pow(ciphertext, dp, p)
    m2 = pow(ciphertext, dq, q)

    h = (q_inv * (m1 - m2)) % p
    return m2 + h * q

Why is this roughly 4x faster? Modular exponentiation with a $b$ -bit modulus and a $b$ -bit exponent takes roughly $O(b^3)$ time. Splitting into two $b /2$ -bit operations gives:

\times O!\left(\left(\frac{b}{2}\right)^3\right) = 2 \times \frac{O(b^3)}{8} = \frac{O(b^3)}{4}

That is a 4x speedup -- significant when you are doing thousands of decryptions per second on a server.

Verify CRT produces the same result

keys = generate_keypair(1024)
pub, priv = keys["public"], keys["private"]
p, q = keys["_p"], keys["_q"]

message = 123456789
cipher = encrypt(message, pub)

plain_standard = decrypt(cipher, priv)
plain_crt = decrypt_crt(cipher, p, q, priv[1])

assert plain_standard == plain_crt
print("CRT decryption matches standard decryption.")

String Encryption Demo

Real messages are strings, not single integers. Here is a simple demo that converts a string to an integer and back. (Production systems use proper padding schemes -- see the comparison table below.)

def str_to_int(s):
    return int.from_bytes(s.encode("utf-8"), "big")

def int_to_str(i):
    length = (i.bit_length() + 7) // 8
    return i.to_bytes(length, "big").decode("utf-8")

# Generate keys (2048-bit for realistic string lengths)
keys = generate_keypair(2048)
pub, priv = keys["public"], keys["private"]

message = "Hello, RSA!"
m = str_to_int(message)

cipher = encrypt(m, pub)
decrypted_int = decrypt(cipher, priv)
decrypted_msg = int_to_str(decrypted_int)

print(f"Original:  {message}")
print(f"Encrypted: {cipher}")
print(f"Decrypted: {decrypted_msg}")
assert decrypted_msg == message

Our Implementation vs. Production RSA

Our implementation is mathematically correct but not safe for production use. Here is what real libraries add:

Aspect	Our Implementation	Production RSA (e.g. OpenSSL)
Key size	512-2048 bit demo	2048-4096 bit minimum
Padding	None (textbook RSA)	OAEP (PKCS#1 v2.2)
Prime generation	Probabilistic (Miller-Rabin)	Miller-Rabin + additional checks
Side-channel protection	None	Constant-time operations, blinding
CRT decryption	Optional	Always used, with fault checks
Key storage	Plain Python dict	Hardware security modules (HSMs)
Random source	`random` module	OS-level CSPRNG (`/dev/urandom`)
Signature support	Not implemented	PSS padding (PKCS#1 v2.2)

Critical differences to understand:

Textbook RSA is deterministic: encrypting the same message twice produces the same ciphertext, which leaks information. OAEP padding adds randomness.
Side-channel attacks: our pow() call has data-dependent timing. Production implementations use constant-time modular exponentiation and RSA blinding.
The random module is not cryptographically secure. Use secrets or os.urandom for real applications.

Putting It All Together

All the code above composes into a single file. Concatenate the helper functions (gcd, extended_gcd, mod_inverse, is_prime, generate_prime), the core functions (generate_keypair, encrypt, decrypt, decrypt_crt), and the string utilities (str_to_int, int_to_str). Then run:

if __name__ == "__main__":
    keys = generate_keypair(2048)
    pub, priv = keys["public"], keys["private"]

    msg = "Hello, RSA!"
    m = str_to_int(msg)
    c = encrypt(m, pub)
    assert int_to_str(decrypt(c, priv)) == msg
    assert decrypt_crt(c, keys["_p"], keys["_q"], priv[1]) == m
    print(f"Original:  {msg}")
    print(f"Encrypted: {c}")
    print(f"Decrypted: {int_to_str(decrypt(c, priv))}")
    print("All assertions passed.")

What's Next

We now have a fully working RSA implementation and a proof that it is mathematically correct. But how secure is it really? In Part #4, we will explore:

Practical limitations of RSA: key size growth, performance costs, and why RSA is rarely used to encrypt data directly.
Known attacks: Wiener's attack on small $d$ , Bleichenbacher's padding oracle, and factoring advances.
Elliptic Curve Cryptography (ECC): how curves over finite fields give us the same security with dramatically smaller keys, and why the industry is moving toward ECC and post-quantum alternatives.

Stay tuned -- the finale brings everything full circle.

Note: A version of this article with formal theorem/proof environments is available on Folio.

The Math Behind RSA #2: Modular Arithmetic — When Clock Math Becomes Cryptography

zuka3 — Mon, 23 Mar 2026 01:45:03 +0000

This article has a more math-focused version with formal proofs on Folio.

In Part 1, we explored prime numbers — the raw material of RSA. Now we need the machinery that makes RSA work: modular arithmetic.

You already know modular arithmetic. Every time you look at a clock and say "3 hours after 11 is 2," you're doing it. The twist is that this simple idea — numbers that wrap around — turns out to be the foundation of modern cryptography.

The Clock Analogy

On a 12-hour clock, there's no "13 o'clock." After 12, you wrap back to 1. In math, we write:

\equiv 1 \pmod{12}

This reads "13 is congruent to 1, modulo 12." It means 13 and 1 have the same remainder when divided by 12.

# Modular arithmetic in Python is just the % operator
print(13 % 12)  # 1
print(27 % 12)  # 3
print(48 % 12)  # 0  (exactly on the 12)

More formally: $\equiv b \pmod{n}$ means $n$ divides $(a - b)$ . That's it. That's the whole definition.

The beautiful thing is that modular arithmetic preserves addition and multiplication:

\bmod n = ((a \bmod n) + (b \bmod n)) \bmod n

\times b) \bmod n = ((a \bmod n) \times (b \bmod n)) \bmod n

# These properties let us keep numbers small during computation
n = 17
a, b = 100, 200

# Direct computation
print((a * b) % n)  # 13

# Reducing first, same result
print(((a % n) * (b % n)) % n)  # 13

This property is critical for RSA. Without it, we'd need to compute numbers with thousands of digits before taking the modulus. Instead, we reduce at every step.

Fast Modular Exponentiation: The Speed Trick

RSA needs to compute things like $nm^e \bmod n$ where $e$ might be 65537 and $m$ might be a 2048-bit number. Computing $m^{65537}$ directly? Your computer would run out of memory (and patience).

The trick is repeated squaring. Instead of 65537 multiplications, we need about $log_2(65537) = 17$ squarings.

def fast_mod_exp(base, exponent, mod):
    """Compute base^exponent mod mod using repeated squaring."""
    result = 1
    base = base % mod
    while exponent > 0:
        # If exponent is odd, multiply result with base
        if exponent % 2 == 1:
            result = (result * base) % mod
        # Square the base, halve the exponent
        exponent = exponent >> 1
        base = (base * base) % mod
    return result

# Python has this built in!
print(pow(7, 65537, 143))  # 7^65537 mod 143 = 123
print(fast_mod_exp(7, 65537, 143))  # Same: 123

The key insight: we never let any intermediate value exceed $n^2$ because we reduce modulo $n$ after every multiplication. This is what makes RSA practical.

One-Way Functions: Easy Forward, Hard Backward

Here's where cryptography enters the picture. Modular exponentiation is a one-way function:

Forward (easy): Given $m$ , $e$ , and $n$ , compute $m^e \bmod n$ . This takes milliseconds.
Backward (hard): Given $c$ , $e$ , and $n$ , find $m$ . This is the discrete logarithm problem — no efficient algorithm is known.

# Forward: trivial
m, e, n = 42, 65537, 3233
c = pow(m, e, n)
print(f"Encrypted: {c}")  # Encrypted: 2557

# Backward: you'd need to try all possible m values
# For real RSA with 2048-bit n, this is computationally infeasible

RSA's genius is that it finds a trapdoor — a secret piece of information that makes the backward direction easy too. That trapdoor is the modular inverse, and to understand it, we need the Euclidean algorithm.

The Euclidean Algorithm: 2300 Years Old and Still Useful

Euclid's algorithm finds the greatest common divisor (GCD) of two numbers. It's one of the oldest algorithms still in active use today.

The idea is simple: $b)\gcd(a, b) = \gcd(b, a \bmod b)$ , and $gcd⁡(a,0)=a\gcd(a, 0) = a$ .

def gcd(a, b):
    """Euclid's algorithm — over 2300 years old."""
    while b != 0:
        a, b = b, a % b
    return a

print(gcd(48, 18))   # 6
print(gcd(17, 13))   # 1  (coprime — important for RSA!)
print(gcd(65537, 3120))  # 1  (this is a real RSA check)

Two numbers with $gcd⁡(a,b)=1\gcd(a, b) = 1$ are called coprime. RSA requires that the public exponent $e$ is coprime with a certain special number. We'll get to that number shortly.

The Extended Euclidean Algorithm: Finding the Trapdoor

The extended version doesn't just find $gcd⁡(a,b)\gcd(a, b)$ — it finds integers $x$ and $y$ such that:

\gcd(a, b)

This is called Bezout's identity, and it's the key to computing modular inverses.

def extended_gcd(a, b):
    """Returns (gcd, x, y) such that a*x + b*y = gcd(a, b)."""
    if a == 0:
        return b, 0, 1
    gcd_val, x1, y1 = extended_gcd(b % a, a)
    x = y1 - (b // a) * x1
    y = x1
    return gcd_val, x, y

g, x, y = extended_gcd(35, 15)
print(f"gcd={g}, 35*({x}) + 15*({y}) = {35*x + 15*y}")
# gcd=5, 35*(1) + 15*(-2) = 5

Modular Inverse: The RSA Private Key

The modular inverse of $a$ modulo $n$ is the number $a^{-1}$ such that:

\cdot a^{-1} \equiv 1 \pmod{n}

Think of it as "division in modular arithmetic." It exists if and only if $gcd⁡(a,n)=1\gcd(a, n) = 1$ .

Why does the extended Euclidean algorithm give us this? If $gcd⁡(a,n)=1\gcd(a, n) = 1$ , then we can find $x, y$ where $a x + n y = 1$ . Taking both sides modulo $n$ , the $n y$ term vanishes:

\equiv 1 \pmod{n}

So $x$ is the modular inverse of $a$ .

def mod_inverse(a, n):
    """Find a^(-1) mod n using extended Euclidean algorithm."""
    g, x, _ = extended_gcd(a % n, n)
    if g != 1:
        raise ValueError(f"No inverse: gcd({a}, {n}) = {g}")
    return x % n

# Example: inverse of 7 mod 26
inv = mod_inverse(7, 26)
print(f"7^(-1) mod 26 = {inv}")        # 15
print(f"Verify: 7 * {inv} mod 26 = {(7 * inv) % 26}")  # 1

# Python 3.8+ has this built in:
print(pow(7, -1, 26))  # 15

This is exactly how RSA computes the private key. Given the public exponent $e$ , the private key $d$ is:

\equiv e^{-1} \pmod{\phi(n)}

But what is $ϕ(n)\phi(n)$ ? For that, we need two more theorems.

Fermat's Little Theorem: The Warm-Up

Fermat discovered that for any prime $p$ and any $a$ not divisible by $p$ :

a^{p-1} \equiv 1 \pmod{p}

# Verify Fermat's little theorem
p = 17
for a in range(1, p):
    assert pow(a, p - 1, p) == 1
print(f"Fermat's little theorem holds for all a in [1, {p-1}] mod {p}")

# Useful corollary: a^(-1) ≡ a^(p-2) (mod p)
a, p = 7, 17
print(f"Inverse via Fermat: {pow(a, p - 2, p)}")     # 5
print(f"Inverse via ext GCD: {mod_inverse(a, p)}")    # 5

This gives us a second way to compute modular inverses (when the modulus is prime), but more importantly, it's the stepping stone to Euler's theorem.

Euler's Theorem and the Totient Function

Euler generalized Fermat's result to any modulus, not just primes. First, he defined the totient function $ϕ(n)\phi(n)$ : the count of integers from 1 to $n$ that are coprime with $n$ .

def euler_totient(n):
    """Compute phi(n) by counting coprimes (brute force)."""
    from math import gcd
    return sum(1 for k in range(1, n + 1) if gcd(k, n) == 1)

print(f"phi(12) = {euler_totient(12)}")  # 4  (1, 5, 7, 11)
print(f"phi(7) = {euler_totient(7)}")    # 6  (all of 1..6, since 7 is prime)
print(f"phi(15) = {euler_totient(15)}")  # 8

Euler's theorem states: if $gcd⁡(a,n)=1\gcd(a, n) = 1$ , then:

a^{\phi(n)} \equiv 1 \pmod{n}

Notice that when $n = p$ is prime, $ϕ(p)=p−1\phi(p) = p - 1$ , and this reduces to Fermat's little theorem. Euler's theorem is the engine that makes RSA's encryption-decryption cycle work.

Why $ϕ(n)=(p−1)(q−1)\phi(n) = (p-1)(q-1)$ Is the Secret

Here's where everything clicks. RSA chooses $\cdot q$ for two large primes $p$ and $q$ . The totient has a beautiful property for products of distinct primes:

\phi(p \cdot q) = (p - 1)(q - 1)

Why? Among the numbers $\ldots, pq$ , the ones that are not coprime to $pq$ are exactly the multiples of $p$ (there are $q$ of them) and multiples of $q$ (there are $p$ of them), minus the multiples of both (just $pq$ itself). So:

\phi(pq) = pq - p - q + 1 = (p-1)(q-1)

# Verify with a small example
p, q = 61, 53
n = p * q  # 3233

phi_brute = euler_totient(n)
phi_formula = (p - 1) * (q - 1)

print(f"n = {n}")
print(f"phi(n) brute force = {phi_brute}")    # 3120
print(f"(p-1)(q-1) = {phi_formula}")          # 3120
assert phi_brute == phi_formula

This is the secret of RSA. Anyone can know $n$ (it's public), but computing $ϕ(n)\phi(n)$ requires knowing $p$ and $q$ — which requires factoring $n$ . And factoring large numbers is computationally infeasible.

Putting It All Together: The RSA Key Relationship

Now we can see the full picture. RSA picks primes $p, q$ , computes $n = pq$ and $ϕ(n)=(p−1)(q−1)\phi(n) = (p-1)(q-1)$ , then chooses $e$ coprime to $ϕ(n)\phi(n)$ and computes:

\equiv e^{-1} \pmod{\phi(n)}

This means $\equiv 1 \pmod{\phi(n)}$ , or equivalently $k\phi(n)$ for some integer $k$ . Now watch the magic of decryption:

c^d \equiv (m^e)^d \equiv m^{ed} \equiv m^{1 + k\phi(n)} \equiv m \cdot (m^{\phi(n)})^k \equiv m \cdot 1^k \equiv m \pmod{n}

The last step uses Euler's theorem. The message comes back.

# Complete RSA key generation using everything we've learned
p, q = 61, 53
n = p * q                    # 3233 (public)
phi_n = (p - 1) * (q - 1)   # 3120 (secret!)
e = 17                       # public exponent (coprime with phi_n)

assert gcd(e, phi_n) == 1    # Verify e is valid

d = mod_inverse(e, phi_n)    # 2753 (private key!)
print(f"Public key:  (n={n}, e={e})")
print(f"Private key: (n={n}, d={d})")

# Encrypt and decrypt
message = 42
encrypted = pow(message, e, n)
decrypted = pow(encrypted, d, n)
print(f"Message: {message} -> Encrypted: {encrypted} -> Decrypted: {decrypted}")
# Message: 42 -> Encrypted: 2557 -> Decrypted: 42

Recap: The Modular Arithmetic Toolkit for RSA

Concept	Role in RSA
Modular arithmetic	Keeps numbers bounded, enables wrap-around
Fast exponentiation	Makes encryption/decryption practical
One-way functions	Security foundation — easy to encrypt, hard to reverse
Euclidean algorithm	Validates that $e$ is coprime with $ϕ(n)\phi(n)$
Extended Euclidean	Computes the private key $d$
Modular inverse	$e^{-1} \bmod \phi(n)$ — the private key itself
Fermat's little theorem	Special case that builds intuition
Euler's theorem	Guarantees $med≡m(modn)m^{ed} \equiv m \pmod{n}$ — why decryption works
Totient function	$ϕ(n)=(p−1)(q−1)\phi(n) = (p-1)(q-1)$ — the trapdoor secret

Every piece of modular arithmetic we covered plays a specific, essential role. Remove any one, and RSA falls apart.

Up Next: Part 3 — Building RSA From Scratch

We now have all the mathematical tools. In Part 3, we'll implement RSA end-to-end in Python: key generation, encryption, decryption, and digital signatures. We'll also see where textbook RSA is dangerously insecure and what real implementations do differently.

Note: A version of this article with formal theorem/proof environments is available on Folio.

The Math Behind RSA #1: Primes and Prime Factorization

zuka3 — Thu, 19 Mar 2026 01:44:51 +0000

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 \times 311 = \text{?}

Hard to do mentally, but a computer handles it in nanoseconds. Now go backwards -- factor this number into its two prime components:

\text{?} \times \text{?}

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 gap -- easy to multiply, hard to factor -- is the entire foundation of RSA.

Let's see it in Python:

import time

p = 2**521 - 1   # a known Mersenne prime (157 digits)
q = 2**607 - 1   # another Mersenne prime (183 digits)

start = time.time()
n = p * q
elapsed = time.time() - start

print(f"n has {len(str(n))} digits")
print(f"Multiplication took {elapsed:.6f} seconds")
# n has 340 digits
# Multiplication took 0.000001 seconds

That multiplication finishes in microseconds. Factoring a 340-digit number back into its two prime factors? With current algorithms and hardware, it would take longer than the age of the universe.

What Are Prime Numbers, Really?

A prime number $p$ is an integer greater than 1 whose only positive divisors are 1 and itself. The first few:

\ldots

The Fundamental Theorem of Arithmetic tells us that every integer $n > 1$ can be written as a unique product of primes (up to ordering). For example:

2^3 \times 11 \times 23

This uniqueness is what makes factoring a well-defined problem -- there is exactly one answer to find.

How Many Primes Are There?

A natural question: if RSA needs large primes, are there enough of them? The answer is a resounding yes.

The Prime Number Theorem states that the number of primes less than or equal to $x$ , denoted $π(x)\pi(x)$ , is approximately:

\pi(x) \sim \frac{x}{\ln x}

This means roughly 1 in every $ln⁡x\ln x$ numbers near $x$ is prime. For a 1024-bit number (about 308 digits), $ln⁡(21024)≈710\ln(2^{1024}) \approx 710$ , so roughly 1 in every 710 numbers of that size is prime.

import math

bits = 1024
x = 2 ** bits
density = 1 / (bits * math.log(2))
print(f"Approximately 1 in {int(1/density)} numbers near 2^{bits} is prime")
# Approximately 1 in 710 numbers near 2^1024 is prime

That is an astronomically large supply. There are more 1024-bit primes than atoms in the observable universe.

Testing for Primality: The Miller-Rabin Test

RSA key generation needs to find large primes quickly. Trial division -- dividing by every number up to $n\sqrt{n}$ -- is hopelessly slow for 300-digit numbers. Instead, we use probabilistic primality tests.

The most widely used is the Miller-Rabin primality test. Here is the core idea.

The Math

Fermat's Little Theorem says that if $p$ is prime and $a$ is not divisible by $p$ , then:

a^{p-1} \equiv 1 \pmod{p}

Miller-Rabin strengthens this. Write $2^s \cdot d$ where $d$ is odd. Then for a prime $n$ , any base $a$ must satisfy one of:

a^d \equiv 1 \pmod{n}

a^{2^r \cdot d} \equiv -1 \pmod{n} \quad \text{for some } 0 \le r < s

If neither condition holds, $n$ is definitely composite. If both fail to disprove primality, $n$ is probably prime. Each round of testing with a random base has at most a $14\frac{1}{4}$ chance of being fooled, so $k$ rounds give a false positive probability of at most $4^{-k}$ .

Python Implementation

import random

def miller_rabin(n, k=20):
    """
    Miller-Rabin primality test.
    Returns True if n is probably prime, False if definitely composite.
    k rounds -> false positive probability at most 4^(-k).
    """
    if n < 2:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False

    # Write n - 1 as 2^s * d with d odd
    s, d = 0, n - 1
    while d % 2 == 0:
        s += 1
        d //= 2

    # Run k rounds of testing
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)  # a^d mod n (Python's built-in modular exponentiation)

        if x == 1 or x == n - 1:
            continue

        for _ in range(s - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False  # definitely composite

    return True  # probably prime

# Test it
print(miller_rabin(2**61 - 1))    # True  (Mersenne prime)
print(miller_rabin(2**67 - 1))    # False (not prime: 147573952589676412927 = 193707721 * 761838257287)
print(miller_rabin(561))           # False (Carmichael number, fools Fermat test but not Miller-Rabin)

With 20 rounds, the probability of a false positive is $4−20≈10−124^{-20} \approx 10^{-12}$ -- far less likely than a hardware error flipping a bit in your computation.

Generating Large Primes

With Miller-Rabin in hand, generating a prime of a desired bit length is straightforward: pick random odd numbers and test until one passes.

import secrets

def generate_prime(bits, k=20):
    """Generate a random prime with the specified number of bits."""
    while True:
        # Generate a random odd number with the MSB set (ensures correct bit length)
        candidate = secrets.randbits(bits)
        candidate |= (1 << (bits - 1)) | 1  # set MSB and LSB

        if miller_rabin(candidate, k):
            return candidate

# Generate a 1024-bit prime
p = generate_prime(1024)
print(f"Found a {p.bit_length()}-bit prime")
print(f"First 20 digits: {str(p)[:20]}...")
print(f"Last 20 digits:  ...{str(p)[-20:]}")

Because roughly 1 in 710 odd 1024-bit numbers is prime, we expect to test about 355 candidates on average. Each Miller-Rabin test is fast (modular exponentiation is $O(log⁡2n⋅log⁡log⁡n)O(\log^2 n \cdot \log \log n)$ with efficient algorithms), so generating a 1024-bit prime typically takes well under a second.

In practice, implementations apply small optimizations like checking divisibility by small primes (3, 5, 7, ...) before running Miller-Rabin, which filters out most composites cheaply.

SMALL_PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

def generate_prime_optimized(bits, k=20):
    """Prime generation with small-prime sieving."""
    while True:
        candidate = secrets.randbits(bits)
        candidate |= (1 << (bits - 1)) | 1

        # Quick check: skip if divisible by any small prime
        if any(candidate % sp == 0 for sp in SMALL_PRIMES):
            if candidate not in SMALL_PRIMES:
                continue

        if miller_rabin(candidate, k):
            return candidate

How Hard Is Factoring, Actually?

So multiplication is easy and factoring is hard -- but how hard exactly?

The Best Known Algorithm: GNFS

The fastest known algorithm for factoring large numbers is the General Number Field Sieve (GNFS). Its heuristic running time for factoring an integer $n$ is:

L_n!\left[\frac{1}{3},\; \left(\frac{64}{9}\right)^{1/3}\right] = \exp!\left(\left(\frac{64}{9}\right)^{1/3} (\ln n)^{1/3} (\ln \ln n)^{2/3}\right)

This is sub-exponential but super-polynomial -- it grows faster than any polynomial in $log⁡n\log n$ but slower than a true exponential. In practice, this means that each additional digit in the number you are trying to factor makes the problem harder, but not uniformly so.

Factoring Records

The largest RSA-type number factored so far is RSA-250 (250 decimal digits, 829 bits), achieved in 2020. It required approximately 2700 CPU core-years of computation.

RSA Key Lengths and Security

Here is a rough picture of how factoring difficulty scales with key size:

RSA Key Size	Status	Estimated GNFS Effort
512 bits (155 digits)	Broken (1999)	Hours on modern hardware
768 bits (232 digits)	Broken (2009)	~2000 CPU core-years
1024 bits (309 digits)	Threatened	~ $10^6$ core-years
2048 bits (617 digits)	Secure	~ $10^{20}$ core-years
4096 bits (1234 digits)	Very secure	~ $10^{40}$ core-years

This is why 2048-bit RSA keys are the current minimum recommendation, and why security-conscious applications use 4096-bit keys.

A Note on Quantum Computing

Shor's algorithm can factor integers in polynomial time on a quantum computer, which would break RSA entirely. This is why the cryptographic community is actively developing post-quantum algorithms. But as of today, no quantum computer has factored anything beyond trivially small numbers, so RSA remains safe for now.

Putting It All Together

Let's tie everything from this article into a mini RSA key parameter generator:

import secrets
import random
import time

def miller_rabin(n, k=20):
    if n < 2:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False
    s, d = 0, n - 1
    while d % 2 == 0:
        s += 1
        d //= 2
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(s - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

def generate_prime(bits):
    while True:
        candidate = secrets.randbits(bits)
        candidate |= (1 << (bits - 1)) | 1
        if miller_rabin(candidate):
            return candidate

# Generate RSA parameters
KEY_BITS = 2048
start = time.time()
p = generate_prime(KEY_BITS // 2)
q = generate_prime(KEY_BITS // 2)
n = p * q
elapsed = time.time() - start

print(f"Generated two {KEY_BITS // 2}-bit primes in {elapsed:.2f}s")
print(f"Product n has {n.bit_length()} bits ({len(str(n))} digits)")
print(f"Good luck factoring that!")

Running this produces a 2048-bit modulus in about a second. Factoring it back? That would take roughly $10^{20}$ CPU core-years. The asymmetry is staggering, and it is exactly what keeps your data safe.

Key Takeaways

The core asymmetry: multiplying primes is $O(n^2)$ or better; factoring their product is sub-exponential via GNFS.
Primes are abundant: the Prime Number Theorem guarantees a vast supply of large primes.
Miller-Rabin lets us find large primes efficiently with negligible error probability.
Factoring is hard but not proven hard: no one has proved $\neq NP$ , so the hardness of factoring remains an assumption -- but one that has held up for decades.

Note: A version of this article with formal theorem/proof environments is available on Folio.

Next up in the series: **The Math Behind RSA #2: Modular Arithmetic and Euler's Theorem* -- where we'll build the algebraic machinery that makes RSA encryption and decryption actually work. We'll cover modular inverses, Euler's totient function, and the beautiful identity that ties it all together.*

What You Can't Write on Dev.to — Math Notation Limits and Alternatives

zuka3 — Mon, 16 Mar 2026 01:50:51 +0000

Dev.to's KaTeX support handles most mathematical notation well. But if you're writing about certain topics, you'll hit walls that no workaround can fully solve.

This article documents the specific limitations, who they affect, and what your options are.

Limitation 1: Commutative Diagrams

What you want to write

In algebra and category theory, commutative diagrams are essential. In LaTeX:

\begin{tikzcd}
A \arrow[r, "f"] \arrow[d, "g"'] & B \arrow[d, "\phi"] \\
C \arrow[r, "\psi"'] & D
\end{tikzcd}

This produces a diagram with labeled arrows showing that different paths between the same endpoints yield the same result.

On Dev.to

Not supported. Neither tikz-cd nor the simpler amscd environment works.

Workarounds

ASCII art — works for simple diagrams:

A ---f--→ B
|         |
g         φ
↓         ↓
C ---ψ--→ D

External tools — generate an image and embed it:
- quiver — interactive commutative diagram editor
- Export as SVG/PNG → upload to Dev.to
Describe in words — "The diagram commutes, meaning $ψ∘g=ϕ∘f\psi \circ g = \phi \circ f$ "

None of these are great. ASCII breaks with complex diagrams. Images can't be edited inline. Words are imprecise.

Limitation 2: Theorem/Proof Environments

What you want

\begin{theorem}[Cantor's Diagonal Argument]
The set $\mathbb{R}$ is uncountable.
\end{theorem}

\begin{proof}
...
\end{proof}

LaTeX auto-formats this with numbering, consistent styling, and QED marks.

On Dev.to

Not supported. As covered in the previous article, you can approximate with blockquotes and <details>, but you lose:

Automatic numbering
Cross-references ("by Theorem 2.3")
Consistent styling
Auto QED marks

For a single article, manual numbering is manageable. For a series of 10+ articles with dozens of theorems referencing each other, it becomes a maintenance burden.

Limitation 3: Custom Macros

What you want

\newcommand{\R}{\mathbb{R}}
\newcommand{\norm}[1]{\left\| #1 \right\|}
\newcommand{\inner}[2]{\left\langle #1, #2 \right\rangle}

% Then use: $\norm{x} \in \R$

On Dev.to

Not supported. Every occurrence must be written in full:

{% katex inline %} \left\| x \right\| \in \mathbb{R} {% endkatex %}

This is especially painful for articles with heavy notation. An article about functional analysis might use $R\mathbb{R}$ fifty times.

Limitation 4: Algorithm Pseudocode with Math

What you want

\begin{algorithmic}[1]
\Require $a, b \in \mathbb{Z}_{>0}$
\While{$b \neq 0$}
    \State $r \gets a \bmod b$
    \State $a \gets b$, $b \gets r$
\EndWhile
\State \Return $a$
\end{algorithmic}

On Dev.to

Code blocks don't render math. You have to choose:

Code block — no math rendering:

Input: a, b ∈ Z (positive integers)
while b ≠ 0 do
    r ← a mod b
    a ← b, b ← r
return a

Math block — no code formatting, no line numbers

You can't mix both naturally.

Limitation 5: tikz Drawings

What you want

Graph theory graphs, automata, neural network diagrams, geometric figures — anything drawn with tikz.

On Dev.to

Not supported. Mermaid diagrams cover flowcharts and sequence diagrams, but not mathematical graphs where vertex positioning matters.

Who Is Affected?

For most technical articles, these limitations don't matter:

Content type	Affected?
Algorithm analysis (Big-O, recurrences)	❌ No — KaTeX is fine
ML/statistics formulas	❌ No — KaTeX is fine
Basic proofs	❌ No — blockquotes work
Category theory	✅ Yes — needs commutative diagrams
Algebraic topology	✅ Yes — exact sequences, spectral sequences
Textbook-style content	✅ Yes — needs theorem numbering and cross-references
Graph theory	✅ Yes — needs graph drawings

Alternatives

If you're hitting these limitations regularly, here are your options:

1. Embed images

Generate diagrams locally (LaTeX → PDF → PNG) and embed them. High friction — every edit requires regenerating images.

2. Use a LaTeX-native platform

I ran into these exact limitations writing a series on group theory. After fighting with ASCII diagrams and manual numbering for too long, I moved my math-heavy articles to Folio, which renders full LaTeX including tikz-cd, theorem environments, and \newcommand.

I still write general programming articles on Dev.to — it's great for that. But for content where the math is the point, a LaTeX-native platform saves significant time.

3. Overleaf + PDF

Write in Overleaf, export PDF, and link to it. You lose the web-native reading experience, but get full LaTeX power.

Summary

Feature	Dev.to	Full LaTeX
Basic equations	✅ KaTeX	✅
Aligned equations	✅ `aligned`	✅ `align`
Matrices	✅	✅
Commutative diagrams	❌	✅ tikz-cd
Theorem environments	❌	✅
Custom macros	❌	✅
tikz drawings	❌	✅
Auto-numbering	❌	✅

Dev.to is excellent for technical articles with some math. For articles where advanced math notation is central, you'll need to decide between workarounds and alternative platforms.

Writing Theorems, Proofs, and Definitions on Dev.to

zuka3 — Thu, 12 Mar 2026 01:22:16 +0000

If you're writing a math-heavy article — explaining an algorithm's correctness, proving a complexity bound, or walking through a cryptographic protocol — you need a way to clearly distinguish theorems, proofs, definitions, and examples from the surrounding text.

Standard LaTeX has dedicated environments for this (\begin{theorem}, \begin{proof}). Dev.to doesn't. But with some markdown techniques, you can get close.

Method 1: Blockquotes (Simplest)

Markdown blockquotes (>) give a visual distinction from body text:

> **Theorem 1 (Lagrange's Theorem).**
> For a finite group G and subgroup H,
> the order of H divides the order of G:
> {% katex %} |G| = [G : H] \cdot |H| {% endkatex %}

Theorem 1 (Lagrange's Theorem).
For a finite group G and subgroup H, the order of H divides the order of G:

$\cdot |H|$

Simple, reliable, and works everywhere.

Method 2: Collapsible Proofs

Long proofs can overwhelm readers. Use <details> to make them collapsible:

<details>
<summary><b>Proof</b></summary>

Consider the set of left cosets of H in G.
Each coset gH contains |H| elements,
and distinct cosets are disjoint.
Since G is the disjoint union of its cosets:

{% katex %}
|G| = (\text{number of cosets}) \times |H| = [G:H] \cdot |H|
{% endkatex %}

{% katex inline %} \square {% endkatex %}
</details>

Proof Consider the set of left cosets of H in G. Each coset gH contains |H| elements, and distinct cosets are disjoint. Since G is the disjoint union of its cosets:

(\text{number of cosets}) \times |H| = [G:H] \cdot |H|

$□\square$

This lets readers see the theorem statement first and expand the proof only if they want the details.

Method 3: Horizontal Rules

Use --- to create visual boundaries:

---

**Theorem 2 (Euler's Formula).**

For any real number θ:

{% katex %}
e^{i\theta} = \cos\theta + i\sin\theta
{% endkatex %}

---

Theorem 2 (Euler's Formula).

For any real number θ:

e^{i\theta} = \cos\theta + i\sin\theta

QED Marks

In LaTeX, \begin{proof} automatically adds a QED mark. On Dev.to, add it manually:

Style	Code	Result
White square	`{% katex inline %} \square {% endkatex %}`	□
Black square	`{% katex inline %} \blacksquare {% endkatex %}`	■
Text	`■`	■

Place it at the end of your proof, typically on the last line.

Numbering Conventions

Option 1: Sequential numbering (recommended)

Theorem 1, Lemma 2, Theorem 3, Corollary 4 ...

Sequential numbering makes it easy to find referenced items — "Lemma 2 comes before Theorem 3" is immediately clear from the numbers.

Option 2: Section-based numbering

Theorem 2.1, Lemma 2.2, Theorem 3.1 ...

Better for longer articles with clear sections.

Option 3: Type-based numbering

Theorem 1, Theorem 2, Lemma 1, Lemma 2 ...

Avoid this — it's confusing when referencing ("Lemma 1 is used in the proof of Theorem 2" doesn't tell you the ordering).

Distinguishing Types

In math writing, different statement types serve different roles:

Type	Purpose	When to use
Definition	Introduces a term	Before first use
Theorem	Major result	Central claims
Lemma	Helper result	Building blocks for theorems
Proposition	Medium result	Less central than a theorem
Corollary	Direct consequence	Immediately after a theorem
Example	Concrete instance	After definitions or theorems
Remark	Commentary	Supplementary notes

Full Example: The First Isomorphism Theorem

Here's a complete example combining everything:

Definition 1 (Group Homomorphism).
A map $φ:G→H\varphi: G \to H$ between groups is a homomorphism if

$φ(ab)=φ(a)φ(b)\varphi(ab) = \varphi(a)\varphi(b)$
for all $\in G$ .
Definition 2 (Kernel and Image).
For a homomorphism $φ:G→H\varphi: G \to H$ :

$Im⁡φ=φ(g)∣g∈G\begin{aligned} \ker\varphi &= { g \in G \mid \varphi(g) = e_H } \ \operatorname{Im}\varphi &= { \varphi(g) \mid g \in G } \end{aligned}$
Lemma 3. The kernel $ker⁡φ\ker\varphi$ is a normal subgroup of G.

Proof

The subgroup property is straightforward. For normality: for any
$\in G$
and
$\in \ker\varphi$
:

φ(gng−1)=φ(g)φ(n)φ(g−1)=φ(g)⋅eH⋅φ(g)−1=eH\begin{aligned} \varphi(gng^{-1}) &= \varphi(g)\varphi(n)\varphi(g^{-1}) \\ &= \varphi(g) \cdot e_H \cdot \varphi(g)^{-1} = e_H \end{aligned}

So
$gng−1∈ker⁡φgng^{-1} \in \ker\varphi$
, proving
$ker⁡φ⊴G\ker\varphi \trianglelefteq G$
.
$□\square$

Theorem 4 (First Isomorphism Theorem).
For any group homomorphism $φ:G→H\varphi: G \to H$ :

$\ker\varphi \cong \operatorname{Im}\varphi$

Proof

Let
$\ker\varphi$
. Define
$φˉ:G/N→Im⁡φ\bar{\varphi}: G/N \to \operatorname{Im}\varphi$
by
$φˉ(gN)=φ(g)\bar{\varphi}(gN) = \varphi(g)$
.

Well-defined: If
$g N = g^{'} N$
, then
$g−1g′∈Ng^{-1}g' \in N$
, so
$φ(g)=φ(g′)\varphi(g) = \varphi(g')$
.

Homomorphism:
$φˉ(gN⋅g′N)=φ(gg′)=φ(g)φ(g′)=φˉ(gN)φˉ(g′N)\bar{\varphi}(gN \cdot g'N) = \varphi(gg') = \varphi(g)\varphi(g') = \bar{\varphi}(gN)\bar{\varphi}(g'N)$
.

Injective:
$φˉ(gN)=eH\bar{\varphi}(gN) = e_H$
implies
$\in N$
, so
$g N = N$
.

Surjective: By definition of
$Im⁡φ\operatorname{Im}\varphi$
.

Hence
$φˉ\bar{\varphi}$
is an isomorphism.
$□\square$

Corollary 5. If $φ\varphi$ is surjective, then $G/ker⁡φ≅HG/\ker\varphi \cong H$ .

Templates

Copy-paste these to get started:

Theorem:

> **Theorem N (Name).**
> Statement here.
> {% katex %} equation {% endkatex %}

Proof (collapsible):

<details>
<summary><b>Proof</b></summary>

Proof body here.

{% katex inline %} \square {% endkatex %}
</details>

Definition:

> **Definition N (Term).**
> Definition here.

Summary

Blockquotes for theorems/definitions, <details> for proofs
Sequential numbering for easy referencing
QED mark: $□\square$ at the end of proofs
Collapsible proofs keep articles scannable
No auto-numbering or cross-references — manage manually

Dev.to KaTeX vs Standard LaTeX — What Works and What Doesn't

zuka3 — Mon, 09 Mar 2026 01:27:29 +0000

If you've used LaTeX before (in papers, Overleaf, or textbooks), you'll find that many things work differently — or don't work at all — on Dev.to. This is because Dev.to uses KaTeX, which covers a large subset of LaTeX but not everything.

This article is a reference for what's supported and what's not, with workarounds for common pain points.

The Key Difference: Liquid Tags

Standard LaTeX uses $...$ for inline math and $$...$$ for display math. Dev.to uses liquid tags:

Context	Standard LaTeX	Dev.to
Inline	$x^2$	`{% katex inline %} x^2 {% endkatex %}`
Display	`$$x^2$$`	`{% katex %} x^2 {% endkatex %}`

This is more verbose, but the rendering inside the tags follows standard KaTeX syntax.

What Works ✅

Environments

Environment	Example	Notes
`aligned`	Multi-line aligned equations	Use this instead of `align`
`cases`	Piecewise functions
`pmatrix`, `bmatrix`, etc.	Matrices	All bracket types work
`array`	Custom layouts
`smallmatrix`	Inline matrices

Symbols and Commands

These all work as expected:

All Greek letters (\alpha through \omega, uppercase too)
Fractions: \frac, \dfrac, \cfrac
Roots: \sqrt, \sqrt[n]
Accents: \hat, \bar, \tilde, \vec, \dot
Operators: \sum, \prod, \int, \lim
Relations: \leq, \geq, \neq, \sim, \cong, \equiv
Logic: \forall, \exists, \neg, \land, \lor
Sets: \in, \subset, \cup, \cap, \emptyset
Arrows: \to, \Rightarrow, \iff, \mapsto
Fonts: \mathbb, \mathbf, \mathcal, \mathfrak, \mathrm, \text
Decorations: \color, \boxed, \cancel, \underbrace, \overbrace

What Doesn't Work ❌

1. `align` environment

This is the most common gotcha for LaTeX users.

Won't work:

{% katex %}
\begin{align}
a &= b + c \\
  &= d
\end{align}
{% endkatex %}

Use instead:

{% katex %}
\begin{aligned}
a &= b + c \\
  &= d
\end{aligned}
{% endkatex %}

The difference: align is a top-level environment in LaTeX (with auto-numbering). aligned is a sub-environment that works inside math mode, which is what KaTeX expects.

2. `\newcommand` (Custom Macros)

In LaTeX, you can define shortcuts:

% This doesn't work on Dev.to
\newcommand{\R}{\mathbb{R}}
\newcommand{\norm}[1]{\left\| #1 \right\|}

Workaround: Write the full command every time. Use your editor's find-and-replace or snippets to save time while writing.

3. Auto-numbering and Cross-references

% None of these work
\label{eq:main}
\ref{eq:main}
\eqref{eq:main}

Workaround: Use \tag{} for manual numbering:

{% katex %}
E = mc^2 \tag{1}
{% endkatex %}

mc^2 \tag{1}

You'll need to manage numbers by hand. If you add an equation in the middle, you'll need to renumber everything after it.

4. Theorem Environments

% Not supported
\begin{theorem}
Every finite group of order p is cyclic.
\end{theorem}

\begin{proof}
...
\end{proof}

Workaround: Use markdown formatting:

> **Theorem 1.** Every finite group of order p is cyclic.

<details>
<summary><b>Proof</b></summary>

... proof content ...

{% katex inline %} \square {% endkatex %}
</details>

5. Diagrams (tikz, tikz-cd)

Commutative diagrams, graphs, automata — none of the tikz family works:

% Not supported
\begin{tikzcd}
A \arrow[r] & B
\end{tikzcd}

Workaround: Generate diagrams externally and embed as images. Tools:

quiver for commutative diagrams
tikzjax for general tikz
Export to SVG/PNG and use ![diagram](url)

6. `\DeclareMathOperator`

% Not supported
\DeclareMathOperator{\Hom}{Hom}

Workaround: Use \operatorname{}:

{% katex %}
\operatorname{Hom}(A, B)
{% endkatex %}

\operatorname{Hom}(A, B)

Quick Reference: Substitutions

What you want	Standard LaTeX	Dev.to equivalent
Aligned equations	`\begin{align}`	`\begin{aligned}` inside katex block
Display equation	`$$...$$`	`{% katex %}...{% endkatex %}`
Inline equation	$...$	`{% katex inline %}...{% endkatex %}`
Custom macro	`\newcommand`	Write it out every time
Equation number	`\label` + `\ref`	`\tag{1}` manually
Named operator	`\DeclareMathOperator`	`\operatorname{Name}`
Theorem box	`\begin{theorem}`	Markdown blockquote + bold
Diagram	`tikz-cd`	External image

When KaTeX Isn't Enough

For most technical articles — algorithm analysis, ML math, basic proofs — KaTeX on Dev.to is sufficient. But if you're writing content that requires:

Commutative diagrams (algebra, category theory)
Formal theorem/proof environments with auto-numbering
Complex tikz drawings (graphs, automata)
Custom macros for long articles

You may want to consider a LaTeX-native platform. I've been using Folio for articles that need full LaTeX support — tikz-cd, theorem environments, \newcommand, all work out of the box.

Summary

Dev.to uses KaTeX via {% katex %} liquid tags — not $ syntax
Most standard math notation works fine
Main gaps: align (use aligned), no macros, no auto-numbering, no diagrams
For 90% of technical articles, these limitations don't matter
Know the workarounds, and you can write clean math on Dev.to

How to Write Beautiful Math Equations on Dev.to

zuka3 — Thu, 05 Mar 2026 02:51:04 +0000

Dev.to supports mathematical equations through KaTeX. If you're writing articles about algorithms, machine learning, cryptography, or any math-heavy topic, this is essential knowledge.

This guide covers everything from basic syntax to practical tips for making your equations look great.

Basic Syntax

Dev.to uses liquid tags for math rendering, not the $...$ syntax you might know from LaTeX or GitHub.

Block Equations

For standalone equations on their own line:

{% katex %}
\int_0^\infty e^{-x^2} dx = \frac{\sqrt{\pi}}{2}
{% endkatex %}

\int_0^\infty e^{-x^2} dx = \frac{\sqrt{\pi}}{2}

Inline Equations

For equations within text, add inline:

The function {% katex inline %} f(x) = x^2 + 1 {% endkatex %} is defined for all real numbers.

The function $f(x) = x^2 + 1$ is defined for all real numbers.

Common Patterns

Fractions

{% katex %}
\frac{a}{b}, \quad \dfrac{a}{b}, \quad \cfrac{1}{1+\cfrac{1}{2}}
{% endkatex %}

\frac{a}{b}, \quad \dfrac{a}{b}, \quad \cfrac{1}{1+\cfrac{1}{2}}

Sums and Products

{% katex %}
\sum_{k=1}^{n} k = \frac{n(n+1)}{2}, \quad \prod_{i=1}^{n} a_i
{% endkatex %}

\sum_{k=1}^{n} k = \frac{n(n+1)}{2}, \quad \prod_{i=1}^{n} a_i

Integrals

{% katex %}
\int_a^b f(x)\,dx, \quad \iint_D f(x,y)\,dx\,dy, \quad \oint_C \mathbf{F} \cdot d\mathbf{r}
{% endkatex %}

\int_a^b f(x)\,dx, \quad \iint_D f(x,y)\,dx\,dy, \quad \oint_C \mathbf{F} \cdot d\mathbf{r}

Limits

{% katex %}
\lim_{n \to \infty} \left(1 + \frac{1}{n}\right)^n = e
{% endkatex %}

\lim_{n \to \infty} \left(1 + \frac{1}{n}\right)^n = e

Matrices

{% katex %}
A = \begin{pmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{pmatrix}
{% endkatex %}

\begin{pmatrix} a_{11} & a_{12} \ a_{21} & a_{22} \end{pmatrix}

Bracket variants: pmatrix (round), bmatrix (square), vmatrix (determinant), Bmatrix (curly).

Cases (Piecewise Functions)

{% katex %}
|x| = \begin{cases} x & (x \geq 0) \\ -x & (x < 0) \end{cases}
{% endkatex %}

\begin{cases} x & (x \geq 0) \ -x & (x < 0) \end{cases}

Multi-line Aligned Equations

Use the aligned environment to align equations at a specific point (usually =):

{% katex %}
\begin{aligned}
(a+b)^2 &= (a+b)(a+b) \\
&= a^2 + 2ab + b^2
\end{aligned}
{% endkatex %}

\begin{aligned} (a+b)^2 &= (a+b)(a+b) \ &= a^2 + 2ab + b^2 \end{aligned}

Important: Use aligned, not align. The align environment doesn't work in KaTeX on Dev.to.

Symbols Reference

Greek Letters

Code	Symbol	Code	Symbol
`\alpha`	α	`\beta`	β
`\gamma`	γ	`\delta`	δ
`\epsilon`	ε	`\theta`	θ
`\lambda`	λ	`\mu`	μ
`\pi`	π	`\sigma`	σ
`\phi`	φ	`\omega`	ω

Operators and Relations

Code	Symbol	Meaning
`\leq`	≤	less than or equal
`\geq`	≥	greater than or equal
`\neq`	≠	not equal
`\approx`	≈	approximately
`\equiv`	≡	congruent / equivalent
`\in`	∈	element of
`\subset`	⊂	subset
`\forall`	∀	for all
`\exists`	∃	there exists
`\to`	→	maps to
`\Rightarrow`	⇒	implies
`\iff`	⟺	if and only if

Fonts

Code	Use
`\mathbb{R}`	Number fields (ℝ, ℤ, ℚ)
`\mathbf{v}`	Vectors, matrices
`\mathcal{F}`	Filters, sigma-algebras
`\mathfrak{g}`	Lie algebras
`\text{word}`	Text inside equations

Tips for Readability

1. Spacing

Small spacing adjustments make a big difference:

Command	Width	Use
`\,`	thin	before dx in integrals
`\quad`	wide	separating expressions
`\qquad`	extra wide	large separations

Before: $∫01f(x)dx\int_0^1 f(x)dx$
After: $dx\int_0^1 f(x)\,dx$

2. Auto-sizing Brackets

Use \left and \right to auto-size brackets around tall content:

{% katex %}
\left(\frac{a}{b}\right)^2
{% endkatex %}

3. Color

Highlight important parts with \color{}:

{% katex %}
f(x) = \color{red}{a}x^2 + \color{blue}{b}x + \color{green}{c}
{% endkatex %}

\color{red}{a}x^2 + \color{blue}{b}x + \color{green}{c}

4. Boxed Results

Draw attention to key results:

{% katex %}
\boxed{E = mc^2}
{% endkatex %}

\boxed{E = mc^2}

What Doesn't Work

Dev.to's KaTeX has the same limitations as other KaTeX-based platforms:

❌ \newcommand — no custom macros
❌ \begin{align} — use aligned inside katex tags instead
❌ \label / \ref — no auto-numbering or cross-references
❌ \begin{theorem} — no theorem environments
❌ tikz-cd / tikzpicture — no diagram drawing
❌ $...$ syntax — must use liquid tags

For manual equation numbering, use \tag{}:

{% katex %}
E = mc^2 \tag{1}
{% endkatex %}

Summary

Use {% katex %}...{% endkatex %} for block math
Use {% katex inline %}...{% endkatex %} for inline math
Use aligned (not align) for multi-line equations
\, and \quad for spacing, \left/\right for bracket sizing
No macros, no auto-numbering, no diagrams — those are KaTeX limitations

DEV Community: zuka3

The Math Behind RSA #4: Breaking RSA and the Rise of Elliptic Curve Cryptography

Part I: Attacks on RSA

The Factoring Arms Race

Side-Channel Attacks

Padding Oracle Attacks

Part II: The Key Length Problem

Part III: Introduction to Elliptic Curves

Group Structure

Part IV: Python Implementation

A Quick Test

Part V: ECDH Key Exchange

Part VI: Why ECDLP Is Harder Than Factoring

Part VII: The Quantum Threat

Shor's Algorithm

Post-Quantum Cryptography

Part VIII: RSA vs ECC — Full Comparison

Folio: The Full Mathematical Treatment

Series Summary

The Math Behind RSA #3: Implementing RSA from Scratch in Python

RSA in Three Steps

Recap: Helper Functions from Parts #1 and #2

Greatest Common Divisor

Extended Euclidean Algorithm

Modular Inverse

Miller-Rabin Primality Test

Key Generation

Why e = 65537?

Encryption and Decryption

Quick Test

Proof of Correctness

CRT Optimization: 4x Speedup

Verify CRT produces the same result

String Encryption Demo

Our Implementation vs. Production RSA

Putting It All Together

What's Next

The Math Behind RSA #2: Modular Arithmetic — When Clock Math Becomes Cryptography

The Clock Analogy

Fast Modular Exponentiation: The Speed Trick

One-Way Functions: Easy Forward, Hard Backward

The Euclidean Algorithm: 2300 Years Old and Still Useful

The Extended Euclidean Algorithm: Finding the Trapdoor

Modular Inverse: The RSA Private Key

Fermat's Little Theorem: The Warm-Up

Euler's Theorem and the Totient Function

Why ϕ(n)=(p−1)(q−1)\phi(n) = (p-1)(q-1) ϕ(n)=(p−1)(q−1) Is the Secret

Putting It All Together: The RSA Key Relationship

Recap: The Modular Arithmetic Toolkit for RSA

Up Next: Part 3 — Building RSA From Scratch

The Math Behind RSA #1: Primes and Prime Factorization

The Fundamental Asymmetry

What Are Prime Numbers, Really?

How Many Primes Are There?

Testing for Primality: The Miller-Rabin Test

The Math

Python Implementation

Generating Large Primes

How Hard Is Factoring, Actually?

The Best Known Algorithm: GNFS

Factoring Records

RSA Key Lengths and Security

A Note on Quantum Computing

Putting It All Together

Key Takeaways

What You Can't Write on Dev.to — Math Notation Limits and Alternatives

Limitation 1: Commutative Diagrams

What you want to write

On Dev.to

Workarounds

Limitation 2: Theorem/Proof Environments

What you want

On Dev.to

Limitation 3: Custom Macros

What you want

On Dev.to

Limitation 4: Algorithm Pseudocode with Math

What you want

On Dev.to

Limitation 5: tikz Drawings

Why $ϕ(n)=(p−1)(q−1)\phi(n) = (p-1)(q-1)$ Is the Secret

1. `align` environment

2. `\newcommand` (Custom Macros)

6. `\DeclareMathOperator`