uplinks:: Elliptic Curve
tags:: #lang/en

Elliptic Curve Arithmetic

Point Addition

  • A point addition is the operation of adding two elliptic curve points
  • there is a natural way to take two points on an elliptic

Let

  • E:Y2=X3+AX+BE: Y^2 = X^3 + AX + B be an Elliptic Curve
  • OO as point at infinity
  • P1=(x1,y1)P_1 = (x_1,y_1) and P2=(x2,y2)P_2 = (x_2,y_2) be points on EE

If P1=OP_1 = O, then P1+P2=P2P_1 + P_2 = P_2
If P2=OP_2 = O, then P1+P2=P1P_1 + P_2 = P_1
If x1=x2x_1 = x_2 and y1=−y2y_1 = -y_2 , then P1+P2=OP_1 + P_2 = O
Else, let

λ={y2−y1x2−x1,if P2≠P2,3x12+A2y1,if P1=P2,\lambda = \begin{cases} \frac{y_2 - y_1}{x_2 - x_1}, & \text{if } P_2 \neq P_2, \\ \frac{3x_1^2 + A}{2y_1}, & \text{if } P_1 = P_2, \end{cases}

and let

x3=λ2−x1−x2andy3=λ(x1−x3)−y1x_3 = \lambda^2 - x_1 - x_2 \qquad\text{and}\qquad y_3 = \lambda(x_1 - x_3) - y_1

Then P1+P2=(x3,y3)P_1 + P_2 = (x_3,y_3)

Point Scalar Multiplication

A point scalar multiplication is the operation of adding a point along an elliptic curve to itself repeatedly.

Let E:Y2=X3+AX+BE: Y^2 = X^3 + AX + B be an Elliptic Curve
Let PP be a point on EE

kP=P+P+P+⋯+Pk times point double/addition\begin{gather} kP = P + P + P + \dots + P \\ k\text{ times point double/addition} \end{gather}

This is similar to modular exponentiation:

gk≡g⋅g⋅g⋯g(modp)k times modular multiplication\begin{gather} g^k \equiv g \cdot g \cdot g \cdots g \pmod{p} \\ k \text{ times modular multiplication} \end{gather}

See Also

  1. Modular Arithmetic

References

  1. Peking University Introduction to Information Security Class