Problem 38 - An Introduction to Mathematical Cryptography

Question

Let \(E\) be the elliptic curve $$ E: y^{2}=x^{3}+1 $$ over a field \(K\), and suppose that \(K\) contains an element \(\beta \neq 1\) satisfying \(\beta^{3}=1\). (We say that \(\beta\) is a primitive cube root of unity.) Define a map \(\phi\) by $$ \phi(x, y)=(\beta x, y) \quad \text { and } \quad \phi(\mathcal{O})=\mathcal{O} . $$ (a) Let \(P \in E(K)\). Prove that \(\phi(P) \in E(K)\). (b) Prove that \(\phi\) respects the addition law on \(E\), i.e., \(\phi\left(P_{1}+P_{2}\right)=\phi\left(P_{1}\right)+\phi\left(P_{2}\right)\) for all \(P_{1}, P_{2} \in E(K)\).

Step-by-Step Solution

Answer

(a) \( \phi(P) \in E(K) \) because \( \beta^3 = 1 \). (b) \( \phi \) respects addition as it commutes with point addition on \( E \).

Step 1: Show that \( P \) is on \( E \)

Given that \( P \) is a point on the elliptic curve \( E \), it satisfies the curve's equation: \( y^2 = x^3 + 1 \). Thus \( P = (x, y) \), with \( y^2 = x^3 + 1 \).

Step 2: Apply \( \phi \) to \( P \)

The map \( \phi \) is defined as \( \phi(x, y) = (\beta x, y) \). Applying \( \phi \) to \( P = (x, y) \), we have \( \phi(P) = (\beta x, y) \).

Step 3: Verify that \( \phi(P) \) is on \( E \)

For \( \phi(P) = (\beta x, y) \) to be on the elliptic curve \( E \), it must satisfy the equation \( y^2 = (\beta x)^3 + 1 \). Calculate the right side: \((\beta x)^3 = \beta^3 x^3 = x^3\). Since \( y^2 = x^3 + 1 \), \( y^2 = (\beta x)^3 + 1 \), confirming \( \phi(P) \) is on \( E \).

Step 4: Consider the addition law for \( E \)

The points on an elliptic curve have a group structure with an addition operation. This operation respects the algebraic structure defined by the equation of the curve.

Step 5: Compute \( P + Q \) for \( P = (x_1, y_1), Q = (x_2, y_2) \)

If \( P \) and \( Q \) are points on \( E \), \( P + Q = (x_3, y_3) \) is found through the chord-tangent rule or geometric addition. Suppose \( \lambda = \frac{y_2 - y_1}{x_2 - x_1} \) (if \( x_1 eq x_2 \)), then \( x_3 = \lambda^2 - x_1 - x_2 \) and \( y_3 = \lambda(x_1 - x_3) - y_1 \).

Step 6: Show \( \phi(P + Q) = \phi(P) + \phi(Q) \)

Let \( \phi(P_1) = (\beta x_1, y_1) \) and \( \phi(P_2) = (\beta x_2, y_2) \). Compute \( \phi(P_1) + \phi(P_2) = (x_3', y_3') \) using the same addition law but with inputs \( \beta x_1, y_1 \) and \( \beta x_2, y_2 \). Using the identity \( \beta^3 = 1 \), \( x_3' = \beta x_3 \). Thus \( \phi(P + Q) = (\beta x_3, y_3) = \phi((x_3, y_3)) \), hence \( \phi(P + Q) = \phi(P) + \phi(Q) \).

Key Concepts

Addition Law on Elliptic Curves

Elliptic curves are fascinating mathematical structures that are not just confined to theoretical research but find applications in cryptography and number theory. One of their most interesting properties is how we define the addition of two points on such a curve. This is known as the "Addition Law on Elliptic Curves".
For an elliptic curve, we usually express the addition of two points, say \(P = (x_1, y_1)\) and \(Q = (x_2, y_2)\), in the form of another point \(P + Q = (x_3, y_3)\). The geometric method of addition uses the principle of drawing a line through \(P\) and \(Q\), where this line intersects the curve at a third point. The reflection of this third point across the x-axis gives \(x_3, y_3\).
In terms of formulas, when the points are distinct \((x_1 eq x_2)\), the slope \(\lambda\) is calculated as \(\lambda = \frac{y_2 - y_1}{x_2 - x_1}\). Then, \(x_3\) and \(y_3\) can be derived using:\

• \(x_3 = \lambda^2 - x_1 - x_2\)
• \(y_3 = \lambda(x_1 - x_3) - y_1\)

This addition respects the algebraic structure imposed by the elliptic curve's equation, ensuring consistency and closure under addition.

Primitive Roots of Unity

Primitive roots of unity are closely tied to the concept of roots of equations. They are special numbers that, when raised to a certain power, produce the unity of the mathematical system, often 1. Specifically, a primitive \(n\)-th root of unity is a complex number \(\zeta\) such that \(\zeta^n = 1\), and no smaller positive power of \(\zeta\) is equal to 1.
In the context of the given problem, \(\beta\) is a primitive cube root of unity, meaning it satisfies \(\beta^3 = 1\) and \(\beta eq 1\). This property is crucial because it allows manipulations on elements of the field \(K\) such as scaling points \((x, y)\) on the elliptic curve \(E\) using \(\beta\).
Properties of primitive roots of unity include:

• They lie on the unit circle in the complex plane.
• They form a cyclic group under multiplication.
• They can be used in polynomial factorization and solving polynomial equations.

Understanding primitive roots of unity can lead to insights in multiple areas such as Fourier transforms and signal processing.

Field Extensions

Field extensions enhance the structure of a given field by introducing new elements and operations. They allow mathematicians and scientists to solve equations that would be unmanageable in smaller fields.
Simply put, if we have a field \(F\) and we introduce new elements to form a larger field \(E\), where \(F \subseteq E\), \(E\) is an extension of \(F\).
This concept plays an important role when discussing elliptic curves over different fields. For instance, the elliptic curve \(E\) in the problem is defined over a field \(K\) that contains an element \(\beta\). Here, \(K\) could be a field extension of a smaller field, allowing \(\beta\) to act as the primitive cube root of unity necessary for the map \(\phi\) to be applicable.
Field extensions can be characterized in several ways:

• Simplicity: Achieved by adding a single new element.
• Algebraic: All elements of the extension are roots of polynomials with coefficients in the smaller field.
• Transcendental: At least one element cannot be expressed as a root of any polynomial with coefficients in the smaller field.

By understanding field extensions, we have a powerful tool to investigate polynomial equations and their solutions.