Number Theory for Cryptography for Beginners

​A Quick Story Before We Begin

The math that keeps your bank password private is roughly two thousand years old, and it goes by the humble name number theory. This guide is about that math: the small, surprising corner of whole-number arithmetic that almost every secure connection on the internet depends on. We will start from absolute scratch, and by the end you will understand not just what number theory does for cryptography, but why it works, and why smart people are quietly building replacements for it right now.

To see why this matters, imagine you and a friend want to pass secret notes in class. The old way is simple. You agree on a secret code word. From then on, every note is encoded by swapping each letter for the one three steps ahead in the alphabet. "HELLO" becomes "KHOOR." Anyone who knows the rule can read the note. Anyone who doesn't, can't.

This kind of code is called symmetric cryptography, and people have been using versions of it for thousands of years. Julius Caesar used it. The Enigma machine was a fancy version of it. The problem is always the same: how do you and your friend agree on the secret rule in the first place? You have to whisper it somewhere. And that whisper can be overheard.

For most of human history, the answer was: meet in person first. Share the secret. Then go your separate ways and use it.

But the modern internet doesn't work that way. When your browser opens a connection to a bank's website, you and the bank have never met. There's no alley to whisper in. There is only the open channel. And yet, somehow, the connection is private.

How? Two researchers, Whitfield Diffie and Martin Hellman, sketched the answer in a 1976 paper titled "New Directions in Cryptography." Their idea is one of the most beautiful in computer science. It uses math, and in particular, that corner of math that had been considered useless: the study of whole numbers, called number theory.

This guide is about that idea. We will walk through it slowly, in plain English, with analogies where they help.

---

​What You'll Find Here

• The puzzle of how two strangers can share a secret
• The one picture that captures the whole idea
• The minimum amount of math you need, with no more
• How Diffie–Hellman, RSA, and elliptic-curve cryptography actually work
• What happens when you visit a website
• Why everyone is racing to replace these algorithms

---

​The Puzzle That Baffled Everyone

Let's set the stage. Alice wants to send a private message to Bob, over a channel that Eve (an eavesdropper) is listening to. They have never met. They share no prior secret. They can only send messages through the public channel.

Symmetric cryptography can't help. If Alice and Bob use the same secret key, Eve can intercept the key when they try to share it. So they'd need to share another key to protect the first key, and so on, forever.

The puzzle is: how can two people who share no secret end up with a shared secret, by sending messages back and forth in public?

For centuries, the conventional wisdom was that they can't. Any message they send in public, Eve can see. Any computation they can do, Eve can do. There is no asymmetry to exploit.

Diffie and Hellman found one. The trick is to use a math operation that is easy one way and hard the other. We call this a one-way function. If there's a secret shortcut to undo it, we call it a trapdoor function.

Picture this. Mixing two colors of paint is easy. Squinting at the result and figuring out the exact original colors is genuinely hard. You can always go forward. You can almost never go back.

That is the entire engine. Everything else in this tutorial is engineering around that one insight.

​What "Trapdoor Function" Actually Means

The phrase trapdoor function sounds mysterious, but it just means a function that is easy to compute going one way and very hard to reverse, unless you happen to know a special piece of secret information (the trapdoor) that makes the reverse direction easy too.

A familiar example from everyday life: a combination padlock. To lock it, you spin the dials to a random new combination and snap it shut. Anyone can do that in a second. To unlock it, you'd have to try every possible combination, 10,000 of them on a typical four-dial lock, unless you know the right combination. The "trapdoor" is the secret combination.

A good trapdoor function works the same way, but with numbers. RSA is the textbook example:

• Easy direction: multiply two large primes $p$ and $q$ to get $N = p \times q$. Even a child can do this on paper.
• Hard direction: given only $N$, recover $p$ and $q$. This is the factoring problem, and it is infeasible for large enough $N$.
• The trapdoor: if you happen to know $p$ and $q$ already (because you generated the key), you can reverse the function instantly.

The whole art of public-key cryptography is finding mathematical "padlocks" whose structure makes the easy direction astronomically faster than the hard direction, and where some piece of secret information acts as the combination.

So when you hear "trapdoor function" in this tutorial, remember the padlock. Easy to lock, hard to unlock without the secret, and the only thing protecting every message you've ever sent over an encrypted connection.

---

​The One Picture You Need to Remember

Before we go further, take a look at this:

This single picture is the whole story. On the left, two primes, say $61$ and $53$. On the right, their product, $3{,}233$. The thick green arrow going left to right is multiply: trivially fast, you can do it on a napkin. The thin red dashed arrow going right to left is factor: impossibly hard, in general.

That asymmetry, easy one way and hard the other, is the one-way function that makes public-key cryptography possible. Every algorithm we will discuss, from RSA to Diffie–Hellman to elliptic curves, is a different choice of which easy-and-hard operation to use.

---

​The Minimum Amount of Math You Need

Cryptography uses math, but only a small slice of math. The whole toolkit is a few ideas about how integers behave.

We will walk through them slowly, with analogies where they help.

​Primes: The Atoms of Numbers

A prime number is a whole number greater than 1 that has no divisors other than 1 and itself. The first few primes are 2, 3, 5, 7, 11, 13, 17, 19, 23.

You can think of primes as the atoms of the integer world. Just as every molecule is made of atoms, every whole number is made by multiplying primes together. The number 60 is $2 \times 2 \times 3 \times 5$. The number 91 is $7 \times 13$. And here is the key fact: this decomposition is unique. Every number has exactly one prime factorization, up to ordering. This is called the Fundamental Theorem of Arithmetic, and it has been known since ancient Greece.

It is precisely because prime factorizations are unique that they are useful. There is only one way to take a big number apart into primes.

​Modular Arithmetic: Clock Math

You already know modular arithmetic. You just don't call it that.

When you tell time, 10 o'clock plus 5 hours is 3 o'clock, not 15 o'clock. That's because clocks "wrap around" at 12. The number 12 is called the modulus, and we write $10 + 5 \equiv 3 \pmod{12}$. The triple bar $\equiv$ means "is equivalent to, in this wrapped-around world."

We can do arithmetic modulo any positive integer. $17 \bmod 12$ is $5$ (because 17 is 12 plus 5). $2^{10} = 1024 \bmod 10$ is $4$ (because 1024 ends in 4). Modular arithmetic is ordinary arithmetic in a finite, circular world.

Why does this matter? Because in a finite world, powers are periodic. Pick any number $a$ and any modulus $n$, and the sequence $a^1, a^2, a^3, \ldots$ will eventually loop. With a prime modulus $p$ and $a$ not divisible by $p$, the loop length is at most $p - 1$. This periodicity is the foundation of nearly every cryptographic trick we will discuss.

​Modular Inverses: The "Undo" Button

In regular arithmetic, every nonzero number has a multiplicative inverse: $1/3$, the thing that, when multiplied by 3, gives you 1.

In modular arithmetic, the same idea works, but only sometimes. The number $3$ has an inverse modulo $7$, and it is $5$, because $3 \times 5 = 15 \equiv 1 \pmod{7}$. The number $4$ has no inverse modulo $6$, because $4$ and $6$ share a common factor (2), and once two numbers share a factor, you can never multiply one of them to "undo" the other.

The rule is simple: an integer $a$ has a multiplicative inverse modulo $n$ if and only if $a$ and $n$ share no common factor other than 1. We say they are coprime.

There is an efficient algorithm, the Euclidean algorithm, that finds modular inverses quickly. It is a clever process of repeated remainders, dating back to ancient Greece. If you remember doing long division in school, you have the basic idea.

A Slow-Motion Walkthrough

Let's find the inverse of $3$ modulo $7$ by hand, so the process stops being abstract.

We want a number $x$ such that $3 \times x \equiv 1 \pmod{7}$. Let's try values:

• $3 \times 1 = 3$, not 1.
• $3 \times 2 = 6$, not 1.
• $3 \times 3 = 9 = 7 + 2 \equiv 2 \pmod{7}$, not 1.
• $3 \times 4 = 12 = 7 + 5 \equiv 5 \pmod{7}$, not 1.
• $3 \times 5 = 15 = 14 + 1 \equiv 1 \pmod{7}$. There it is. The inverse of $3$ modulo $7$ is $5$.

You can verify it: $3 \times 5 = 15$, and $15$ leaves a remainder of $1$ when divided by $7$.

For a real-world size like RSA, brute-force guessing like this would take longer than the universe has existed. That is where the Euclidean algorithm comes in: a fast procedure that walks down the problem using repeated remainders. The intuition is that if you have $a$ and $n$ and you want to find $x$ with $a \times x \equiv 1 \pmod{n}$, you can do long division on $n \div a$, then on the remainder, then on the next remainder, building up a sequence of equations that lets you "peel" the answer out. It is a 2,300-year-old trick that still powers modern key generation. The detailed steps are a delight; for now, the take-away is this: yes, finding modular inverses is genuinely fast, even for numbers with hundreds of digits.

Here is the deeper why: a modular inverse exists precisely when $a$ and $n$ are coprime. If they share a common factor $d > 1$, then every product $a \times x$ is a multiple of $d$, so it can never be a multiple of $n$ (which is what "$\equiv 1 \pmod{n}$" requires, since 1 is not a multiple of $d$). The condition isn't arbitrary. It falls right out of the definition.

​Fermat's Little Theorem and Euler's Theorem

Two theorems do the heavy lifting in modular arithmetic.

Fermat's little theorem: If $p$ is prime and $a$ is not divisible by $p$, then

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

In other words, if you take any number and raise it to the $(p-1)$-th power, you get 1, as long as you are working modulo a prime. Always.

Euler's theorem: If $a$ and $n$ are coprime, then

$a^{\varphi(n)} \equiv 1 \pmod{n}$

where $\varphi(n)$ is Euler's totient function. It counts how many numbers up to $n$ are coprime to $n$. For a prime $p$, $\varphi(p) = p - 1$. For the product of two distinct primes, $\varphi(p \times q) = (p - 1)(q - 1)$.

These two theorems look like party tricks. They aren't. They are the reason decryption works in RSA, the reason digital signatures verify, the reason key exchange produces a shared secret. Every public-key algorithm you have heard of leans on one of these.

Why the (p − 1) Exponent Is Special

Fermat's little theorem says: take any number $a$ (that doesn't share a factor with the prime $p$), and keep multiplying it by itself $p - 1$ times. The result is always 1, modulo $p$. Always.

There is a good reason for it, and the reason illuminates a deep idea: the order of an element.

Imagine the set of all numbers that are coprime to $p$: $\{1, 2, 3, \ldots, p - 1\}$. There are $p - 1$ of them. Now pick any $a$ from this set, and start multiplying it by itself, taking every result modulo $p$:

$a^1 \bmod p,\quad a^2 \bmod p,\quad a^3 \bmod p,\quad \ldots$

Since there are only $p - 1$ possible values, this sequence must eventually repeat. The first time it returns to 1, we say the sequence has "closed the loop." The length of that loop, the smallest positive $k$ with $a^k \equiv 1 \pmod{p}$, is called the order of $a$. By a famous result (Lagrange's theorem, in the world of group theory), the order of any element always divides the size of the group. The group has size $p - 1$, so the order of $a$ divides $p - 1$. That means $a^{p-1}$ is $a$ raised to a multiple of the order, which lands you at 1 again.

That is the whole reason. The exponent $(p - 1)$ is special because it equals the size of the group, and the size of the group is always a multiple of any element's loop length. Fermat's little theorem is a clean statement of this fact for prime moduli.

What Euler's Totient Function Is Counting

Euler's theorem is the same idea, but for any modulus $n$ (not just primes). The exponent that works isn't $n - 1$ anymore. It is $\varphi(n)$, Euler's totient.

What is $\varphi(n)$ counting? It is the number of integers in $\{1, 2, \ldots, n\}$ that are coprime to $n$. For example:

• $\varphi(10) = 4$ because the numbers coprime to 10 are $\{1, 3, 7, 9\}$.
• $\varphi(7) = 6$ because every number from 1 to 6 is coprime to the prime 7.
• $\varphi(p \times q) = (p - 1)(q - 1)$ because the count of numbers coprime to both primes is exactly that product.

Why is this the right number to use? The same "group size" reason as before. The set of all integers coprime to $n$, under multiplication modulo $n$, forms a group whose size is exactly $\varphi(n)$. So by the same Lagrange-style argument, raising any element of that group to the $\varphi(n)$-th power must return to 1.

The reason this matters so much for RSA: when we choose $n = p \times q$, we can compute $\varphi(n) = (p - 1)(q - 1)$ cheaply only if we know $p$ and $q$. Someone who has only $n$ cannot compute $\varphi(n)$ without first factoring $n$, and that is exactly the hard problem that makes RSA secure. The whole security of RSA rests on the asymmetry between "knows $p$ and $q$" and "doesn't."

So when you see $\varphi(n)$ in a cryptography paper, remember: it is counting something, that count is special, and the specialness is what makes the math go round.

​Groups and Generators

A group, in math, is a set of things with an operation that combines any two of them to give a third, where the operation is associative, has an "identity" element, and every element has an inverse. The integers modulo $n$ under addition form a group. The coprime integers modulo $n$ under multiplication form a group too, called $(\mathbb{Z}/n\mathbb{Z})^*$, and it is the stage on which most public-key cryptography is performed.

A generator $g$ of a group is an element whose powers visit every element of the group. Pick $g$, and the sequence $g^0, g^1, g^2, \ldots, g^{m-1}$ (where $m$ is the size of the group) hits every element exactly once.

This matters because, in such a group, computing $g^x$ is fast (it is a process called repeated squaring). But going the other way, given $g^x$, finding $x$, is the discrete logarithm problem, and it is believed to be infeasible for well-chosen groups. That asymmetry is the second of our one-way functions.

Why One Element Can Reach the Whole Group

A beginner often reads "generator" and pictures a power source, a thing that creates everything else. The actual idea is more humble and more useful than that.

Imagine a clock with $m$ numbered positions, $0$ through $m - 1$. A "generator" is a step size such that if you start at position $0$ and keep adding that step (taking the result modulo $m$), you visit every single position before getting back to $0$.

For a 12-hour clock, the step size 7 works as a generator. Starting at 0: 0, 7, 2, 9, 4, 11, 6, 1, 8, 3, 10, 5, 0. All 12 positions, exactly once. The step size 6, by contrast, is not a generator on a 12-hour clock. Starting at 0 and adding 6 gives you 0, 6, 0, 6, 0, 6. You only ever see two positions.

Generators in cryptography work exactly the same way. The group $(\mathbb{Z}/p\mathbb{Z})^*$ is like a "clock" with $p - 1$ positions, and a generator $g$ is a step size that walks through all of them. When you compute $g^x$, you are saying "start at 1 (the identity), take the step $g$ exactly $x$ times, and tell me where you end up." Going forward is fast. Going backward, given only the ending position, means trying every possible $x$ from 0 to $p - 2$, and for a 2048-bit prime, that is a search space larger than the number of atoms in the observable universe.

A useful side note: not every number is a generator. For $(\mathbb{Z}/p\mathbb{Z})^*$, the number of generators is $\varphi(p - 1)$, which is usually large but not equal to $p - 1$. Real-world systems pick a generator from a published list of well-vetted values.

Sub-Exponential vs. Exponential: Two Words That Matter

When cryptographers say an attack is "sub-exponential," they mean something precise. It runs in time between polynomial and exponential in the size of the key. For a 2048-bit key, "polynomial" would be like $n^3$ operations, a few trillion. "Exponential" would be like $2^n$, astronomically more than the age of the universe can offer. Sub-exponential sits somewhere in between, growing much faster than polynomial but much slower than full exponential.

The General Number Field Sieve, the best known attack on RSA and classical Diffie–Hellman, is sub-exponential. Its running time is roughly $\exp(c \cdot (\log n)^{1/3} \cdot (\log \log n)^{2/3})$ for some small constant $c$. That looks awful, but it is much better than $2^n$. It is the difference between "the world's fastest supercomputers might crack a 600-digit number in 100 years" and "no computer ever built could crack it before the heat death of the universe."

Pollard's rho and its variants, the best known attacks on the elliptic-curve discrete log, are fully exponential, about $\sqrt{n}$ operations for a group of size $n$. For a 256-bit group, that is $2^{128}$ operations. Sub-exponential attacks don't exist (yet) for the standard elliptic curves. That is why a 256-bit elliptic-curve key is considered as strong as a 3072-bit RSA key, even though the ECC key is 12 times shorter.

The practical upshot: when someone tells you a problem is sub-exponential, breathe a little. When they tell you it is fully exponential, you can rest easy. The distinction between "very hard" and "astronomically hard" is the gap that makes elliptic curves so attractive.

---

​The Three Hard Problems

Public-key cryptography today rests on three computational problems that we don't know how to solve quickly. We have been trying for decades, and the world's best mathematicians have failed. There is a theoretical worry that quantum computers might one day change this (we will get to that), but for now these problems are the bedrock.

​Hard Problem 1: Factoring Big Numbers

The problem: Given a large integer $N$ that is the product of two primes $p$ and $q$, find $p$ and $q$.

Why it's hard: The best known classical algorithm is the General Number Field Sieve. For a 2048-bit $N$ (the size used in real RSA today), the algorithm's running time is so astronomical that no existing computer, no cluster of computers, no plausible extension of Moore's law, can complete it within the age of the universe.

The current factoring record, as of 2024, is 250 decimal digits (829 bits), set in 2020. RSA-2048, used in production, is 617 decimal digits. There is a yawning gap between the record and the production target, and there is no public reason to think the gap will close soon.

RSA rests on this problem.

​Hard Problem 2: The Discrete Logarithm Problem

The problem: Given a prime $p$, a generator $g$ of the group $(\mathbb{Z}/p\mathbb{Z})^*$, and an element $h = g^x \bmod p$, find $x$.

Why it's hard: The best known classical algorithm is also a variant of the Number Field Sieve. The largest DLP in a prime field ever publicly solved is 795 bits, set in 2019. Like with factoring, the production target is much larger.

The Diffie–Hellman family of protocols rests on this problem.

​Hard Problem 3: The Elliptic-Curve Discrete Logarithm

The problem: Given an elliptic curve $E$, a point $P$ on $E$, and another point $Q = P + P + \ldots + P$ (added to itself some unknown number of times), find that number.

Why it's hard: The best known attack runs in time proportional to the square root of the group size. For a 256-bit group, that is $2^{128}$ operations, beyond the reach of any classical computer. (The name of the underlying algorithm is Pollard's rho, a clever randomized search procedure; for our purposes, what matters is the $2^{128}$ cost.)

Notice the difference. The first two problems are sub-exponential to attack, meaning faster than the brute-force $2^{\text{bit-length}}$, but still infeasible. The third is exponential to attack, meaning we have no known shortcut at all. The result: elliptic-curve cryptography achieves the same security as RSA or Diffie–Hellman with far smaller keys. A 256-bit elliptic-curve key is roughly equivalent to a 3072-bit RSA key.

Elliptic-curve cryptography rests on this problem.

---

​How the Algorithms Actually Work

Now we put the math to use. Three algorithms cover the vast majority of public-key cryptography in the world. We will walk through each one step by step.

​Diffie–Hellman: The Original Key Exchange

This is the protocol that started it all. Alice and Bob want to agree on a shared secret, but they have no prior shared secret. They can only chat in public, and Eve is listening.

The public setup (everyone knows this):

• A large prime number $p$.
• A generator $g$ of the multiplicative group $(\mathbb{Z}/p\mathbb{Z})^*$.

The protocol:

1. Alice picks a random secret integer $a$, computes $A = g^a \bmod p$, and broadcasts $A$.
2. Bob picks a random secret integer $b$, computes $B = g^b \bmod p$, and broadcasts $B$.
3. Alice receives $B$ and computes $s = B^a \bmod p$.
4. Bob receives $A$ and computes $s = A^b \bmod p$.

Both arrive at the same $s = g^{ab} \bmod p$. Why? Because $(g^b)^a = g^{ba} = g^{ab} = (g^a)^b$. Commutativity of multiplication does the trick.

Eve sees $p$, $g$, $A$, $B$. To recover $s$, she would have to find $a$ from $A$ (a discrete logarithm problem) or find $b$ from $B$. Both are believed to be infeasible for the chosen parameters.

The lesson: neither Alice nor Bob transmitted the secret in a way that lets an eavesdropper recover it, even though every message they exchanged was public. The math did the work.

In 2024, real-world Diffie–Hellman uses primes of at least 2048 bits, and the elliptic-curve variant (ECDH) uses curves of 256 or 384 bits. The elliptic-curve version is roughly an order of magnitude faster and produces much smaller messages.

​RSA: Encryption and Signatures with Trapped Multiplication

Named after its inventors Rivest, Shamir, and Adleman, who published it in 1977.

A note on history: an equivalent scheme was independently invented at GCHQ in 1973 by the British mathematician Clifford Cocks. It was classified and remained unknown publicly until 1997. This is a good reminder that cryptography has a longer and stranger history than its public timeline suggests.

Key generation:

1. Pick two random large primes $p$ and $q$, both roughly the same size.
2. Compute $n = p \times q$. This is the modulus.
3. Compute $\varphi(n) = (p - 1)(q - 1)$. This is Euler's totient of $n$.
4. Pick a public exponent $e$, almost always $65{,}537$. This value is small enough to be fast and large enough to have no special weaknesses.
5. Compute the private exponent $d$ as the modular inverse of $e$ modulo $\varphi(n)$. So $e \cdot d \equiv 1 \pmod{\varphi(n)}$.

The public key is the pair $(n, e)$. The private key is $d$ (and the original primes, which are usually destroyed after key generation because they are no longer needed).

Encryption: to send a message $m$ (an integer less than $n$), compute $c = m^e \bmod n$. The ciphertext is $c$.

Decryption: given $c$, compute $m = c^d \bmod n$.

That is it. The whole algorithm is two lines of math, and yet it is the foundation of encryption on the web.

Why decryption works: By Euler's theorem, since $e \cdot d = 1 + k \cdot \varphi(n)$ for some integer $k$,

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

The modular exponentiation wraps everything around so that decryption unwinds encryption exactly. The trapdoor is the knowledge of $\varphi(n)$, which requires knowing $p$ and $q$, which requires factoring $n$, which is the hard problem.

In practice: Real-world RSA is always used with padding. Textbook RSA is deterministic (the same message always gives the same ciphertext) and vulnerable to a handful of clever attacks. Real systems use schemes like OAEP for encryption and PSS for signatures, standardized in PKCS#1 and FIPS 186-4. As of 2024, NIST recommends RSA keys of at least 2048 bits, with 3072 bits preferred for new deployments.

​Elliptic-Curve Cryptography: Same Idea, More Efficient

An elliptic curve over a finite field is a set of points satisfying an equation of the form

$y^2 = x^3 + ax + b$

The points on this curve, together with a special "point at infinity" used as the identity, form a group. You can add two points on the curve and get a third point on the curve. The geometry is a bit unusual (you draw a line through the two points and reflect the third intersection across the x-axis), but the group operation is well-defined and computable.

Once you have a group, you can do Diffie–Hellman and digital signatures on it. The discrete log problem in this group (the elliptic-curve discrete log problem) is what makes the system secure.

The most popular curves today:

• P-256 (secp256r1): a 256-bit Weierstrass curve, widely used in TLS and SSH.
• Curve25519 / Ed25519: a pair of curves designed by Daniel Bernstein and colleagues for high performance and resistance to implementation mistakes. Used in TLS 1.3, Signal, SSH, and many other places.
• P-384 (secp384r1) and P-521: higher-security NIST curves.
• BLS12-381: a "pairing-friendly" curve used in more advanced protocols like aggregate signatures and zero-knowledge proofs.

Why not pick your own curve? Because some curves are subtly broken. Some have small subgroups that an attacker can exploit. Some have group structures that make the discrete log problem easy. The list of known bad curves is long, and growing. The safe thing to do, the only professional thing to do, is stick to the published, well-vetted standards.

The "Point at Infinity," Demystified

The phrase "point at infinity" tends to stop beginners cold. Where is this point? What does it mean? Why do we need it?

Every group needs an "identity" element, something that, when you combine it with any other element, leaves the other element unchanged. In the integers under addition, the identity is $0$ (because $5 + 0 = 5$). In the integers under multiplication, the identity is $1$ (because $5 \times 1 = 5$).

The elliptic-curve group needs an identity too, and the natural choice, the additive identity, turns out not to be a regular point on the curve. It is the idea of a point that lives "at infinity," the unique place where all the vertical lines of the curve's geometry meet.

Here is the geometric intuition. When you add a point $P$ to itself (the operation $P + P$), you draw the tangent line to the curve at $P$, find where that line hits the curve a third time, and reflect that point across the x-axis. For almost all points on the curve, this works fine. But for one special case, when the tangent line is vertical, "hits the curve a third time" in some abstract sense that's not a real point, and you need something to call the result. That something is the "point at infinity."

The deep reason it is there: adding a point to itself with the "right" geometry should give you back the identity. The point at infinity is the bookkeeping device that makes this work. In every other respect, it behaves exactly like $0$ in regular addition. Adding any real point $P$ to the point at infinity gives you back $P$. That is the whole job of an identity.

You don't need to picture it, and you don't need to draw it. The point at infinity is a notational convenience, like writing 0 in a column of numbers to keep the place values aligned. Cryptography only ever needs to know that this one special placeholder exists, and that adding it to anything leaves that thing unchanged.

​A Note on Digital Signatures

We have talked about encryption (keeping messages secret) and key exchange (agreeing on a shared secret), but there is a third pillar: digital signatures. A signature proves that a specific private key signed a specific message. Anyone with the corresponding public key can verify it, but no one can forge it.

The two most common signature algorithms are RSA-PSS (a signing variant of RSA) and ECDSA / Ed25519 (signing variants of elliptic-curve cryptography). They work in much the same way as the encryption and key-exchange protocols we have seen, but the roles of public and private keys are reversed. Encryption uses the public key to scramble and the private key to unscramble. Signatures use the private key to sign and the public key to verify.

---

​What Happens When You Visit a Website

The math we have discussed is invisible to most people, but it is running every time you load a webpage. Here is the rough sequence when your browser connects to a bank's site.

1. Your browser connects. It asks the bank for its TLS certificate.
2. Authentication. The certificate contains the bank's public key (an RSA or ECDSA key), signed by a trusted certificate authority. Your browser verifies the signature chain back to a root certificate it already trusts. This is a number-theoretic signature check.
3. Key exchange. Your browser and the bank's server perform a (EC)Diffie–Hellman key exchange, deriving a shared symmetric key. The number-theoretic building block here is the hardness of the discrete log problem.
4. Bulk encryption. All the actual data (the page HTML, your password, your account balance) is encrypted with a symmetric cipher like AES-128 or AES-256, using the shared key from step 3. AES is not number-theoretic; it is a symmetric cipher, the modern descendant of the Caesar cipher. It is fast, and it is the workhorse of bulk encryption.
5. Integrity. Every record of data is also authenticated with HMAC-SHA-256 (or similar), which combines a hash function with the shared key to produce a tag that proves the data hasn't been tampered with. Hash functions are also not number-theoretic, but they are the other half of the cryptographic foundation.

Number theory isn't the whole of cryptography. But it is the layer that makes the magic possible: the part that lets two strangers, with no prior contact, end up with a shared secret that no eavesdropper can compute.

---

​The Quantum Question

There is an asterisk on everything we have discussed, and it is a big one. The three hard problems we relied on (factoring, discrete log, elliptic-curve discrete log) are believed to be hard for classical computers. But in 1994, the mathematician Peter Shor showed that a quantum computer, if one existed at sufficient scale, could solve all three in polynomial time.

As of 2024, no such quantum computer exists. Building one requires millions of high-quality physical qubits, and current state-of-the-art machines are in the low thousands. The cryptography community watches this area carefully, and the question of when a cryptanalytically relevant quantum computer will exist is open and important.

The response is post-quantum cryptography (PQC), a new generation of algorithms whose security rests on different mathematical problems that are believed to be hard even for quantum computers. Since 2016, the U.S. National Institute of Standards and Technology (NIST) has been running a public competition to standardize such algorithms. After three rounds of analysis, in July 2022 NIST announced the first set of algorithms to be standardized:

• CRYSTALS-Kyber for key encapsulation, based on the hardness of the Module Learning with Errors (M-LWE) problem over lattices.
• CRYSTALS-Dilithium for digital signatures, also lattice-based.
• FALCON, a second lattice-based signature, using NTRU lattices.
• SPHINCS+, a hash-based signature scheme, with security relying only on the security of a hash function.

As of 2024, these algorithms are in the standardization process; the FIPS drafts are not yet final, but the selections are public and implementations are widely available in OpenSSL, BoringSSL, liboqs, and other libraries. A common near-term strategy is hybrid key exchange, which combines a classical (EC)Diffie–Hellman exchange with a post-quantum key encapsulation so that an attacker has to break both the classical and the post-quantum assumptions to compromise the connection.

This is one of the most important open transitions in all of computer science, and it is happening right now. If you work in software, security, or any field that touches the internet, you will be touched by this migration over the next decade.

---

​Common Misconceptions

Even people who work adjacent to cryptography often carry around a few persistent myths. Let me clear a few of them up.

"RSA is unbreakable." RSA is believed to be hard to break for sufficiently large keys, using classical computers. But it has well-defined limits. With 1024-bit keys, RSA is essentially broken. With 2048-bit keys, it is believed safe against classical attacks. With quantum computers of sufficient size, it falls to Shor's algorithm.

"Bigger keys always mean more security." Mostly true within a given algorithm family, but the relationship is not linear. Doubling your RSA key from 2048 to 4096 bits only raises the attack cost modestly, because the Number Field Sieve's running time depends sub-exponentially on the key size. Meanwhile, a 256-bit elliptic-curve key is already believed to be stronger than a 3072-bit RSA key.

"If the math is hard, the system is secure." Not by itself. Implementation bugs routinely compromise systems with perfect math. The Heartbleed bug, the ROBOT attack, the various Logjam attacks: all of these exploited software flaws, not mathematical weaknesses. This is why using well-tested libraries (NaCl/libsodium, BoringSSL) matters as much as picking the right algorithm.

"Quantum computers will break everything." They will break all widely deployed public-key systems based on factoring and discrete logs. But symmetric ciphers (AES) and hash functions (SHA-256) are only weakened, not broken. Grover's algorithm gives a square-root speedup against brute-force search, which is countered by doubling the key size or hash output. AES-256 and SHA-384 are believed to remain secure even in a post-quantum world.

"All number-theoretic systems are equally secure." Far from it. Some choices of parameters (small subgroups, smooth-order groups, anomalous curves) lead to catastrophic breaks. The list of known bad parameter choices is long, and researchers continue to find more. This is why sticking to published standards matters, and why "rolling your own crypto" remains one of the cardinal sins of the field.

---

​Wrapping Up

Number theory is the quiet backbone of public-key cryptography. By exploiting the asymmetry between easy group operations and apparently hard inverse problems (integer factorization, the discrete logarithm problem, and the elliptic-curve discrete logarithm problem), we get protocols for key exchange, encryption, and digital signatures that underpin the modern internet.

If you remember just three things from this guide, let them be these:

1. The three hard problems, factoring, DLP, and ECDLP, are the foundation. Every public-key algorithm we use today leans on one of them.
2. Key sizes, group choices, and padding schemes matter as much as the underlying algorithm. Big primes and standard curves are not optional.
3. Cryptography is never done. The algorithms we use today will be replaced. The math is what lets us reason rigorously about what is secure and what is not, and the math is also what tells us when it is time to move on.

You started this guide knowing nothing about number theory or cryptography. You now know the core idea, a one-way function, made from the gap between easy multiplication and hard factoring, and you have seen three of its most important instantiations. That is not a small thing. You are now equipped to read the documentation, follow the news, and make sense of the migration that will reshape the field over the next decade.

Welcome to the conversation.

---

​Sources

1. Diffie, W. and Hellman, M., "New Directions in Cryptography," IEEE Transactions on Information Theory, 1976. The paper that started public-key cryptography.
2. Rivest, R. L., Shamir, A., and Adleman, L., "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems," Communications of the ACM, 1978. The original RSA paper.
3. Koblitz, N., "Elliptic Curve Cryptosystems," Mathematics of Computation, 1987. The introduction of ECC.
4. Miller, V. S., "Use of Elliptic Curves in Cryptography," Advances in Cryptology: CRYPTO '85, 1985. The other half of the ECC origin story.
5. Bernstein, D. J., "Curve25519: New Diffie–Hellman Speed Records," 2006. The paper behind the modern default elliptic curve.
6. Menezes, A. J., van Oorschot, P. C., and Vanstone, S. A., Handbook of Applied Cryptography, CRC Press, 1996. Available free online. The canonical reference.
7. Washington, L. C., Elliptic Curves: Number Theory and Cryptography, 2nd ed., Chapman & Hall/CRC, 2008. A standard reference for the elliptic-curve material.
8. NIST Special Publication 800-57 Part 1 Rev. 5, "Recommendation for Key Management," 2020. The current authoritative source on key sizes and lifetimes.
9. NIST Special Publication 800-56B Rev. 2, "Recommendation for Pair-Wise Key-Establishment Using Integer Factorization Cryptography," 2019. The current authoritative RSA usage guide.
10. NIST Special Publication 800-186, "Recommendations for Discrete Logarithm-Based Cryptography: Elliptic Curve Domain Parameters," 2023. The current authoritative ECC usage guide.
11. NIST Post-Quantum Cryptography project page (csrc.nist.gov/projects/post-quantum-cryptography). The canonical source for the PQC standardization effort, including the July 2022 selections of CRYSTALS-Kyber, CRYSTALS-Dilithium, FALCON, and SPHINCS+.
12. Cornell Mathematics, "Primes, Modular Arithmetic and Public Key Cryptography" (course notes). Worked examples of RSA with small primes.
13. The Renegade Coder, "Understanding the Number Theory Behind RSA Encryption," May 2020. An accessible walkthrough.
14. Shor, P. W., "Algorithms for Quantum Computation: Discrete Logarithms and Factoring," Proceedings of FOCS '94, 1994. The quantum algorithm that started the post-quantum conversation.
15. OpenSSL documentation (openssl.org/docs). For current best practices and parameter recommendations.