Finding points on an elliptic curve

Question

I have an elliptic curve $$x^3+17x+5 \mod 59$$

$P = (4,14)$ is given and I need to find point $8P$.

to calculate $8P$, I first calculated $2P$

by using the equation sigma = 3x^2+a/2y = (3*4^2+17)/(2*14) mod 59 = 65/28 mod 59 = 2.3214 mod 59.

x3 = sigma^2-2x = -2.61 mod 59 y3 = sigma(x1-x3)-y = 1.312 mod 59

so 2p = (56.39,1.312) , Are these answers correct or should I get integer values?

Answer 1

There are various ways to do this, but I will use the method you show.

We are given the elliptic curve

$$x^3+17x+5 \pmod{59}$$

We are asked to find $8P$ for the point $P = (4,14)$.

I will do one and you can continue.

We have:

$$\lambda = \dfrac{3 x_1^2 + A}{2 y_1} = \dfrac{3 \times 4^2 + 17}{2 \times 14} = \dfrac{65}{28} = 65 \times 28^{-1} \pmod{59} = 65 \times 19 \pmod{59} = 55$$

Recall, we are finding a modular inverse over a field as $28^{-1} \pmod{59}$ and not division!

Next, we have:

$$\nu = y_1 - \lambda x_1 \pmod{59} = 14 - 55 \times 4 \pmod{59} = -206 \pmod{59} = 30$$

Now we can find $(x_3, y_3)$ as:

• $x_3 = \lambda^2 - x_1 - x_2 \pmod{59} = 55^2 - 4 - 4 \pmod{59} = 3017 \pmod{59} = 8$
• $y_3 = -(\lambda x_3 + \nu) \pmod{59} = -(55 \times 8 + 30) \pmod{59} = -470 \pmod{59} = 2$

For you to practice (although you do not actually need each of these points to find $8P$ and there is point multiplication like $4 \times 2P$ and others that can make the calculations much shorter), here are all of the intermediate points:

• $1P = (4, 14)$
• $2P = P + P = (8, 2)$
• $3P = 2 P + P = (56, 24)$
• $4P = 2P + 2P = 3P + 1P = (48, 32)$
• $5P = (58, 39)$
• $6P = (22, 17)$
• $7P = (15, 53)$
• $8P = 4P + 4P = (16, 40)$

Three excellent references on the matter:

• The Arithmetic of Elliptic Curves, J. H. Silverman
• A Course in Number Theory and Cryptography, N. Koblitz
• Guide to Elliptic Curve Cryptography , D. Hankerson, A. J. Menezes, S. Vanstone