# Elliptic Curves over Finite Fields

What Elliptic Curves Look Like in Finite Fields?

When we usually think about elliptic curves like $$y^2 = x^3 + 7$$ we imagine a smooth continuous curve. But this only happens when $x$ and $y$ can take any real values. In a finite field, things change completely. If we work modulo a prime $p$, we only allow values from $$\{0,1,2,\ldots, p-1\}$$ So instead of a smooth curve, we get a collection of scattered points on a grid.

For example, in $$y^2 = x^3 + 7 \pmod {23},$$ we check each $x \in \{0,1,2,\ldots, 22\}$. For each $x$, we compute $x^3 + 7 \text{ mod } 23$, and then check if that value is a **square modulo 23** (because it must equal $y^2$). If it is, we get one or two valid $y$ values. If not, we get **no point at all**. This is why the graph looks like **random dots with gaps** instead of a smooth curve.

|  |
|:--:|
| _{Figure 1: $y^2 = x^3 + 7 \pmod{23}$} |

#### Why There Are Gaps

Not every value of $$x^3 + 7 \pmod {23}$$ has a square root in the finite field. For example, numbers like $4$ are squares since $2^2 = 4 \pmod {23}$, but many numbers are not squares. So if $$x^3+7 \equiv 15 \pmod {23}$$ and $15$ is not a quadratic residue modulo 23, then there is no value of $y$ such that $$y^2 \equiv 15 \pmod {23}$$ Hence, no point is plotted for that $x$. This is why the elliptic curve over a finite field appears as a set of scattered valid points rather than a continuous curve.

### How Changing the Prime $p$ Changes the Curve

If we change the prime $p$, the elliptic curve $$y^2 \equiv x^3 + 7 \pmod p$$ changes because the set of allowed values $\{0,1,2, \ldots, p-1\}$ changes.
- For small $p$ (like $11$): there are very few values $\rightarrow$ very few points $\rightarrow$ simple pattern
- For medium $p$ (like $23$): more values $\rightarrow$ more points $\rightarrow$ more visible structure
- For larger $p$ (like $31,41$): many values $\rightarrow$ many points $\rightarrow$ looks dense and random

The number of points on the curve is roughly around $p$, so as $p$ increases, the number of valid $(x,y)$ points also increases.

In real cryptography, $p$ is extremely large (more than $200$ bits), so the curve is just a very large finite set of points and cannot be visualized.

|  |
|:--:|
| _{Figure 2: $y^2 = x^3 + 7 \pmod{11}$} |

|  |
|:--:|
| _{Figure 3: $y^2 = x^3 + 7 \pmod{23}$} |

|  |
|:--:|
| _{Figure 4: $y^2 = x^3 + 7 \pmod{31}$} |

|  |
|:--:|
| _{Figure 5: $y^2 = x^3 + 7 \pmod{41}$} |

### Field Element

A **field element** is just a number inside modulo arithmetic.

For example, in mod $11$: $$\{0,1,2, \ldots, 10\}$$ There are no negative numbers here. Instead: $$ -7 \equiv 4 \pmod {11}$$ because $$7 + 4 \equiv 0 \pmod {11}$$ So every number has an **additive inverse**.

Also, every non-zero number has a **multiplicative inverse**:

Example in mod $23$: $$4 \cdot 6 \equiv 1 \pmod {23}$$ So $6$ is the inverse of $4$.

#### Elliptic Curve Points Form a Group

All the point that satisfy $$y^2 = x^3 + 7 \pmod p$$ together form a **group** under elliptic curve addition.

This group has:
- Closure (adding two points gives another point)
- Associativity
- Identity element (point at infinity)
- Inverse (reflection across x-axis)

Even though the plot looks random, the points follow a strict algebraic structure.

### Cyclic Group

For many useful elliptic curves, the group is cyclic.

his means there exists a special point $G$ (called a generator) such that every point can be written as: $$nG = \underbrace{G + G + \cdots + G}_{n \text{ times}}$$ So instead of dealing with many points separately, everything comes from one point.

Example idea:
- $G$
- $2G$
- $3G$
- $4G$
- $\ldots$
- Eventually cycles through all points

#### Connection to Regular Modular Arithmetic

This behaves similar to numbers modulo $p$: $$ 5 + 7 \equiv 12 \pmod p$$ On elliptic curves: $$ 5G + 7G = 12G$$ So there is a **structure-preserving relationship (homomorphism)** between numbers and points.

## BN128 Curve

The BN128 elliptic curve (used in Ethereum for verifying zero-knowledge proofs) is defined by the equation $$y^2=x^3 + 3 \pmod p$$ where$$p=21888242871839275222246405745257275088696311157297823662689037894645226208583.$$ Here, $p$ is called the **field modulus**, which means all calculations (addition, multiplication, etc.) are done modulo $p$. This makes all values of $x$ and $y$ lie in the finite set $$\{0,1,2,\ldots,p-1\}$$. This number $p$ is extremely large (around $256$ bits), which makes the curve secure and useful for cryptography.

#### Field Modulus vs Curve Order

It is important not to confuse the **field modulus** $p$ with the **curve order**.
- The field modulus $p$ defines the number system we are working in.
- The curve order is the total number of valid points $(x,y)$ that satisfy the equation.

For BN128, the curve order is: $$21888242871839275222246405745257275088548364400416034343698204186575808495617.$$

So:
- $p \rightarrow$ defines the field
- curve order $\rightarrow$ counts the number of points on the curve

These two numbers are different but both very important. The reason for we using smaller modulus for learning is because $p$ in BN128 is extremely large, it is not practical to manually compute or visualize points. So, to understand the idea, we use a smaller example like $$y^2 = x^3 + 3 \pmod {11}$$ This keeps the same structure but makes calculations simple and easy to visualize.

#### How to Find Points on the curve

To find point $(x,y)$, we do the following:

For each $x \in \{0,1,2,\ldots,10\}$, compute $$y^2 \equiv x^3+3 \pmod {11}$$ Then we try to find $y$ such that $$y^2 \equiv \text{that value } \pmod {11}$$ This means we need to compute modular square roots.4

#### Modular Square Roots
A modular square root means solving: $$y^2 \equiv n \pmod {p}.$$ Example in mod 11:
- $4^2 = 16 \equiv 5 \pmod {11}$
- $7^2 = 49 \equiv 5 \pmod {11}$

So: $$y^2 \equiv 5 \pmod {11}$$ has two solutions: $$y = 4 \text{ and } y = 7$$ But some numbers have no solution:
- There is no $y$ such that $$y^2 \equiv 6 \pmod {11}$$

To compute this efficiently, we use the [Tonelli–Shanks algorithm](https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm), which either:
- gives the square roots, or
- tells us no solution exists

You can think of it as a “black box” square root solver for modular arithmetic.

#### Important Property (Two Roots)

If a solution exists, there are usually two values of $y$: $$y \text{ and } -y \pmod p$$ Example: $$4 + 7 \equiv 0 \pmod {11}$$ So $7$ is the "negative" of $4$ in mod 11.

#### Generating Points

To generate curve points:
- Loop over all $x$ values
- Compute $x^3+3 \pmod {11}$
- Check if a square root exists
- If yes $\rightarrow$ add all correspoding $(x,y)$ points

So the curve is simply: $$\text{all } (x,y)\text{ such that } y^2 = x^3 + 3 \pmod {11} $$

#### What the Plot Looks Like

|  |
|:--:|
| _{Figure 6: $y^2 = x^3 + 3 \pmod{11}$} |

When we plot the points:
- Only integer values from $0$ to $10$ appear
- The graph is **not continuous**, just discrete points
- The points appear **symmetric** (if $(x,y)$ exists, then $(x,−y)$ also exists)

There are two important things to notice:

First, no value of $x$ or $y$ is greater than or equal to the modulus. Everything stays within the finite field $$\{0,1,2,\ldots,p-1\}.$$

Second, even though the graph is made of scattered points, it still shows a kind of symmetry similar to curves over real numbers. This symmetry comes from the fact that if $y$ is a solution, then $−y$ is also a solution.

## Elliptic Curve Point Addition

Even in a finite field, elliptic curve point addition still works using the same idea as real curves: "connect and flip." The key difference is that everything is done modulo a prime $p$, so instead of smooth lines, we work with discrete points. If we take two points $P = (x_1, y_1)$ and $Q=(x_2, y_2)$, we compute the slope $$\lambda = \frac{y_2-y_1}{x_2-x_1} \pmod p, $$ and then compute the resulting point $$x_3 = \lambda^2 - x_1 - x_2 \pmod p, \quad y_3=\lambda(x_1-x_3)-y_1 \pmod p.$$ All operations use modular arithmetic, including division (which means multiplying by modular inverse). Even though square roots are used to check if a point is on the curve, they are **not used in addition**, which is why the group operation works cleanly in finite fields.

#### Doubling a Point

When we add a point to itself $P+P$, the slope changes to $$\lambda = \frac{3x_1^2 +a}{2y_1} \pmod p$$ This gives a new point using the same formulas. This is called **point doubling**, and it is a core operation in elliptic curve cryptography.


## Cyclic Group and Generator Point

All points on the curve form a group, and often this group is cyclic, meaning we can generate all points from a single point $G$ (called the generator). For example, for $$y^2 \equiv x^3 + 3 \pmod {11},$$ take $G = (4,10).$ Then: $$G,\, 2G,\, 3G,\, \ldots$$ generates all points. From the computation: $$ (4,10) \rightarrow (7,7)\rightarrow (1,9)\rightarrow (0,6) \rightarrow (8,8) \rightarrow (2,0) \rightarrow (8,3) \rightarrow (0,5) \rightarrow (1,2) \rightarrow (7,4) \rightarrow (4,1) \rightarrow (\text{None}, \text{None})\rightarrow (4,10)$$

Eventually, we reach the point at infinity (identity element), and then the cycle repeats: $$(12)G = G$$ As you can see from the generated points above, after $(\text{None}, \text{None})$ which represents the point at infinity (the identity element), we return to the starting point from which we began.

This is similar to modular arithmetic like: $$ (12 \text{ mod } 12) = 0 $$

#### Every Point Has a "Number"

Each point can be labeled by how many times we added $G$: $$1G = G,\, 2G, \,3G, \, \ldots$$ So every point corresponds to a number. This is why elliptic curves behave like numbers under addition, which is very useful in cryptography.

#### Point at Infinity (Identity Element)

The point at infinity acts like $0$ in addition: $$P + \mathcal{O} = P$$ If we add a point to its inverse, we get: $$ P + (-P) = \mathcal{O}$$

### Point Inverses and Symmetry

Points with the same $x$-coordinate are inverses: $$(x,y) \quad \text{and} \quad (x,-y \text{ mod } p)$$ Example: $$(4,10) \text{ and } (4,1)$$ Since: $$10 + 1 \equiv 0 \pmod {11},$$ they cancel out: $$(4,10) + (4,1) = \mathcal{O}$$ This is why the plot looks vertically symmetric.

### Order of the Curve vs Modulus
The modulus is $p=11$, but the total number of points (called the **order**) is: $$12$$ So:
- Modulus = 11
- Number of points = 12

These are not the same, and this is very important.

### When Order is Prime (Very Important Case)

For another curve: $$y^2 = x^3 + 7 \pmod {43},$$ the number of points is: $$31 \quad \text{(a prime number)}.$$ When the number of points (order) is prime:
- The group behaves like a **finite field**
- The group behaves like a finite field
- Every non-zero element has an inverse

|  |
|:--:|
| _{Figure 8: $y^2 = x^3 + 7 \pmod{43}$ creates a curve with 31 points total} |

### Connection to Finite Field Arithmetic

If an elliptic curve has **prime order** $n$ and a generator point $G$, then every point on the curve can be written as $$P=kG \quad \text{for some } k \in \{0,1,2,\ldots,n-1\}.$$This creates a direct correspondence between numbers modulo $n$ and elliptic curve points.

In particular, addition behaves consistently in both settings: $$a + b \pmod n \quad \leftrightarrow \quad aG+bG = (a+b)G.$$

This means that performing addition in the finite field corresponds exactly to adding points on the elliptic curve. This property is called a **homomorphism**, because the algebraic structure (addition) is preserved between the two systems.

## Scalar Multiplication = Repeated Addition
The plot you see looks random, but it comes from a very simple idea:
there is no real "multiplication" of elliptic curve points. When we write $$kG,$$ it actually means: $$kG = \underbrace{G + G + \cdots + G}_{k \text{ times}}$$ So, for example: $$5G = G+G+G+G+G$$ This is called **scalar multiplication**, but in reality, it is just repeated addition.

### Efficient Computation (Why It’s Fast)
Instead of adding $G$ again and again, we use a faster method called **doubling**: $$
G,\, 2G,\, 4G,\, 8G,\, 16G,\, \ldots$$ Example: $$ 135G = 128G+4G+2G+G.$$ So we break the number into powers of 2 and add those results. This makes computation very fast (logarithmic time instead of linear).

#### What the Plot Represents


The plot shows points: $$G,\,2G,\,3G,\,4G,\,\ldots,\,1000G.$$ Even though the points look random, they are actually generated in a **strict sequence** by repeatedly adding $G$.

#### Why It Looks Random
The numbers are extremely large (hundreds of bits), so:
- The pattern is **not visible to the human eye**
- Points appear scattered randomly
- But mathematically, everything is deterministic

This "random-looking" behavior is what makes elliptic curves useful in cryptography.

### Curve Order vs Field Modulus

In elliptic curves, there are two important numbers that are easy to confuse but play very different roles.

The **field modulus** $p$ defines the space in which the curve lives. It determines the possible values of the coordinates $x$ and $y$. For example, if we are working modulo $11$, then all points on the curve have coordinates in the set $$\{0,\,1,\,2,\,\ldots,\,10\}.$$ The **curve order** $n$, on the other hand, is the total number of points on the curve (including the point at infinity). This number controls how elliptic curve addition behaves.

To understand the difference clearly, consider the curve: $$y^2 \equiv x^3 + 3 \pmod {11}$$ Here, the field modulus is $p=11$, but the total number of points on the curve is $n=12$. Now take a generator point: $$G = (4,10)$$ If we keep adding this point to itself: $$G,\,2G,\,3G,\,\ldots$$ we eventually reach: $$12G = \mathcal{O},$$ where $\mathcal{O}$ is the point at infinity (the identity element). After this, the sequence repeats: $$13G = G$$ This shows the key property: $$xG = (x+n)G.$$ For example: $$1G = G, \quad 13G = (1+12)G = G$$ So elliptic curve addition “wraps around” using the curve order $n=12$.

Now let’s see what happens if we try to use the field modulus instead.
If we take: $$(1+p)G = (1+11)G = 12G,$$ we get: $$12G = \mathcal{O},$$ which is not equal to $G$. So: $$xG\ne(x+p)G.$$

The reason is simple:
- The field modulus $p$ controls the **coordinate system**
- The curve order $n$ controls the **group behavior (addition cycle)**

Whenever we compute scalar multiplication like: $$kG,$$ the value of $k$ effectively wraps around modulo $n$, not modulo $p$.

- $p$ tells you **where points live**
- $n$ tells you **when addition repeats**

#### Inverse and Identity
Every point has an inverse: $$P+(-P) = \mathcal{O}$$
- $\mathcal{O}$ = point at infinity (identity)
- Inverse means same $x$, opposite $y$

#### Associativity (Group Property)
Addition follows: $$(P+Q)+R = P+(Q+R).$$This ensures consistency when combining multiple points.

#### Division in Finite Field
In normal math, division like $5/2$ is tricky for integers.
But in finite fields, we use modular inverse: $$\frac{1}{2} \equiv 2^{-1} \pmod{n}.$$ So: $$\frac{5}{2} = 5 \cdot 2^{-1} \pmod {n}.$$ This allows us to represent fractions safely.

#### Generator Can Produce All Points

Starting from one generator $G$: $$G,\,2G,\,3G,\,\ldots,\,nG = \mathcal{O}$$ After $n$, it repeats again. So:
- All points come from one generator
- The group is **cyclic**

## Basic Zero-Knowledge Idea with Elliptic Curves
Let’s understand a very simple example of a zero-knowledge style proof using elliptic curves.

Suppose someone (the prover) claims: $$ x+ y = 15$$ but does not want to reveal the actual values of $x$ and $y$.

#### How the Proof Works
Instead of sending $x$ and $y$, the prover converts them into elliptic curve points using a generator $G$: $$A = xG, \quad B=yG$$ and sends: $$(A,B,15)$$ to the verifier.

#### What the Verifier Checks
The verifier computes: $$15G$$ and checks: $$A + B \stackrel{?}{=} 15G$$ If true, then: $$xG+yG = (x+y)G = 15G$$ So the verifier is convinced that: $$x+y =15$$ even though they **never saw $x$ or $y$**.

#### Why This Works
This works because of the property: $$aG + bG = (a+b)G$$This is the **homomorphic property** of elliptic curves.
So operations on numbers translate directly to operations on points.

#### Important Insight
- The prover hides values using:
$$x \rightarrow xG$$
- The verifier checks relationships using:
$$(x+y)G$$

So the verifier checks the structure, not the actual values.

#### Scalar Multiplication Reminder
When we write: $$xG$$ It means: $$xG = \underbrace{G + G + \cdots + G}_{x \text{ times}}$$ So multiplying by a number is just repeated addition.

#### Example Extension
You can also prove statements like: $$23x = 161$$by sending:$$X = xG$$and the verifier checks: $$23X \stackrel{?}{=} 161G$$Because:$$23(xG) = (23x)G = 161G$$

#### General Idea (More Variables)
For multiple variables: $$a_1x_1+a_2x_2+\dots+a_nx_n = c$$ You send: $$X_1=x_1G,\,X_2=x_2G,\,\ldots$$Verifier checks: $$a_1X_1+a_2X_2+\dots = cG$$So any **linear equation** can be verified this way.

#### Important Requirement
Both prover and verifier must agree on:
- The equation
- The generator $G$

Otherwise verification won’t work.

### Security Assumption
This works only because of the **discrete logarithm problem**:
Given: $$P=xG$$ it is **very hard** to find $x$.
So even if someone sees: $$A = xG$$ they cannot recover $x$.

#### Why Large Numbers Are Needed
If the numbers are small, an attacker can try all possibilities.

So we use very large primes (like BN128 curve), where:
- Field size $\approx$ $254$ bits
- Security $\approx$ $128$ bits

This makes brute force or advanced attacks infeasible.

### True Zero Knowledge
Our example $(A+B = 15G)$ is **not perfectly zero-knowledge**.

Why?
If an attacker guesses $x$ and $y$, they can check: $$xG \stackrel{?}{=} A, \quad yG \stackrel{?}{=} B$$ So the secret can still be guessed.

## Eliptic Curves Over Finite Fields as "Black Box"

You can think of elliptic curves like a tool you use without knowing all the internal details. Just like you use a hash function without understanding how it is built, you can use elliptic curve operations without knowing the full math behind them. What really matters is understanding the rules they follow, not how they are implemented internally.

### The Rules You Must Know (Cyclic Group Rules)

Elliptic curve points follow the rules of a **cyclic group**, and these rules are the most important thing to remember.

First, **closure** means if you add two points $P$ and $Q$, the result is always another valid point on the curve: $$P+Q = R.$$ Second, **associativity** means the order of grouping does not matter: $$(P+Q)+R = P+(Q+R).$$ Third, there is an **identity element** (called the point at infinity $\mathcal{O}$)such that: $$P+\mathcal{O} = P.$$ Fourth, every point has an **inverse**: $$P + (-P) = \mathcal{O}$$ As long as you follow these rules, you can safely perform operations like addition, scalar multiplication, and inversion without worrying about breaking anything.

#### What This Means in Practice
Because of these rules, elliptic curves behave very similarly to numbers in modular arithmetic. You can:
- Add points
- Multiply a point by a number (scalar multiplication)
- Find inverses

All of these operations are supported in libraries like ```py_ecc```, so in practice you just call functions instead of doing the math manually.

#### The Most Important Idea
The key idea to remember is:
> Elliptic curves over finite fields **preserve addition** from normal numbers.

Mathematically: $$a+b \pmod n \, \leftrightarrow \, aG+bG = (a+b)G.$$

This means elliptic curve points act like an “encoded version” of numbers, where addition still works the same way. This is why elliptic curves are useful in cryptography and zero-knowledge proofs.

Think of it like this:
- Numbers $\rightarrow$ hidden inside points
- Addition $\rightarrow$ still works exactly the same
- But you cannot easily recover the original numbers

So elliptic curves act like a **safe wrapper around numbers**.

### How Do We Know the Curve Order?

A natural question is: how do we know how many points are on the curve (the **curve order**)?

For small curves, we can count all points manually. But for real curves like BN128, the number of points is extremely large, so counting is impossible.

Instead, mathematicians use a special algorithm called [Schoof’s Algorithm](https://en.wikipedia.org/wiki/Schoof%27s_algorithm), which can compute the number of points efficiently (in polynomial time). You do not need to understand how this algorithm works - only that it exists and is reliable.

The detailed math behind algorithms like Schoof’s is quite advanced and not needed for practical use. In real-world systems:
- Curve parameters (like order) are already computed
- Libraries provide safe implementations
- You just need to use them correctly