Elliptic Curve Multiplication: Coordinate Arithmetic

A Bitcoin public key is derived by multiplying a secret 256-bit scalar integer (the private key, $k$) by a fixed coordinate base point (the generator point, $G$).

To understand how a computer executes this math, we must explore the algebraic laws of elliptic curve coordinate arithmetic.

---

📐 Point Addition ($P + Q = R$)

On an elliptic curve, adding two distinct points $P(x_P, y_P)$ and $Q(x_Q, y_Q)$ yields a third point $R(x_R, y_R)$ on the curve.

Geometrically, we draw a straight line through $P$ and $Q$. The line intersects the curve at a third point, which we then reflect across the x-axis to find $R$.

                     ELLIPTIC CURVE POINT ADDITION
          y ▲
            │           * (Reflection) R (x_R, y_R)
            │          /
            │         /
            │  P *---/-----------* Intersect
            │     \ /
            │      * Q
            │     /
            └────/────────────────────────► x
                /

⚙️ The Algebraic Equations

Over a finite field modulo $p$, the coordinates of $R = P + Q$ are calculated as:

1. Calculate the slope ($\lambda$):

$$\lambda = \frac{y_Q - y_P}{x_Q - x_P} \pmod p$$

1. Calculate the new coordinates ($x_R, y_R$):

$$x_R = \lambda^2 - x_P - x_Q \pmod p$$

$$y_R = \lambda(x_P - x_R) - y_P \pmod p$$

(Note: Division is performed as multiplication by the modular multiplicative inverse)

---

📈 Point Doubling ($2P = R$)

When adding a point to itself ($P + P$), we cannot draw a line through two distinct points. Instead, we draw a line tangent to the curve at point $P$. This tangent line intersects the curve at a second point, which we reflect across the x-axis to yield $R = 2P$.

⚙️ The Algebraic Equations

Since we are using the curve equation $y^2 = x^3 + 7 \pmod p$, the derivative of the curve gives us the slope of the tangent:

1. Calculate the tangent slope ($\lambda$):

$$\lambda = \frac{3x_P^2}{2y_P} \pmod p$$

1. Calculate the doubled coordinates ($x_R, y_R$):

$$x_R = \lambda^2 - 2x_P \pmod p$$

$$y_R = \lambda(x_P - x_R) - y_P \pmod p$$

---

🚀 Scalar Multiplication: Double-and-Add

To compute $K = k \cdot G$, a computer cannot simply perform $G + G + G + \dots$ billions of times; it would take trillions of years.

Instead, software uses the binary Double-and-Add algorithm, which performs the operation in logarithmic time ($O(\log k)$), completing in under 512 coordinate operations.

⚙️ The Double-and-Add Algorithm

To multiply $G$ by a scalar $k$ (e.g., $k = 105$, which is 1101001 in binary):

1. Initialize an accumulator point: $T = \text{Point at Infinity}$ (or null).
2. Set the base doubler point: $D = G$.
3. Read the binary bits of $k$ from right to left (least significant to most significant):

Bit Index	Bit Value	Action	State of Doubler ($D$)	State of Accumulator ($T$)
0	1 (Active)	Add $D$ to $T$	$D \leftarrow 2G$	$T \leftarrow G$
1	0	Double $D$	$D \leftarrow 4G$	$T \leftarrow G$
2	0	Double $D$	$D \leftarrow 8G$	$T \leftarrow G$
3	1 (Active)	Add $D$ to $T$	$D \leftarrow 16G$	$T \leftarrow G + 8G = 9G$
4	0	Double $D$	$D \leftarrow 32G$	$T \leftarrow 9G$
5	1 (Active)	Add $D$ to $T$	$D \leftarrow 64G$	$T \leftarrow 9G + 32G = 41G$
6	1 (Active)	Add $D$ to $T$	$D \leftarrow 128G$	$T \leftarrow 41G + 64G = 105G$

By doubling the point $D$ at every step and only adding it to the accumulator $T$ when a binary bit is 1, the calculation completes in exactly 256 doublings and a maximum of 256 additions.