06a-curves-over-reals.ipynb

Kernel: SageMath 10.5

Notebook 06a: Elliptic Curves over the Reals

Module 06. Elliptic Curves

---

Motivating Question. In Modules 01 and 05 we built cryptography on the multiplicative group $\mathbb{Z}/p\mathbb{Z}^*$. That group works, but it has a weakness: sub-exponential attacks (index calculus) mean we need 2048-bit primes for adequate security. Is there a different group where the discrete log is even harder, so we can use shorter keys? The answer is yes, elliptic curves provide groups where the best known attacks are fully exponential, enabling 256-bit keys with security comparable to 3072-bit RSA.

Before we can use these curves for crypto, we must first understand what they look like. This notebook starts with curves over the real numbers $\mathbb{R}$, where we can draw pictures and build geometric intuition.

---

Prerequisites. You should be comfortable with:

• Groups and group operations (Module 01)

• Fields, especially $\mathbb{R}$ and finite fields $\mathbb{F}_p$ (Module 02)

• The discrete logarithm problem in $\mathbb{Z}/p\mathbb{Z}^*$ (Module 05)

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

1. Write the short Weierstrass equation $y^2 = x^3 + ax + b$ and explain each component.

2. Compute and interpret the discriminant $\Delta = -16(4a^3 + 27b^2)$.

3. Plot elliptic curves over $\mathbb{R}$ and describe how $a$ and $b$ affect the shape.

4. Identify the point at infinity $\mathcal{O}$ and the $x$-axis symmetry.

5. Distinguish singular from non-singular curves.

1. The Weierstrass Equation

An elliptic curve over a field $K$ (for now, $K = \mathbb{R}$) is the set of points $(x, y)$ satisfying

$$E: \quad y^2 = x^3 + ax + b$$

together with a special "point at infinity" $\mathcal{O}$ that we will discuss shortly.

This is called the short Weierstrass form. The constants $a, b \in K$ determine the curve's shape.

Parameter	Role
$a$	Controls the "width" / curvature of the curve
$b$	Shifts the curve vertically (controls $y$-intercept)

Not every choice of $(a, b)$ gives a valid elliptic curve, we need the curve to be non-singular (no cusps or self-intersections). This is guaranteed by the discriminant condition.

# Our first elliptic curve: y^2 = x^3 - x + 1
a, b = -1, 1
print(f"Curve: y^2 = x^3 + ({a})x + ({b})")
print(f"This is a valid elliptic curve, let's see what it looks like.")

# SageMath's EllipticCurve over the reals
E = EllipticCurve(RR, [a, b])
print(f"\nSageMath representation: {E}")

# Plot it!
E.plot(xmin=-3, xmax=3)

Observations:

• The curve is symmetric about the $x$-axis (if $(x, y)$ is on the curve, so is $(x, -y)$, since $(-y)^2 = y^2$).

• It has a smooth, connected shape, no sharp corners or crossings.

• The right "arm" extends to infinity as $x \to \infty$.

Checkpoint 1. Why is the curve symmetric about the $x$-axis? Look at the equation $y^2 = x^3 + ax + b$, what happens when you replace $y$ with $-y$?

2. The Discriminant: Singular vs Non-Singular

For the curve $y^2 = x^3 + ax + b$ to define an elliptic curve, we require the discriminant

$$\Delta = -16(4a^3 + 27b^2) \neq 0.$$

When $\Delta = 0$, the cubic $x^3 + ax + b$ has a repeated root, and the curve develops a singularity, either a cusp (one repeated root of multiplicity 3) or a node (a double root). Singular curves do not form a group, so they are useless for cryptography.

Condition	Curve type	Group?
$\Delta \neq 0$	Non-singular (elliptic curve)	Yes
$\Delta = 0$, double root	Node (self-crossing)	No
$\Delta = 0$, triple root	Cusp (sharp point)	No

# Compute the discriminant for several curves
test_curves = [
    (-1, 1, "Non-singular"),
    (0, 0, "Cusp: y^2 = x^3"),
    (-3, 2, "Node: y^2 = x^3 - 3x + 2"),
    (-1, 0, "Non-singular"),
    (0, 1, "Non-singular"),
]

print("a b 4a^3+27b^2 Delta  Type")for a_val, b_val, label in test_curves:
    disc_inner = 4*a_val^3 + 27*b_val^2
    delta = -16 * disc_inner
    print(f"{a_val} {b_val} {disc_inner} {delta}  {label}")

# Visual comparison: non-singular vs singular curves
var('x y')

G1 = implicit_plot(y^2 - x^3 + x - 1, (x, -2.5, 2.5), (y, -4, 4), color='blue')
G1 += text('$y^2 = x^3 - x + 1$\n(Non-singular, $\\Delta \\neq 0$)', (0, -3.5), fontsize=10)

G2 = implicit_plot(y^2 - x^3, (x, -2.5, 2.5), (y, -4, 4), color='blue')
G2 += point([(0, 0)], color='red', size=80, zorder=5)
G2 += text('Cusp', (0.5, 0.5), fontsize=10, color='red')
G2 += text('$y^2 = x^3$\n(Cusp at origin, $\\Delta = 0$)', (0, -3.5), fontsize=10)

G3 = implicit_plot(y^2 - x^3 + 3*x - 2, (x, -2.5, 2.5), (y, -4, 4), color='blue')
G3 += point([(1, 0)], color='red', size=80, zorder=5)
G3 += text('Node', (1.5, 0.5), fontsize=10, color='red')
G3 += text('$y^2 = x^3 - 3x + 2$\n(Node, $\\Delta = 0$)', (0, -3.5), fontsize=10)

graphics_array([G1, G2, G3]).show(figsize=[15, 5])

Key observation: The cusp ($y^2 = x^3$) has a sharp point at the origin where the tangent is not well-defined. The node ($y^2 = x^3 - 3x + 2$) crosses itself at $(1, 0)$. Neither can be used for cryptography because the group law breaks down at the singular point.

Misconception alert. "Any cubic equation defines an elliptic curve." No! The curve must be non-singular ($\Delta \neq 0$). Also, the general cubic $y^2 + a_1 xy + a_3 y = x^3 + a_2 x^2 + a_4 x + a_6$ can always be transformed to short Weierstrass form over fields with characteristic $\neq 2, 3$.

3. Exploring Different Shapes

By varying $a$ and $b$, the curve can take on quite different shapes. Let us build a gallery.

# Gallery of elliptic curves with different (a, b)
var('x y')

curves = [
    (0, 1, "$y^2 = x^3 + 1$"),
    (0, -1, "$y^2 = x^3 - 1$"),
    (-1, 0, "$y^2 = x^3 - x$"),
    (-2, 1, "$y^2 = x^3 - 2x + 1$"),
    (1, 1, "$y^2 = x^3 + x + 1$"),
    (-4, 4, "$y^2 = x^3 - 4x + 4$"),
]

plots = []
for a_val, b_val, label in curves:
    G = implicit_plot(y^2 - x^3 - a_val*x - b_val, (x, -4, 4), (y, -6, 6),
                      color='blue', aspect_ratio=1)
    delta = -16*(4*a_val**3 + 27*b_val**2)
    G += text(label, (0, -5.5), fontsize=10)
    G += text(f'$\\Delta = {delta:.0f}$', (-3, 5), fontsize=9, color='brown')
    plots.append(G)

graphics_array([plots[:3], plots[3:]]).show(figsize=[15, 10])

Patterns to notice:

• When $a < 0$, the curve can have two components: a closed "egg" on the left and an unbounded piece on the right (e.g., $y^2 = x^3 - x$).

• When $a \geq 0$ or $b$ is large enough, the curve typically has one connected component.

• The curve always extends to the right ($x \to +\infty$) because $x^3$ dominates.

• All curves are symmetric about the $x$-axis.

Checkpoint 2. The curve $y^2 = x^3 - x$ has two components. The cubic $x^3 - x = x(x-1)(x+1)$ has three real roots at $x = -1, 0, 1$. Between which pairs of roots is $x^3 - x \geq 0$ (needed for real $y$)?

4. The Point at Infinity $\mathcal{O}$

Every elliptic curve has a special point $\mathcal{O}$ called the point at infinity. You cannot see it on our plots, it lives "at the top and bottom of the plane simultaneously," in the projective closure of the curve.

Formally, we work in projective coordinates $[X : Y : Z]$ where the affine point $(x, y)$ corresponds to $[x : y : 1]$, and the point at infinity is $\mathcal{O} = [0 : 1 : 0]$.

Why do we need $\mathcal{O}$? It serves as the identity element of the group:

$$P + \mathcal{O} = \mathcal{O} + P = P \quad \text{for all points } P.$$

Without $\mathcal{O}$, the set of curve points would not have an identity and could not form a group.

Analogy	Identity element
$(\mathbb{Z}, +)$	0
$(\mathbb{Z}/p\mathbb{Z}^*, \times)$	1
$(E, +)$	$\mathcal{O}$ (point at infinity)

# SageMath represents the point at infinity as (0 : 1 : 0)
E = EllipticCurve(QQ, [-1, 1])  # Over the rationals for exact arithmetic
O = E(0)  # The point at infinity
print(f"Point at infinity: {O}")
print(f"Is it on the curve? {O in E}")

# Pick a point on the curve
P = E(1, 1)
print(f"\nP = {P}")
print(f"P + O = {P + O}")
print(f"O + P = {O + P}")
print(f"P + O == P? {P + O == P}")

5. Points and the $x$-Axis Symmetry

For any point $P = (x_0, y_0)$ on the curve, the point $(x_0, -y_0)$ is also on the curve (since $(-y_0)^2 = y_0^2$). This "mirror" point is the inverse of $P$ in the group:

$$-P = (x_0, -y_0), \qquad P + (-P) = \mathcal{O}.$$

Geometrically: the line through $P$ and $-P$ is vertical, and it "meets the curve at infinity", which is $\mathcal{O}$.

# Demonstrating point negation
E = EllipticCurve(QQ, [-1, 1])
P = E(1, 1)
neg_P = -P

print(f"P     = {P}")
print(f"-P    = {neg_P}")
print(f"P + (-P) = {P + neg_P}")
print(f"\nNotice: P = (1, 1) and -P = (1, -1), same x, opposite y.")

# Visualise point and its inverse
var('x y')
a_val, b_val = -1, 1

G = implicit_plot(y^2 - x^3 - a_val*x - b_val, (x, -1.5, 2.5), (y, -2.5, 2.5),
                  color='blue', aspect_ratio=1)

# Mark P and -P
px, py = 1, 1
G += point([(px, py)], color='red', size=80, zorder=5)
G += text('$P = (1, 1)$', (px + 0.3, py + 0.2), fontsize=12, color='red')
G += point([(px, -py)], color='green', size=80, zorder=5)
G += text('$-P = (1, -1)$', (px + 0.3, -py - 0.2), fontsize=12, color='green')

# Vertical line through P and -P
G += line([(px, -2.5), (px, 2.5)], color='black', linestyle='--', alpha=0.5)
G += text('vertical line\n(meets at $\\mathcal{O}$)', (px + 0.6, 2.0), fontsize=10, color='gray')

G.show(figsize=7,
       title='$y^2 = x^3 - x + 1$: Point $P$ and its inverse $-P$',
       gridlines=True)

Checkpoint 3. If a point $P = (x_0, 0)$ lies on the curve (i.e., $y_0 = 0$), what is $-P$? What does this tell you about such points in the group?

6. Finding Rational Points

Over $\mathbb{R}$, there are infinitely many points on any elliptic curve. But finding points with rational coordinates (both $x$ and $y$ in $\mathbb{Q}$) is a deep number-theoretic problem. Let us find some by hand and with SageMath.

# Find some rational points on y^2 = x^3 - x + 1
E = EllipticCurve(QQ, [-1, 1])

# Try integer x-values and check if y^2 is a perfect square
print("Searching for rational points with integer x in [-5, 5]:")
print("x x^3-x+1 y^2 perfect square? y")for x_val in range(-5, 6):
    rhs = x_val^3 - x_val + 1
    if rhs >= 0:
        y_sq = rhs
        y_val = sqrt(RR(y_sq))
        is_square = (int(y_val))^2 == y_sq
        y_str = str(int(y_val)) if is_square else f"√{y_sq} ≈ {y_val:.3f}"
        marker = " ✓" if is_square else ""
        print(f"{x_val} {rhs} {'Yes' if is_square else 'No'} {y_str}{marker}")

# SageMath can find rational points systematically
E = EllipticCurve(QQ, [-1, 1])

# The rank tells us about the "size" of the rational point group
print(f"Curve: {E}")
print(f"Rank: {E.rank()}")

# Generators of the Mordell-Weil group (rational points mod torsion)
gens = E.gens()
print(f"Generators: {gens}")

# Torsion subgroup
torsion = E.torsion_subgroup()
print(f"Torsion subgroup: {torsion}")
print(f"Torsion points: {torsion.gens()}")

---

Bridge from Module 05. In Module 05, our group elements were numbers in $\{1, 2, \ldots, p-1\}$ and the operation was multiplication mod $p$. On an elliptic curve, our group elements are points $(x, y)$ and the operation is a geometric "addition" rule (coming in notebook 06b). Different objects, same abstract structure: a finite cyclic group where the DLP is hard.

---

7. Why Curves, Not Lines or Conics?

You might wonder: why specifically cubic curves? Why not lines ($y = mx + b$) or conics ($x^2 + y^2 = 1$)?

• Lines have no interesting structure, a line meets another line in at most one point.

• Conics (degree 2) can be parameterised rationally, meaning you can write down all rational points with a formula. This makes the "discrete log" problem trivial.

• Cubics (degree 3) are the sweet spot: they have enough structure to define a group law (two points determine a third), but they cannot be rationally parameterised, which is what makes the DLP hard.

This is sometimes called the genus argument: elliptic curves have genus 1, which is exactly what gives them a group structure and computational hardness.

# A line meets a cubic in up to 3 points (Bezout's theorem)
# This is the geometric foundation for the group law
var('x y')
a_val, b_val = -1, 1

G = implicit_plot(y^2 - x^3 - a_val*x - b_val, (x, -1.5, 2.5), (y, -2.5, 2.5),
                  color='blue', legend_label='$y^2 = x^3 - x + 1$', aspect_ratio=1)

# Draw a secant line that hits the curve in 3 points
# Line: y = 0.5x + 0.5
G += plot(0.5*x + 0.5, (x, -1.5, 2.5), color='red', linestyle='--',
          legend_label='$y = 0.5x + 0.5$')

# Find intersections numerically: y^2 = x^3 - x + 1, y = 0.5x + 0.5
# => (0.5x+0.5)^2 = x^3 - x + 1
# => x^3 - 0.25x^2 - 1.5x + 0.75 = 0
poly_ring.<t> = PolynomialRing(RR)
cubic = t^3 - 0.25*t^2 - 1.5*t + 0.75
real_roots = [r for r, _ in cubic.roots()]

for xr in sorted(real_roots):
    yr = 0.5 * xr + 0.5
    G += point([(float(xr), float(yr))], color='red', size=80, zorder=5)
    G += text(f'({float(xr):.2f}, {float(yr):.2f})', (float(xr) + 0.25, float(yr) + 0.2),
              fontsize=10)

G.show(figsize=8,
       title='A line meets an elliptic curve in (up to) 3 points',
       gridlines=True)

print(f"Intersection x-coordinates: {sorted([f'{float(r):.4f}' for r in real_roots])}")
print("A generic line meets a cubic in exactly 3 points (by Bezout's theorem).")

This "three-point" property is the key to defining the group law in the next notebook. Given two points $P$ and $Q$ on the curve, we draw a line through them, find the third intersection point $R$, and then reflect $R$ across the $x$-axis to get $P + Q$.

Crypto foreshadowing. The group law on elliptic curves enables the same cryptographic constructions as $\mathbb{Z}/p\mathbb{Z}^*$, Diffie-Hellman, ElGamal, digital signatures, but with much shorter keys. A 256-bit elliptic curve key provides roughly the same security as a 3072-bit RSA key. That is a factor of 12× savings in key size, which matters for constrained devices, bandwidth, and storage.

8. Exercises

Exercise 1 (Worked): Checking the Discriminant

Problem. Determine which of the following define valid elliptic curves:

• (a) $y^2 = x^3 + 2x + 3$

• (b) $y^2 = x^3 - 3x + 2$

• (c) $y^2 = x^3 + x + 1$

Solution. Compute $\Delta = -16(4a^3 + 27b^2)$ for each:

Curve	$a$	$b$	$4a^3 + 27b^2$	$\Delta$	Valid?
(a)	2	3	$4(8) + 27(9) = 275$	$-4400$	Yes ($\Delta \neq 0$)
(b)	-3	2	$4(-27) + 27(4) = 0$	$0$	No (singular!)
(c)	1	1	$4(1) + 27(1) = 31$	$-496$	Yes ($\Delta \neq 0$)

Curve (b) is singular because $x^3 - 3x + 2 = (x-1)^2(x+2)$ has a double root at $x = 1$.

# Exercise 1: verification
for a_val, b_val, label in [(2, 3, 'a'), (-3, 2, 'b'), (1, 1, 'c')]:
    disc = -16 * (4*a_val^3 + 27*b_val^2)
    status = 'VALID' if disc != 0 else 'SINGULAR'
    print(f"({label}) a={a_val}, b={b_val}: Δ = {disc} → {status}")
    if disc != 0:
        E = EllipticCurve(QQ, [a_val, b_val])
        print(f"     SageMath confirms: {E}")

Exercise 2 (Guided): Curve Shape Classification

Problem. For the curve $y^2 = x^3 + ax$ (with $b = 0$), determine:

1. For which values of $a$ is the curve non-singular?

2. For $a = -1$ and $a = 1$, how many connected components does the real curve have?

3. Plot both curves to confirm.

Hint: With $b = 0$, the discriminant simplifies to $\Delta = -16 \cdot 4a^3 = -64a^3$. When is this zero?

# Exercise 2: fill in the TODOs

# TODO 1: Compute the discriminant for b=0. For which a is Δ = 0?
# delta = -64 * a^3
# This is zero when a = ???

# TODO 2: For a = -1, factor x^3 - x to find the real roots.
# The cubic x^3 - x = x(x^2 - 1) = x(x-1)(x+1)
# Roots at: ???
# The cubic is >= 0 on which intervals? → How many components?

# TODO 3: Plot both curves side by side using implicit_plot
# var('x y')
# G1 = implicit_plot(y^2 - x^3 + x, (x, -3, 3), (y, -3, 3), color='blue')
# G2 = implicit_plot(y^2 - x^3 - x, (x, -3, 3), (y, -3, 3), color='blue')
# graphics_array([G1, G2]).show(figsize=[12, 5])

Exercise 3 (Independent): Point Negation

Problem.

1. On the curve $E: y^2 = x^3 + 1$ over $\mathbb{Q}$, find the point $P = (0, 1)$ and its inverse $-P$. Verify that $P + (-P) = \mathcal{O}$ using SageMath.

2. Find all points of the form $(x, 0)$ on this curve (i.e., points where $y = 0$). What is special about these points?

3. The point $(-1, 0)$ is on the curve. What is its order in the group? (Hint: compute $2 \cdot (-1, 0)$.)

# Exercise 3: write your solution here

Summary

Concept	Key Fact
Weierstrass form	$y^2 = x^3 + ax + b$ with $a, b$ from a field $K$
Discriminant	$\Delta = -16(4a^3 + 27b^2) \neq 0$ ensures non-singularity
Point at infinity	$\mathcal{O} = [0:1:0]$ is the identity element of the group
Symmetry	If $(x, y) \in E$, then $(x, -y) \in E$; negation is reflection
Three-point property	A line meets a cubic in (generically) 3 points, the basis for the group law

We now know what elliptic curves look like over $\mathbb{R}$. In the next notebook, we will define the group law: how to "add" two points on the curve using the chord-and-tangent construction.

---

Next: 06b: Point Addition: The Geometry