How to Compute the Modular Inverse in Elliptic-Curve Addition

When you add elliptic-curve points over a finite field, the slope formula contains a division. Since field elements are calculated modulo a prime $p$, that division means multiplication by a modular inverse. The extended Euclidean algorithm computes the inverse.

This is not the same as finding the inverse point of a curve point. The modular inverse is used to calculate the slope; the inverse point is the point that adds to the identity.

The short-Weierstrass formulas below assume an odd prime $p$ and a nonsingular curve, so $4a^3+27b^2\not\equiv0\pmod p$.

What needs to be inverted?

For distinct points $P=(x_1,y_1)$ and $Q=(x_2,y_2)$ on a short Weierstrass curve $y^2=x^3+ax+b$ over the prime field $\mathbb{F}_p$, when $x_2\ne x_1$, the slope is

$$\lambda = (y_2-y_1)(x_2-x_1)^{-1} \pmod p.$$

The notation $(x_2-x_1)^{-1}$ means the multiplicative inverse of $x_2-x_1$ modulo $p$. It is the residue $u$ satisfying

$$u(x_2-x_1) \equiv 1 \pmod p.$$

When doubling a point $P=(x_1,y_1)$ with $y_1\ne0$, use the tangent slope instead:

$$\lambda = (3x_1^2+a)(2y_1)^{-1} \pmod p.$$

After finding the slope, the coordinates of the sum are

$$x_3 = \lambda^2-x_1-x_2 \pmod p, \qquad y_3=\lambda(x_1-x_3)-y_1 \pmod p.$$

All arithmetic, including subtraction and multiplication, is reduced modulo $p$.

Find the inverse with extended Euclid

For an integer $d$ not divisible by prime $p$, the Euclidean algorithm finds the greatest common divisor of $d$ and $p$. The extended version also finds integers $u$ and $v$ such that

$$ud+vp=\gcd(d,p).$$

Because $p$ is prime and $d$ is nonzero modulo $p$, the gcd is $1$. Reducing the equation modulo $p$ gives $ud\equiv1\pmod p$, so $u$ reduced modulo $p$ is the inverse of $d$.

For example, to invert $5$ modulo $17$:

$$\begin{aligned} 17 &= 3\cdot 5+2,\\ 5 &= 2\cdot 2+1. \end{aligned}$$

Back-substitute to express $1$ using $5$ and $17$:

$$1=5-2(17-3\cdot5)=7\cdot5-2\cdot17.$$

Thus $7\cdot5\equiv1\pmod{17}$, and $5^{-1}\equiv7\pmod{17}$. You can verify it directly: $5\cdot7=35\equiv1\pmod{17}$.

Worked point-addition example

Consider the curve $y^2=x^3+2x+2$ over $\mathbb{F}_{17}$ and the points $P=(5,1)$ and $R=(10,6)$. Both lie on the curve. For instance, at $P$, the right side is $5^3+2\cdot5+2=137\equiv1=1^2\pmod{17}$.

The slope denominator is $x_R-x_P=10-5=5$. From the Euclidean calculation above, its inverse modulo $17$ is $7$. Therefore

$$\lambda=(6-1)\cdot7=35\equiv1\pmod{17}.$$

Now calculate the sum coordinates, reducing each result modulo $17$:

$$\begin{aligned} x_3 &= 1^2-5-10=-14\equiv3\pmod{17},\\ y_3 &= 1(5-3)-1=1\pmod{17}. \end{aligned}$$

So $P+R=(3,1)$. The inverse was needed only to evaluate the slope; after that, the ordinary point-addition formulas give the result using modular arithmetic.

Common mistakes and special cases

• Using an ordinary fraction: Dividing by $5$ modulo $17$ does not mean using the real number $1/5$. It means multiplying by $5^{-1}\equiv7\pmod{17}$.
• Forgetting to reduce modulo $p$: Reduce intermediate results as needed. For example, $35$ is $1$ modulo $17$.
• Confusing two kinds of inverse: The additive inverse of $P=(x,y)$ is $-P=(x,-y\bmod p)$. On the example curve, $-(5,1)=(5,16)$ over $\mathbb{F}_{17}$.
• Trying to invert zero: If distinct-point addition has $x_2=x_1$, the denominator is zero. For distinct points on the curve, this means they are negatives of each other, and their sum is the point at infinity, the identity. In doubling, if $y_1=0$, the tangent is vertical and $2P$ is the point at infinity.
• Applying the prime-field rule to a composite modulus: A nonzero number modulo a composite $n$ may not have an inverse. In general, an inverse exists exactly when $\gcd(d,n)=1$. Elliptic-curve cryptographic groups commonly use a prime field, where every nonzero denominator has an inverse.

In code, an extended-Euclidean routine can return the inverse as a signed integer; reduce that result into the range $0,\ldots,p-1$ before using it. A denominator that is zero modulo $p$ is a point-addition special case, not an input for modular inversion.