06c-curves-over-finite-fields.ipynb

Kernel: SageMath 10.5

Notebook 06c: Curves over Finite Fields

Module 06. Elliptic Curves

---

Motivating Question. In Notebooks 06a and 06b, we drew smooth curves over $\mathbb{R}$ and defined the group law geometrically. But real-number arithmetic has rounding errors and infinite precision issues, useless for cryptography. What happens when we move to a finite field $\mathbb{F}_p$? The curve becomes a finite set of discrete points, the addition formulas work exactly (no rounding!), and we get a finite group ready for cryptographic use.

---

Prerequisites. You should be comfortable with:

• Finite fields $\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}$ and arithmetic modulo $p$ (Modules 01--02)

• Elliptic curves and the Weierstrass equation (Notebook 06a)

• The point addition and doubling formulas (Notebook 06b)

Learning objectives. By the end of this notebook you will be able to:

1. Define an elliptic curve over $\mathbb{F}_p$ and list all its points.

2. Verify that the same addition formulas from 06b work over finite fields.

3. Visualise the discrete point set and compare it to the real curve.

4. Understand why finite fields are essential for cryptography.

5. Compute with SageMath's EllipticCurve(GF(p), [a, b]).

1. From $\mathbb{R}$ to $\mathbb{F}_p$

An elliptic curve over $\mathbb{F}_p$ uses the same equation:

$$E(\mathbb{F}_p): \quad y^2 \equiv x^3 + ax + b \pmod{p}$$

The only difference: all arithmetic is modulo $p$. The discriminant condition $\Delta = -16(4a^3 + 27b^2) \not\equiv 0 \pmod{p}$ still must hold.

Since $x \in \{0, 1, \ldots, p-1\}$ and $y \in \{0, 1, \ldots, p-1\}$, there are at most $p^2$ candidate points. The actual number is determined by how many $x$-values yield a quadratic residue.

Over $\mathbb{R}$	Over $\mathbb{F}_p$
Infinitely many points	Finitely many points
Smooth curve	Discrete point set
Floating-point issues	Exact arithmetic
Geometric intuition	Algebraic computation
Not useful for crypto	The setting for all EC crypto

# Our first curve over a finite field
p = 23
F = GF(p)
E = EllipticCurve(F, [1, 1])  # y^2 = x^3 + x + 1 over F_23

print(f"Curve: {E}")
print(f"Base field: F_{p}")
print(f"Discriminant (mod {p}): {E.discriminant()}")
print(f"Number of points (including O): {E.cardinality()}")

2. Finding Points by Brute Force

To find all points on $E(\mathbb{F}_p)$, we can check each $x \in \{0, 1, \ldots, p-1\}$:

1. Compute $r = x^3 + ax + b \pmod{p}$.

2. Check if $r$ is a quadratic residue mod $p$ (i.e., does $y^2 \equiv r$ have a solution?).

3. If yes, find $y$ and add the points $(x, y)$ and $(x, -y \bmod p)$ to the list.

# Find all points on E(F_23): y^2 = x^3 + x + 1
p = 23
a, b = 1, 1

points = []  # will collect (x, y) tuples

print("x x^3+x+1 QR? y values")
for x in range(p):
    rhs = (x^3 + a*x + b) % p
    # Check if rhs is a quadratic residue using Euler's criterion
    if rhs == 0:
        points.append((x, 0))
        print(f"{x} {rhs} Yes {str(0)}")
    elif power_mod(rhs, (p-1)//2, p) == 1:  # Euler's criterion
        # Find square root (SageMath)
        y = int(Mod(rhs, p).sqrt())
        y2 = p - y
        points.append((x, y))
        points.append((x, y2))
        print(f"{x} {rhs} Yes {f'{y}, {y2}':>15}")
    else:
        print(f"{x} {rhs} No -")

print(f"\nFound {len(points)} affine points + 1 point at infinity = {len(points) + 1} total")

# Verify against SageMath's built-in enumeration
E = EllipticCurve(GF(23), [1, 1])
sage_points = E.points()

print(f"SageMath finds {len(sage_points)} points:")
for pt in sage_points:
    print(f"  {pt}")

print(f"\nOur brute force: {len(points)} affine points + O = {len(points) + 1} total")
print(f"Counts match? {len(points) + 1 == len(sage_points)}")

Checkpoint 1. For a given $x$, the value $r = x^3 + ax + b \bmod p$ is either a quadratic residue (giving 2 points), zero (giving 1 point with $y = 0$), or a non-residue (giving 0 points). On average, about half the $x$-values yield points. This is why $|E(\mathbb{F}_p)| \approx p$, we will make this precise with Hasse's theorem in Notebook 06d.

3. Visualising the Point Set

Over $\mathbb{R}$, the curve is a smooth line. Over $\mathbb{F}_p$, it becomes a scatter plot of discrete points. The $x$-axis symmetry is preserved: if $(x, y)$ is on the curve, so is $(x, p - y)$.

var('x y')

# Side-by-side: real curve vs finite field

# Left: Real curve
G1 = implicit_plot(y^2 - x^3 - x - 1, (x, -2, 4), (y, -6, 6),
                   color='blue', aspect_ratio=1)
G1 += text('$y^2 = x^3 + x + 1$ over $\\mathbb{R}$', (1, -5.5), fontsize=11)

# Right: Finite field
p = 23
E = EllipticCurve(GF(p), [1, 1])
pts = [(int(pt[0]), int(pt[1])) for pt in E.points() if pt != E(0)]
G2 = point(pts, size=40, color='red', zorder=5)
# Draw symmetry line y = p/2
G2 += line([(-1, p/2), (p, p/2)], color='gray', linestyle='--', alpha=0.3)
G2 += text(f'y = {p}/2 (symmetry)', (p/2, p/2 + 1), fontsize=9, color='gray')
G2 += text(f'$y^2 \\equiv x^3 + x + 1 \\pmod{{{p}}}$\n({len(E.points())} points)',
           (p/2, -2), fontsize=11)

graphics_array([G1, G2]).show(figsize=[14, 6])

Observations:

• Over $\mathbb{R}$: a smooth, continuous curve.

• Over $\mathbb{F}_{23}$: a scattered cloud of points with no visible geometric pattern.

• The symmetry is about the line $y = p/2$ instead of $y = 0$, because $-y \equiv p - y \pmod{p}$.

• The "randomness" of the point distribution is what makes the ECDLP hard.

Misconception alert. "The points over $\mathbb{F}_p$ lie on the real curve." No, they live in $\mathbb{F}_p \times \mathbb{F}_p$, a completely different space. The real curve gives geometric intuition for the group law, but over $\mathbb{F}_p$ there is no continuous geometry at all.

# Same curve, different primes: see how the point set grows
plots = []
for p in [23, 67, 127]:
    E = EllipticCurve(GF(p), [1, 1])
    pts = [(int(pt[0]), int(pt[1])) for pt in E.points() if pt != E(0)]
    sz = max(5, 50 - p//3)
    G = point(pts, size=sz, color='red', alpha=0.7)
    G += text(f'$E(\\mathbb{{F}}_{{{p}}})$: {len(E.points())} points',
              (p/2, -p//8), fontsize=11)
    plots.append(G)

graphics_array(plots).show(figsize=[16, 5])

4. Point Arithmetic over $\mathbb{F}_p$

The beautiful thing: the same addition formulas from Notebook 06b work over $\mathbb{F}_p$. Division by $d$ becomes multiplication by $d^{-1} \bmod p$, which always exists since $p$ is prime.

Operation over $\mathbb{R}$	Operation over $\mathbb{F}_p$
$\lambda = \frac{y_2 - y_1}{x_2 - x_1}$	$\lambda = (y_2 - y_1) \cdot (x_2 - x_1)^{-1} \bmod p$
$x_3 = \lambda^2 - x_1 - x_2$	$x_3 \equiv \lambda^2 - x_1 - x_2 \pmod{p}$
$y_3 = \lambda(x_1 - x_3) - y_1$	$y_3 \equiv \lambda(x_1 - x_3) - y_1 \pmod{p}$

# Implement point addition over F_p from scratch
def ec_add_fp(p, a, b, P, Q):
    """
    Add points P and Q on y^2 = x^3 + ax + b over F_p.
    Points are (x, y) tuples or None for the identity O.
    """
    if P is None:  # O + Q = Q
        return Q
    if Q is None:  # P + O = P
        return P
    
    x1, y1 = P
    x2, y2 = Q
    
    if x1 == x2 and y1 == (p - y2) % p:  # P + (-P) = O
        return None
    
    if P == Q:  # Doubling
        lam = (3 * x1^2 + a) * pow(2 * y1, -1, p) % p
    else:       # Addition
        lam = (y2 - y1) * pow(x2 - x1, -1, p) % p
    
    x3 = (lam^2 - x1 - x2) % p
    y3 = (lam * (x1 - x3) - y1) % p
    return (x3, y3)

# Test: compare our implementation with SageMath
p = 23
a_coeff, b_coeff = 1, 1
E = EllipticCurve(GF(p), [a_coeff, b_coeff])

P_sage = E(0, 1)
Q_sage = E(6, 4)

# Our implementation
P_tuple = (0, 1)
Q_tuple = (6, 4)
R_manual = ec_add_fp(p, a_coeff, b_coeff, P_tuple, Q_tuple)

# SageMath
R_sage = P_sage + Q_sage

print(f"P = {P_tuple}")
print(f"Q = {Q_tuple}")
print(f"P + Q (manual):   {R_manual}")
print(f"P + Q (SageMath): ({int(R_sage[0])}, {int(R_sage[1])})")
print(f"Match? {R_manual == (int(R_sage[0]), int(R_sage[1]))}")

# Step-by-step addition with all arithmetic shown
p = 23
a_coeff = 1
P = (0, 1)
Q = (6, 4)
x1, y1 = P
x2, y2 = Q

print(f"Adding P = {P} and Q = {Q} on y^2 = x^3 + x + 1 over F_{p}")
print()

# Step 1: slope
num = (y2 - y1) % p
den = (x2 - x1) % p
den_inv = pow(den, -1, p)
lam = (num * den_inv) % p
print(f"Step 1: λ = (y₂ - y₁) · (x₂ - x₁)⁻¹ mod {p}")
print(f"  numerator:   {y2} - {y1} ≡ {num} (mod {p})")
print(f"  denominator: {x2} - {x1} ≡ {den} (mod {p})")
print(f"  inverse:     {den}⁻¹ ≡ {den_inv} (mod {p})  [check: {den}·{den_inv} ≡ {(den*den_inv) % p} (mod {p})]")
print(f"  λ = {num} · {den_inv} ≡ {lam} (mod {p})")
print()

# Step 2: x3
x3 = (lam^2 - x1 - x2) % p
print(f"Step 2: x₃ = λ² - x₁ - x₂ mod {p}")
print(f"  x₃ = {lam}² - {x1} - {x2} = {lam^2} - {x1 + x2} ≡ {x3} (mod {p})")
print()

# Step 3: y3
y3 = (lam * (x1 - x3) - y1) % p
print(f"Step 3: y₃ = λ(x₁ - x₃) - y₁ mod {p}")
print(f"  y₃ = {lam}·({x1} - {x3}) - {y1} ≡ {y3} (mod {p})")
print()
print(f"Result: P + Q = ({x3}, {y3})")

# Verify
print(f"\nVerify ({x3}, {y3}) is on the curve: {y3}² ≡ {y3^2 % p}, {x3}³+{x3}+1 ≡ {(x3^3 + x3 + 1) % p} (mod {p})")

Checkpoint 2. In the computation above, the modular inverse $(x_2 - x_1)^{-1} \bmod p$ is computed using Fermat's little theorem: $d^{-1} \equiv d^{p-2} \pmod{p}$. Why does this work? (Hint: $d^{p-1} \equiv 1$ for $d \not\equiv 0$.)

5. Multiples of a Generator

Just as in Module 05, we can take a point $G$ and compute $G, 2G, 3G, \ldots$ until we cycle back to $\mathcal{O}$. If $G$ generates the entire group, then $\langle G \rangle = E(\mathbb{F}_p)$.

---

Bridge from Module 05. In Module 05, a generator $g$ of $\mathbb{Z}/p\mathbb{Z}^*$ was called a primitive root: every element was a power of $g$. Here, a generator $G$ of $E(\mathbb{F}_p)$ is a point whose multiples cover the entire group: every point is $kG$ for some $k$.

# Find a generator and trace all multiples
p = 23
E = EllipticCurve(GF(p), [1, 1])
n = E.cardinality()
print(f"|E(F_{p})| = {n}")

# Find a generator (a point of order n)
G = None
for pt in E.points():
    if pt.order() == n:
        G = pt
        break

print(f"Generator: G = {G}")
print(f"Order of G: {G.order()}")
print(f"\nMultiples of G:")
print("k  kG")for k in range(1, n + 1):
    kG = k * G
    if kG == E(0):
        print(f"{k}  O  ← back to identity!")
    else:
        print(f"{k}  ({int(kG[0])}, {int(kG[1])})")

# Visualise: trace multiples of G as a "random walk" on the point set
n = E.cardinality()  # E from cell above (GF(23))
p = 23
E = EllipticCurve(GF(p), [1, 1])
n = E.cardinality()

# Find a generator (a point of order n)
G_pt = None
for pt in E.points():
    if pt.order() == n:
        G_pt = pt
        break

xs, ys, ks = [], [], []
for k in range(1, n):
    kG = k * G_pt
    xs.append(int(kG[0]))
    ys.append(int(kG[1]))
    ks.append(k)

# Left: all multiples coloured by k
from sage.plot.colors import rainbow
colors_list = rainbow(len(xs))
G1 = Graphics()
for i in range(len(xs)):
    G1 += point([(xs[i], ys[i])], color=colors_list[i], size=60, zorder=5)
G1 += text(f'Multiples of $G$ on $E(\\mathbb{{F}}_{{{p}}})$', (p/2, -2), fontsize=11)

# Right: connect consecutive multiples to see the "path"
G2 = point(list(zip(xs, ys)), color='lightgray', size=30, zorder=3)
for i in range(len(xs) - 1):
    G2 += arrow((xs[i], ys[i]), (xs[i+1], ys[i+1]), color='blue', alpha=0.3, width=0.5)

# Highlight first 5 multiples
highlight_colors = ['red', 'green', 'blue', 'purple', 'orange']
for k in range(1, 6):
    G2 += point([(xs[k-1], ys[k-1])], color=highlight_colors[k-1], size=80, zorder=6)
    G2 += text(f'{k}G', (xs[k-1] + 1, ys[k-1] + 1), fontsize=9,
               fontweight='bold', color=highlight_colors[k-1])

G2 += text('"Path" through consecutive multiples', (p/2, -2), fontsize=11)

graphics_array([G1, G2]).show(figsize=[14, 6])

print(f"The multiples of G visit all {n-1} affine points, G generates the entire group.")

Look at the right plot: the arrows connecting consecutive multiples jump erratically around the grid. There is no spatial pattern that would help you predict $kG$ from $(k-1)G$ without doing the computation. This "scramble" is exactly what makes the ECDLP hard.

Checkpoint 3. If someone gives you a point $Q$ on the curve and tells you $Q = kG$ for some secret $k$, how would you find $k$? Over this small curve, you could try all $k$ (brute force). For a 256-bit curve with $\approx 2^{256}$ points, that is impossible.

6. Comparing Curve Sizes

How does the number of points $|E(\mathbb{F}_p)|$ relate to $p$? Roughly, $|E| \approx p + 1$. The exact count varies with the curve parameters.

# Count points for several primes
primes = [p for p in prime_range(10, 200)]
counts = []

print("p |E(F_p)| p+1 difference")for p in primes[:15]:
    if (4*1^3 + 27*1^2) % p != 0:  # valid curve
        E = EllipticCurve(GF(p), [1, 1])
        n = E.cardinality()
        diff = n - (p + 1)
        counts.append((p, n))
        print(f"{p} {n} {p+1} {diff}")

print(f"\nNotice: |E| ≈ p+1, with small fluctuations.")
print(f"Hasse's theorem (next notebook) says |difference| ≤ 2√p.")

# Visualise: |E(F_p)| vs p for many primes
primes_list = prime_range(10, 500)
sizes = []
for p in primes_list:
    if (4 + 27) % p != 0:
        E = EllipticCurve(GF(p), [1, 1])
        sizes.append((int(p), int(E.cardinality())))

ps = [s[0] for s in sizes]
ns = [s[1] for s in sizes]

G = point(list(zip(ps, ns)), size=15, color='blue', alpha=0.6,
          legend_label='$|E(\\mathbb{F}_p)|$')
G += plot(x + 1, (x, 10, 500), color='red', legend_label='$p + 1$')

# Hasse bounds as filled region
upper = [(p, p + 1 + 2*sqrt(float(p))) for p in ps]
lower = [(p, p + 1 - 2*sqrt(float(p))) for p in ps]
# Draw the boundary lines
G += list_plot(upper, plotjoined=True, color='red', alpha=0.3, linestyle='--')
G += list_plot(lower, plotjoined=True, color='red', alpha=0.3, linestyle='--',
               legend_label='Hasse bound: $p+1 \\pm 2\\sqrt{p}$')

G.show(figsize=[10, 5],
       axes_labels=['Prime $p$', 'Number of points'],
       title="$|E(\\mathbb{F}_p)|$ stays close to $p + 1$ (Hasse's theorem)",
       gridlines=True)

Crypto foreshadowing. For a 256-bit prime $p$, we get $|E(\mathbb{F}_p)| \approx 2^{256}$ points. This gives us a group large enough for 128-bit security against Pollard's rho attack ($O(\sqrt{n}) \approx 2^{128}$ operations). By contrast, achieving 128-bit security in $\mathbb{Z}/p\mathbb{Z}^*$ requires a 3072-bit prime (due to sub-exponential index calculus).

7. Exercises

Exercise 1 (Worked): Point Addition over $\mathbb{F}_{29}$

Problem. On $E: y^2 = x^3 + 4x + 20$ over $\mathbb{F}_{29}$, compute $P + Q$ where $P = (2, 6)$ and $Q = (5, 22)$.

Solution.

Step 1: Slope. $$\lambda = (22 - 6) \cdot (5 - 2)^{-1} \equiv 16 \cdot 3^{-1} \pmod{29}$$ $3^{-1} \equiv 10 \pmod{29}$ (since $3 \cdot 10 = 30 \equiv 1$), so $\lambda \equiv 16 \cdot 10 = 160 \equiv 160 - 5 \cdot 29 = 160 - 145 = 15 \pmod{29}$.

Step 2: $x_3 = 15^2 - 2 - 5 = 225 - 7 = 218 \equiv 218 - 7 \cdot 29 = 218 - 203 = 15 \pmod{29}$.

Step 3: $y_3 = 15 \cdot (2 - 15) - 6 = 15 \cdot (-13) - 6 = -195 - 6 = -201 \equiv -201 + 7 \cdot 29 = 2 \pmod{29}$.

So $P + Q = (15, 2)$.

# Exercise 1: verification
E = EllipticCurve(GF(29), [4, 20])
P = E(2, 6)
Q = E(5, 22)
R = P + Q
print(f"P + Q = {R}")
print(f"Expected: (15, 2)")
print(f"Match? {R == E(15, 2)}")

Exercise 2 (Guided): Enumerate and Verify

Problem. On $E: y^2 = x^3 + 2x + 3$ over $\mathbb{F}_{17}$:

1. Use brute force to find all points.

2. Verify that $|E(\mathbb{F}_{17})|$ satisfies Hasse's bound: $|E| - 18| \leq 2\sqrt{17} \approx 8.25$.

3. Find a generator (a point whose order equals $|E|$).

Hint: For each $x$, compute $x^3 + 2x + 3 \bmod 17$ and check if it is a quadratic residue.

# Exercise 2: fill in the TODOs
p = 17
a, b = 2, 3

# TODO 1: Find all points by brute force
# points = []
# for x in range(p):
#     rhs = ???
#     ...

# TODO 2: Check Hasse's bound
# n = len(points) + 1  # +1 for O
# print(f"|E| = {n}, p+1 = {p+1}, |difference| = {abs(n - (p+1))}")
# print(f"2*sqrt(p) = {2*sqrt(float(p)):.2f}")
# print(f"Hasse satisfied? {abs(n - (p+1)) <= 2*sqrt(float(p))}")

# TODO 3: Find a generator using SageMath
# E = EllipticCurve(GF(p), [a, b])
# for pt in E.points():
#     if pt.order() == E.cardinality():
#         print(f"Generator: {pt}")
#         break

Exercise 3 (Independent): The ECDLP in a Small Group

Problem.

1. On $E: y^2 = x^3 + x + 1$ over $\mathbb{F}_{23}$, let $G$ be a generator. Compute $Q = 17 \cdot G$ using SageMath.

2. Now pretend you only know $G$ and $Q$ (not the scalar 17). Write a brute-force loop to recover $k$ from $Q = kG$ by trying $k = 1, 2, 3, \ldots$.

3. For a 256-bit curve, $|E| \approx 2^{256}$. If your computer can test $10^9$ values of $k$ per second, how long would brute force take? (Express in years.)

# Exercise 3: write your solution here

Summary

Concept	Key Fact
EC over $\mathbb{F}_p$	Same equation $y^2 = x^3 + ax + b$, all arithmetic mod $p$
Finite point set	At most $2p + 1$ points; approximately $p + 1$ (Hasse)
Same formulas	Addition and doubling formulas from 06b apply directly
Division → inverse	$\frac{a}{b}$ becomes $a \cdot b^{-1} \bmod p$
Discrete scramble	Multiples of $G$ scatter unpredictably, the ECDLP is hard
Crypto readiness	A 256-bit prime gives $\sim 2^{256}$ group elements with 128-bit security

Now that we can compute with curves over finite fields, the next notebook studies the group structure in more depth: How many points are there exactly? What does the group look like? (Cyclic? Product of cyclic groups?) These questions are answered by Hasse's theorem and the structure theorem for abelian groups.

---

Next: 06d: Group Structure and Order