Number theory meets cryptography: why RSA works and what makes it secure

Every theorem in this series -- Fermat, Euler, the extended Euclidean algorithm, CRT -- corresponds to a component of the RSA cryptosystem. We trace each connection, work through a concrete example, and discuss the factoring barrier that underpins RSA's security.

Folio Official

March 1, 2026

Number theory was long celebrated as the purest branch of mathematics – beautiful, ancient, and seemingly devoid of practical application. That reputation changed in 1977, when Rivest, Shamir, and Adleman combined several classical theorems into a public-key cryptosystem that transformed the way the world communicates securely. In this final article, we trace how each theorem from this series feeds into the RSA cryptosystem.

1 The idea behind public-key cryptography

Remark 1 (The key-distribution problem).

Traditional (symmetric-key) cryptography requires the sender and receiver to share a secret key. But sharing a key securely requires an already-secure channel – a chicken-and-egg problem.

Public-key cryptography resolves this dilemma using a one-way function: an operation that is easy to perform but hard to reverse. Think of a padlock: anyone can snap it shut, but only the keyholder can open it.

2 How RSA works

Definition 2 (RSA key generation).

Choose two large random primes $p$ and $q$ , and compute $n = pq$ .
Compute $φ (n) = (p - 1) (q - 1)$ (Euler's totient function).
Choose $e$ with $g cd (e, φ (n)) = 1$ (the standard choice is $e = 65537$ ).
Compute $d$ satisfying $e d \equiv 1 (mod φ (n))$ (via the extended Euclidean algorithm).

Public key:

(n, e)

. Private key:

d

Remark 3.

Let us identify the tools used in this construction:

Primes (Article 3): the choice of $p$ and $q$ .
Euler's totient function (Article 4): computing $φ (n)$ .
Extended Euclidean algorithm (Article 2): computing $d$ .

Definition 4 (RSA encryption and decryption).

Represent the plaintext as an integer

m

with

0 \leq m < n

Encryption: $c \equiv m^{e} (mod n)$ (using the public key $e$ ).
Decryption: $m \equiv c^{d} (mod n)$ (using the private key $d$ ).

3 Why decryption recovers the plaintext: Euler's theorem is the key

Why does $c^{d} \equiv m (mod n)$ hold?

Theorem 5 (Correctness of RSA).

g cd (m, n) = 1

, then

(m^{e})^{d} \equiv m (mod n)

Proof.

Since

e d \equiv 1 (mod φ (n))

, write

e d = 1 + k φ (n)

for some integer

k

. Then

(m^{e})^{d} = m^{e d} = m^{1 + k φ (n)} = m \cdot (m^{φ (n)})^{k} .

By Euler's theorem (Article 4),

m^{φ (n)} \equiv 1 (mod n)

. Therefore

(m^{e})^{d} \equiv m \cdot 1^{k} = m (mod n) .

□

Remark 6.

When

g cd (m, n) \neq = 1

(that is,

p ∣ m

q ∣ m

), the identity

(m^{e})^{d} \equiv m (mod n)

still holds. This can be verified by working modulo

p

and modulo

q

separately and combining the results using the Chinese Remainder Theorem (Article 5).

4 The security guarantee: the hardness of factoring

Remark 7 (Why RSA is secure).

An attacker knows the public key

(n, e)

but needs the private key

d

. Computing

d

requires

φ (n) = (p - 1) (q - 1)

, and knowing

φ (n)

requires factoring

n

into

p \times q

The hardness of integer factorization: computing

n = p \times q

is instantaneous, but recovering

p

and

q

from

n

(when both are large) is, by all known classical algorithms, extraordinarily expensive. This asymmetry is the foundation of RSA's security.

Remark 8 (The computational gap).

Multiplication: $p \times q$ runs in $O ((lo g n)^{2})$ time – trivial.
Factoring: the fastest known classical algorithm (the general number field sieve) runs in $exp (O ((lo g n)^{1/3} (lo g lo g n)^{2/3}))$ – sub-exponential but still infeasible for large $n$ .
Factoring a 2048-bit modulus $n$ is estimated to take thousands of years with current hardware.

It is this asymmetry – multiplication is easy but factoring is hard– that sustains the security of RSA.

5 How each article contributes to RSA

Remark 9 (The theorems of this series at work).

Every article in this series corresponds to a component of the RSA system:

Article 1 (Modular arithmetic): all RSA computations live in the world of $mod n$ .
Article 2 (Euclidean algorithm): the private key $d$ is computed as the modular inverse of $e$ modulo $φ (n)$ .
Article 3 (Fundamental Theorem of Arithmetic): the uniqueness of prime factorization is the premise on which security rests.
Article 4 (Fermat–Euler): Euler's theorem proves that decryption recovers the plaintext.
Article 5 (Chinese Remainder Theorem): CRT-RSA performs decryption modulo $p$ and modulo $q$ separately, then combines, for a significant speedup.
Article 6 (Quadratic residues): the Rabin cryptosystem (a variant of RSA) rests on the theory of quadratic residues.
Article 7 (Continued fractions): Wiener's attack on RSA with a small private key $d$ uses continued fractions to crack the system.

6 A worked example

Example 10 (RSA with small numbers).

Key generation: $p = 61$ , $q = 53$ ; $n = 3233$ ; $φ (n) = 60 \times 52 = 3120$ .
Choose $e = 17$ ( $g cd (17, 3120) = 1$ ).
Extended Euclidean algorithm: $17 d \equiv 1 (mod 3120)$ yields $d = 2753$ (since $17 \times 2753 = 46801 = 15 \times 3120 + 1$ ).
Encryption: $m = 65 \Rightarrow c \equiv 6 5^{17} (mod 3233) = 2790$ .
Decryption: $279 0^{2753} mod 3233 = 65$ (computed by repeated squaring).

7 Looking ahead: the quantum threat

Remark 11 (Quantum computers and RSA).

Shor's algorithm factors integers in polynomial time on a quantum computer. If a sufficiently powerful quantum machine is built, RSA will be broken. This prospect has spurred intense research into post-quantum cryptography– lattice-based, code-based, isogeny-based, and other schemes believed to resist quantum attacks.

Remark 12.

Yet even if RSA were to fall, the mathematical beauty underlying it would remain intact. Modular arithmetic, the Euclidean algorithm, Fermat's little theorem, the Chinese Remainder Theorem – these are truths that have stood for millennia and will continue to find applications far beyond cryptography.

8 Series summary

Remark 13.

Let us look back over the eight articles of this Number Theory "Between the Lines" series:

Modular arithmetic: the projection that discards information. The ring $Z / n Z$ .
The Euclidean algorithm: an $O (lo g)$ -time algorithm built on an invariant. Bé
The Fundamental Theorem of Arithmetic: uniqueness of prime factorization, resting on Euclid's lemma.
Fermat's little theorem: the group structure of $(Z / p Z)^{*}$ . The inverse $a^{p - 2}$ .
The Chinese Remainder Theorem: divide and conquer in algebra. $Z / mn Z ≅ Z / m Z \times Z / n Z$ .
Quadratic residues: the 2-to-1 nature of $x \mapsto x^{2}$ . The law of quadratic reciprocity.
Continued fractions: the Euclidean algorithm from another angle. Best rational approximations and Pell's equation.
RSA cryptography: the confluence of every theorem in the series.

Number theory begins with the simplest objects imaginable – the integers

1, 2, 3, \dots

– yet it reveals structures of astonishing depth and breadth. If this series has shed light on the "why" that textbooks leave between the lines, it has served its purpose.

Number Theory Mathematics Between the Lines

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Number theory meets cryptography: why RSA works and what makes it secure

Folio Official

March 1, 2026

1 The idea behind public-key cryptography

Remark 1 (The key-distribution problem).

Traditional (symmetric-key) cryptography requires the sender and receiver to share a secret key. But sharing a key securely requires an already-secure channel – a chicken-and-egg problem.

2 How RSA works

Definition 2 (RSA key generation).

Choose two large random primes $p$ and $q$ , and compute $n = pq$ .
Compute $φ (n) = (p - 1) (q - 1)$ (Euler's totient function).
Choose $e$ with $g cd (e, φ (n)) = 1$ (the standard choice is $e = 65537$ ).
Compute $d$ satisfying $e d \equiv 1 (mod φ (n))$ (via the extended Euclidean algorithm).

Public key:

(n, e)

. Private key:

d

Remark 3.

Let us identify the tools used in this construction:

Primes (Article 3): the choice of $p$ and $q$ .
Euler's totient function (Article 4): computing $φ (n)$ .
Extended Euclidean algorithm (Article 2): computing $d$ .

Definition 4 (RSA encryption and decryption).

Represent the plaintext as an integer

m

with

0 \leq m < n

Encryption: $c \equiv m^{e} (mod n)$ (using the public key $e$ ).
Decryption: $m \equiv c^{d} (mod n)$ (using the private key $d$ ).

3 Why decryption recovers the plaintext: Euler's theorem is the key

Why does $c^{d} \equiv m (mod n)$ hold?

Theorem 5 (Correctness of RSA).

g cd (m, n) = 1

, then

(m^{e})^{d} \equiv m (mod n)

Proof.

Since

e d \equiv 1 (mod φ (n))

, write

e d = 1 + k φ (n)

for some integer

k

. Then

(m^{e})^{d} = m^{e d} = m^{1 + k φ (n)} = m \cdot (m^{φ (n)})^{k} .

By Euler's theorem (Article 4),

m^{φ (n)} \equiv 1 (mod n)

. Therefore

(m^{e})^{d} \equiv m \cdot 1^{k} = m (mod n) .

□

Remark 6.

When

g cd (m, n) \neq = 1

(that is,

p ∣ m

q ∣ m

), the identity

(m^{e})^{d} \equiv m (mod n)

still holds. This can be verified by working modulo

p

and modulo

q

separately and combining the results using the Chinese Remainder Theorem (Article 5).

4 The security guarantee: the hardness of factoring

Remark 7 (Why RSA is secure).

An attacker knows the public key

(n, e)

but needs the private key

d

. Computing

d

requires

φ (n) = (p - 1) (q - 1)

, and knowing

φ (n)

requires factoring

n

into

p \times q

The hardness of integer factorization: computing

n = p \times q

is instantaneous, but recovering

p

and

q

from

n

(when both are large) is, by all known classical algorithms, extraordinarily expensive. This asymmetry is the foundation of RSA's security.

Remark 8 (The computational gap).

Multiplication: $p \times q$ runs in $O ((lo g n)^{2})$ time – trivial.
Factoring: the fastest known classical algorithm (the general number field sieve) runs in $exp (O ((lo g n)^{1/3} (lo g lo g n)^{2/3}))$ – sub-exponential but still infeasible for large $n$ .
Factoring a 2048-bit modulus $n$ is estimated to take thousands of years with current hardware.

It is this asymmetry – multiplication is easy but factoring is hard– that sustains the security of RSA.

5 How each article contributes to RSA

Remark 9 (The theorems of this series at work).

Every article in this series corresponds to a component of the RSA system:

Article 1 (Modular arithmetic): all RSA computations live in the world of $mod n$ .
Article 2 (Euclidean algorithm): the private key $d$ is computed as the modular inverse of $e$ modulo $φ (n)$ .
Article 3 (Fundamental Theorem of Arithmetic): the uniqueness of prime factorization is the premise on which security rests.
Article 4 (Fermat–Euler): Euler's theorem proves that decryption recovers the plaintext.
Article 5 (Chinese Remainder Theorem): CRT-RSA performs decryption modulo $p$ and modulo $q$ separately, then combines, for a significant speedup.
Article 6 (Quadratic residues): the Rabin cryptosystem (a variant of RSA) rests on the theory of quadratic residues.
Article 7 (Continued fractions): Wiener's attack on RSA with a small private key $d$ uses continued fractions to crack the system.

6 A worked example

Example 10 (RSA with small numbers).

Key generation: $p = 61$ , $q = 53$ ; $n = 3233$ ; $φ (n) = 60 \times 52 = 3120$ .
Choose $e = 17$ ( $g cd (17, 3120) = 1$ ).
Extended Euclidean algorithm: $17 d \equiv 1 (mod 3120)$ yields $d = 2753$ (since $17 \times 2753 = 46801 = 15 \times 3120 + 1$ ).
Encryption: $m = 65 \Rightarrow c \equiv 6 5^{17} (mod 3233) = 2790$ .
Decryption: $279 0^{2753} mod 3233 = 65$ (computed by repeated squaring).

7 Looking ahead: the quantum threat

Remark 11 (Quantum computers and RSA).

Remark 12.

8 Series summary

Remark 13.

Let us look back over the eight articles of this Number Theory "Between the Lines" series:

Modular arithmetic: the projection that discards information. The ring $Z / n Z$ .
The Euclidean algorithm: an $O (lo g)$ -time algorithm built on an invariant. Bé
The Fundamental Theorem of Arithmetic: uniqueness of prime factorization, resting on Euclid's lemma.
Fermat's little theorem: the group structure of $(Z / p Z)^{*}$ . The inverse $a^{p - 2}$ .
The Chinese Remainder Theorem: divide and conquer in algebra. $Z / mn Z ≅ Z / m Z \times Z / n Z$ .
Quadratic residues: the 2-to-1 nature of $x \mapsto x^{2}$ . The law of quadratic reciprocity.
Continued fractions: the Euclidean algorithm from another angle. Best rational approximations and Pell's equation.
RSA cryptography: the confluence of every theorem in the series.

Number theory begins with the simplest objects imaginable – the integers

1, 2, 3, \dots

– yet it reveals structures of astonishing depth and breadth. If this series has shed light on the "why" that textbooks leave between the lines, it has served its purpose.

Number Theory Mathematics Between the Lines

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Number theory meets cryptography: why RSA works and what makes it secure

1 The idea behind public-key cryptography

2 How RSA works

3 Why decryption recovers the plaintext: Euler's theorem is the key

4 The security guarantee: the hardness of factoring

5 How each article contributes to RSA

6 A worked example

7 Looking ahead: the quantum threat

8 Series summary

Share your expertise with the world

More from Folio Official

Why primes are the atoms of the integers: what the Fundamental Theorem of Arithmetic really says

The Chinese Remainder Theorem: why simultaneous congruences can be merged

What does it mean to "divide evenly"? Why number theory begins with mod

Why the Euclidean algorithm finds the greatest common divisor: from subtraction to division

Number theory meets cryptography: why RSA works and what makes it secure

1 The idea behind public-key cryptography

2 How RSA works

3 Why decryption recovers the plaintext: Euler's theorem is the key

4 The security guarantee: the hardness of factoring

5 How each article contributes to RSA

6 A worked example

7 Looking ahead: the quantum threat

8 Series summary

Share your expertise with the world

More from Folio Official

Why primes are the atoms of the integers: what the Fundamental Theorem of Arithmetic really says

The Chinese Remainder Theorem: why simultaneous congruences can be merged

What does it mean to "divide evenly"? Why number theory begins with mod

Why the Euclidean algorithm finds the greatest common divisor: from subtraction to division