1.3 Elliptic curve point addition

Elliptic curve point addition is a key operation that combines two points on a curve to get a third. It's the foundation for the group structure of elliptic curves, crucial for cryptography and other applications.

The geometric interpretation involves drawing lines through points, while the algebraic formula provides efficient computation. Understanding point addition rules and special cases is essential for working with elliptic curves in various fields.

Definition of point addition

• Point addition is a fundamental operation on elliptic curves that allows us to combine two points on the curve to obtain a third point, also on the curve
• The set of points on an elliptic curve, together with the point at infinity, form an abelian group under the point addition operation
• Point addition is essential for many applications of elliptic curves, such as cryptography and factorization algorithms

Geometric interpretation

Top images from around the web for Geometric interpretation

• 

  Elliptic Curve Cryptography: a gentle introduction - Andrea Corbellini View original

  Is this image relevant?

• 

  The Math Behind Elliptic Curves in Weierstrass Form - Sefik Ilkin Serengil View original

  Is this image relevant?

• 

  Annotated curve E with points P, R, R' and line L labeled. P is tangent to the curve. View original

  Is this image relevant?

• 

  Elliptic Curve Cryptography: a gentle introduction - Andrea Corbellini View original

  Is this image relevant?

• 

  The Math Behind Elliptic Curves in Weierstrass Form - Sefik Ilkin Serengil View original

  Is this image relevant?

1 of 3

Top images from around the web for Geometric interpretation

• 

  Elliptic Curve Cryptography: a gentle introduction - Andrea Corbellini View original

  Is this image relevant?

• 

  The Math Behind Elliptic Curves in Weierstrass Form - Sefik Ilkin Serengil View original

  Is this image relevant?

• 

  Annotated curve E with points P, R, R' and line L labeled. P is tangent to the curve. View original

  Is this image relevant?

• 

  Elliptic Curve Cryptography: a gentle introduction - Andrea Corbellini View original

  Is this image relevant?

• 

  The Math Behind Elliptic Curves in Weierstrass Form - Sefik Ilkin Serengil View original

  Is this image relevant?

1 of 3

• Geometrically, point addition can be visualized by drawing a line through two points on the elliptic curve and finding the third point of intersection
• The third point of intersection is then reflected across the x-axis to obtain the sum of the two original points
• If the line is tangent to the curve at a point, the tangent point is counted twice as an intersection point

Algebraic formula

• The point addition operation can be expressed algebraically using the coordinates of the points involved
• For two points $P=(x_1,y_1)$ and $Q=(x_2,y_2)$ on an elliptic curve $y^2=x^3+ax+b$, their sum $R=(x_3,y_3)$ is given by:
  • $x_3 = \lambda^2 - x_1 - x_2$
  • $y_3 = \lambda(x_1 - x_3) - y_1$
  • where $\lambda = \frac{y_2-y_1}{x_2-x_1}$ if $P \neq Q$, and $\lambda = \frac{3x_1^2+a}{2y_1}$ if $P = Q$
• The algebraic formula allows for efficient computation of point addition in various implementations

Point addition rules

• Point addition on elliptic curves satisfies several important rules that make it a well-defined group operation
• These rules ensure that the set of points on an elliptic curve, together with the point at infinity, form an abelian group under point addition
• Understanding these rules is crucial for working with elliptic curves and their applications

Identity element

• The point at infinity, denoted as $\mathcal{[O](https://www.fiveableKeyTerm:o)}$, serves as the identity element for point addition on elliptic curves
• For any point $P$ on the curve, $P + \mathcal{O} = P$ and $\mathcal{O} + P = P$
• The point at infinity is a special point that does not have finite coordinates and is considered to be on every vertical line

Inverse elements

• For every point $P=(x,y)$ on an elliptic curve, there exists an inverse point $-P=(x,-y)$
• The sum of a point and its inverse is the point at infinity: $P + (-P) = \mathcal{O}$
• The inverse of the point at infinity is itself: $-\mathcal{O} = \mathcal{O}$

Commutativity

• Point addition on elliptic curves is commutative, meaning that for any two points $P$ and $Q$ on the curve, [P + Q](https://www.fiveableKeyTerm:p_+_q) = Q + P
• Commutativity is an important property that simplifies many calculations and proofs involving elliptic curves
• The commutativity of point addition is a consequence of the geometric interpretation of the operation

Associativity

• Point addition on elliptic curves is associative, meaning that for any three points $P$, $Q$, and $R$ on the curve, $(P + Q) + R = P + (Q + R)$
• Associativity allows for the unambiguous definition of point multiplication, which is the repeated addition of a point to itself
• The associativity of point addition is crucial for the group structure of elliptic curves and their use in cryptographic protocols

Point addition on real numbers

• When working with elliptic curves over the real numbers, point addition can be performed using the geometric and algebraic methods described earlier
• However, there are some special cases to consider when the x-coordinates of the points are identical or when the line connecting the points is vertical
• Understanding these cases is important for the correct implementation of point addition algorithms

Distinct x-coordinates

• When adding two points $P=(x_1,y_1)$ and $Q=(x_2,y_2)$ with distinct x-coordinates ($x_1 \neq x_2$), the sum $R=(x_3,y_3)$ is computed using the standard algebraic formulas
• The slope of the line connecting $P$ and $Q$ is given by $\lambda = \frac{y_2-y_1}{x_2-x_1}$
• The x-coordinate of the sum is $x_3 = \lambda^2 - x_1 - x_2$, and the y-coordinate is $y_3 = \lambda(x_1 - x_3) - y_1$

Identical x-coordinates

• When adding a point $P=(x,y)$ to itself (point doubling), or when adding two points with the same x-coordinate but different y-coordinates, the slope of the tangent line or vertical line is used in the computation
• For point doubling, the slope of the tangent line is given by $\lambda = \frac{3x^2+a}{2y}$, where $a$ is a parameter of the elliptic curve equation
• The x-coordinate of the sum is $x_3 = \lambda^2 - 2x$, and the y-coordinate is $y_3 = \lambda(x - x_3) - y$

Vertical line exception

• When adding two points with the same x-coordinate and opposite y-coordinates, the line connecting them is vertical
• In this case, the sum of the points is defined as the point at infinity, $\mathcal{O}$
• This exception is consistent with the geometric interpretation of point addition and ensures that the group law holds for all points on the curve

Point addition on finite fields

• Elliptic curves can also be defined over finite fields, such as the integers modulo a prime number ($\mathbb{F}_p$) or binary fields ($\mathbb{F}_{2^m}$)
• Point addition on elliptic curves over finite fields follows the same general principles as over real numbers, but with some additional considerations
• Finite field arithmetic is used to perform the necessary computations, and the field characteristic plays a role in the formulas and algorithms

Modular arithmetic

• When working with elliptic curves over the finite field $\mathbb{F}_p$, all computations are performed modulo the prime number $p$
• The elliptic curve equation is modified to $y^2 \equiv x^3 + ax + b \pmod{p}$, where $a$ and $b$ are constants in $\mathbb{F}_p$
• Point addition formulas are adapted to use modular arithmetic, ensuring that all intermediate results and the final sum are elements of the finite field

Field characteristic

• The characteristic of a finite field is the smallest positive integer $k$ such that $\underbrace{1 + 1 + \cdots + 1}_{k \text{ times}} = 0$ in the field
• For prime fields $\mathbb{F}_p$, the characteristic is the prime number $p$
• The field characteristic affects the elliptic curve equation and the point addition formulas, particularly in the case of binary fields ($\text{char} = 2$) and fields of characteristic 3 ($\text{char} = 3$)

Distinct x-coordinates

• When adding points with distinct x-coordinates on an elliptic curve over a finite field, the same formulas as in the real number case are used, but with modular arithmetic
• The slope $\lambda$ is computed as $\lambda \equiv (y_2 - y_1)(x_2 - x_1)^{-1} \pmod{p}$, where $(x_2 - x_1)^{-1}$ is the modular multiplicative inverse of $x_2 - x_1$
• The x-coordinate of the sum is $x_3 \equiv \lambda^2 - x_1 - x_2 \pmod{p}$, and the y-coordinate is $y_3 \equiv \lambda(x_1 - x_3) - y_1 \pmod{p}$

Identical x-coordinates

• When adding a point to itself (point doubling) or adding points with the same x-coordinate but different y-coordinates on an elliptic curve over a finite field, the formulas are adapted using modular arithmetic
• For point doubling, the slope of the tangent line is $\lambda \equiv (3x^2 + a)(2y)^{-1} \pmod{p}$, where $(2y)^{-1}$ is the modular multiplicative inverse of $2y$
• The x-coordinate of the sum is $x_3 \equiv \lambda^2 - 2x \pmod{p}$, and the y-coordinate is $y_3 \equiv \lambda(x - x_3) - y \pmod{p}$

Computation of point addition

• Computing point addition on elliptic curves involves several steps, each of which can be optimized for efficiency and security
• The main steps include calculating the slope of the line connecting the points, finding the intersection of this line with the curve, and reflecting the intersection point across the x-axis
• Various algorithms and techniques can be used to perform these computations, depending on the specific requirements of the application

Slope calculation

• The first step in point addition is to calculate the slope of the line connecting the two points (or the tangent line in the case of point doubling)
• For points with distinct x-coordinates, the slope is computed as $\lambda = \frac{y_2 - y_1}{x_2 - x_1}$ (or using modular arithmetic in finite fields)
• For point doubling, the slope of the tangent line is computed as $\lambda = \frac{3x^2 + a}{2y}$ (or using modular arithmetic in finite fields)
• Efficient algorithms for modular multiplication, inversion, and division are used to compute the slope in finite field implementations

Intersection with curve

• Once the slope is calculated, the next step is to find the intersection point of the line with the elliptic curve
• The x-coordinate of the intersection point is computed as $x_3 = \lambda^2 - x_1 - x_2$ (or using modular arithmetic in finite fields)
• The y-coordinate of the intersection point is then computed using the elliptic curve equation: $y_3 = \lambda(x_1 - x_3) - y_1$ (or using modular arithmetic in finite fields)
• These computations involve modular exponentiation and multiplication, which can be optimized using techniques such as Montgomery multiplication or fast modular reduction

Reflection across x-axis

• The final step in point addition is to reflect the intersection point across the x-axis to obtain the sum of the two original points
• This is done by negating the y-coordinate of the intersection point: $(x_3, -y_3)$
• In finite field implementations, negation is performed using modular subtraction: $-y_3 \equiv p - y_3 \pmod{p}$ for prime fields, or using a specific negation algorithm for binary fields
• The reflection step ensures that the sum of the points is another point on the elliptic curve, satisfying the group law

Applications of point addition

• Point addition on elliptic curves has several important applications in cryptography and number theory
• These applications rely on the security and mathematical properties of elliptic curves, such as the difficulty of solving the discrete logarithm problem
• Some of the most notable applications include elliptic curve cryptography, elliptic curve factorization, and elliptic curve primality testing

Elliptic curve cryptography

• Elliptic curve cryptography (ECC) is a public-key cryptography system that uses the algebraic structure of elliptic curves over finite fields
• In ECC, point addition is used to perform scalar multiplication, which is the main operation in key generation, encryption, and digital signature algorithms
• ECC provides the same level of security as other public-key systems (e.g., RSA) with smaller key sizes, making it suitable for resource-constrained environments such as smartphones and IoT devices

Elliptic curve factorization

• Elliptic curve factorization (ECF) is a method for integer factorization that uses elliptic curves to find factors of large composite numbers
• The basic idea behind ECF is to construct an elliptic curve modulo the composite number and perform point additions to find points with certain properties that reveal factors of the original number
• ECF algorithms, such as Lenstra's elliptic curve factorization method, can be more efficient than other factorization methods for certain types of numbers

Elliptic curve primality testing

• Elliptic curve primality testing (ECPT) is a probabilistic primality test that uses elliptic curves to determine whether a given integer is prime or composite
• ECPT algorithms, such as Goldwasser-Kilian and Atkin-Morain tests, rely on the properties of point addition and the group structure of elliptic curves over finite fields
• These tests are based on the fact that the number of points on an elliptic curve modulo a prime number satisfies certain conditions, which can be checked by performing point additions and comparing the results with the expected values

Geometric properties

• The geometric properties of elliptic curves and point addition provide valuable insights into the structure and behavior of these mathematical objects
• Some of the most important geometric properties include the role of tangent lines, collinear points, and inflection points
• Understanding these properties is crucial for the analysis and design of elliptic curve-based algorithms and protocols

Tangent lines

• Tangent lines play a central role in the geometric interpretation of point addition on elliptic curves
• When adding a point to itself (point doubling), the tangent line at that point is used to find the intersection point with the curve, which is then reflected across the x-axis to obtain the sum
• The slope of the tangent line is given by $\lambda = \frac{3x^2 + a}{2y}$, where $(x, y)$ is the point being doubled and $a$ is a parameter of the elliptic curve equation
• Tangent lines are also used in the computation of the group law and in the analysis of the geometric properties of elliptic curves

Collinear points

• Three points on an elliptic curve are said to be collinear if they lie on the same straight line
• Collinearity is closely related to point addition, as the sum of two points on an elliptic curve is defined as the reflection of the third point of intersection of the line connecting the two points with the curve
• If three points are collinear, their sum (using the group law) is equal to the point at infinity, $\mathcal{O}$
• Collinearity properties are used in various elliptic curve-based algorithms, such as the computation of torsion points and the analysis of the group structure

Inflection points

• An inflection point on an elliptic curve is a point where the curve changes from being concave to convex, or vice versa
• Mathematically, an inflection point is a point where the second derivative of the elliptic curve equation equals zero
• For elliptic curves in short Weierstrass form, $y^2 = x^3 + ax + b$, the inflection points are the points where $y = 0$ (i.e., the points where the curve intersects the x-axis)
• Inflection points play a role in the analysis of the geometric and algebraic properties of elliptic curves, and they are used in some cryptographic protocols and attacks

Group law for elliptic curves

• The group law for elliptic curves defines the algebraic structure of the set of points on an elliptic curve, together with the point at infinity
• Under the group law, point addition satisfies the axioms of an abelian group, which include closure, associativity, the existence of an identity element, and the existence of inverse elements
• The group law is essential for understanding the mathematical properties of elliptic curves and their applications in cryptography and other fields

Closure under addition

• The set of points on an elliptic curve, together with the point at infinity, is closed under the point addition operation
• This means that the sum of any two points on the curve (or the point at infinity) is always another point on the curve (or the point at infinity)
• Closure under addition is one of the fundamental properties that make elliptic curves suitable for use in cryptography and other applications
• It ensures that point addition is a well-defined operation and that the set of points forms a mathematical group

Abelian group structure

• The set of points on an elliptic curve, together with the point at infinity, forms an abelian group under the point addition operation
• An abelian group is a group in which the group operation (in this case, point addition) is commutative, meaning that $P + Q = Q + P$ for any two points $P$ and $Q$ on the curve
• The abelian group structure of elliptic curves is characterized by the following axioms:
  • Closure: $\forall P, Q \in E, P + Q \in E