ECC Sample Problems 2

The two problemsSearch on YouTubeBookmarkSaved

Problem set 2 is a handwritten sheet. It does point addition in two prime fields. The steps are the same as in set 1. Only the modulus and the inverses change.

Addition formulasSearch on YouTubeBookmarkSaved

$\lambda = \left(\frac{y_Q - y_P}{x_Q - x_P}\right) \bmod p, \qquad x_R = (\lambda^2 - x_P - x_Q) \bmod p$

$y_R = \left(\lambda(x_P - x_R) - y_P\right) \bmod p, \qquad P + Q = (x_R, y_R)$

Modular inverse with extended EuclidSearch on YouTubeBookmarkSaved

Each slope contains a division. To divide by $a$ modulo $p$, multiply by $a^{-1}$. Find $x$ with $a \cdot x \equiv 1 \pmod p$.

Inverse of 3 modulo 19Search on YouTubeBookmarkSaved

The sheet uses this inverse in problem 1:

• $19 = 6 \times 3 + 1$
• $1 = 19 - 6 \times 3$
• so $3^{-1} = -6 \bmod 19 = 13$

Check: $3 \times 13 = 39 = 38 + 1 \equiv 1 \pmod{19}$.

Inverse of 4 modulo 31Search on YouTubeBookmarkSaved

The sheet uses this inverse in problem 2:

• $31 = 7 \times 4 + 3$
• $4 = 1 \times 3 + 1$
• $1 = 4 - 1 \times 3 = 4 - (31 - 7 \times 4) = 8 \times 4 - 31$
• so $4^{-1} \bmod 31 = 8$

Check: $4 \times 8 = 32 = 31 + 1 \equiv 1 \pmod{31}$.

Problem 1: modulo 19Search on YouTubeBookmarkSaved

Given. Curve $y^2 = x^3 + 5x + 7$, modulus $p = 19$, points $P = (6, 1)$ and $Q = (2, 6)$.

SlopeSearch on YouTubeBookmarkSaved

$\lambda = \frac{6-1}{2-6} \bmod 19 = \frac{5}{-4} \bmod 19$

$-4 \bmod 19 = 15$, so $\lambda = 5 / 15 \bmod 19$. The sheet cancels 5 and gets $1/3$. Then $\lambda = 3^{-1} \bmod 19 = 13$.

Another route gives the same value. $15^{-1} = 14$, because $15 \times 14 = 210 = 19 \times 11 + 1$. Then $5 \times 14 = 70 \equiv 13 \pmod{19}$.

$\boxed{\lambda = 13}$

x coordinateSearch on YouTubeBookmarkSaved

$x_R = (13^2 - 6 - 2) \bmod 19 = (169 - 8) \bmod 19 = 161 \bmod 19$

$161 = 19 \times 8 + 9$, so:

$x_R = 9$

y coordinateSearch on YouTubeBookmarkSaved

Put $x_P = 6$, $x_R = 9$ and $y_P = 1$ in the formula:

$y_R = \left(13(6 - 9) - 1\right) \bmod 19 = (-39 - 1) \bmod 19 = -40 \bmod 19$

$-40 + 3 \times 19 = 17$, so:

$y_R = 17$

Answer.

$P + Q = (9, 17)$

Problem 2: modulo 31Search on YouTubeBookmarkSaved

Given. Modulus $p = 31$, points $P = (8, 21)$ and $Q = (12, 26)$. The sheet notes that $P \neq Q$, so the addition formula applies.

SlopeSearch on YouTubeBookmarkSaved

$\lambda = \frac{26 - 21}{12 - 8} \bmod 31 = \frac{5}{4} \bmod 31$

Use $4^{-1} \bmod 31 = 8$ from the Euclid steps above:

$\lambda = 5 \times 8 \bmod 31 = 40 \bmod 31 = 9$

$\boxed{\lambda = 9}$

x coordinateSearch on YouTubeBookmarkSaved

$x_R = (9^2 - 8 - 12) \bmod 31 = (81 - 20) \bmod 31 = 61 \bmod 31 = 30$

y coordinateSearch on YouTubeBookmarkSaved

Put $x_P = 8$, $x_R = 30$ and $y_P = 21$ in the formula:

$y_R = \left(9(8 - 30) - 21\right) \bmod 31 = (-198 - 21) \bmod 31 = -219 \bmod 31$

The sheet writes $-219 = -248 + 29$. $248 = 8 \times 31$, so:

$y_R = 29$

Answer.

$P + Q = (x_R, y_R) = (30, 29)$

Comparing the two problemsSearch on YouTubeBookmarkSaved

The steps do not change. Only the modulus, the divisor and its inverse change.

Quick self-testSearch on YouTubeBookmarkSaved

Reduce $\dfrac{5}{-4}$ modulo 19 and give $\lambda$.

$-4 \equiv 15 \pmod{19}$. $5/15 \equiv 1/3$, and $3^{-1} = 13$. So $\lambda = 13$.

What is $x_R$ in problem 1?

$x_R = 13^2 - 6 - 2 = 161$, and $161 - 8 \times 19 = 9$. So $x_R = 9$.

What is $y_R$ in problem 1, and which value does the formula subtract?

$y_R = 13(6-9) - 1 = -40 \equiv 17 \pmod{19}$. The formula subtracts $y_P = 1$.

Find $4^{-1} \bmod 31$ with extended Euclid.

$31 = 7 \times 4 + 3$ and $4 = 3 + 1$. So $1 = 4 - (31 - 7 \times 4) = 8 \times 4 - 31$. Thus $4^{-1} = 8$.

Give $P + Q$ for problem 2.

$\lambda = 40 \bmod 31 = 9$. $x_R = 61 \bmod 31 = 30$. $y_R = -219 \bmod 31 = 29$. So $P + Q = (30, 29)$.

Why does problem 2 not use the doubling formula?

$P \neq Q$, because $8 \neq 12$. The doubling slope $\lambda = (3x^2 + a)/(2y)$ is only for $P = Q$.

What is $P + Q$ when $x_P = x_Q$ and $y_Q = -y_P$?

The line is vertical and the slope is not defined. $P + Q = O$, the point at infinity.