We have an elliptic curve E over Z29 and the base point P = (8,10), the curve is

Question

We have an elliptic curve E over Z29 and the base point P = (8,10), the curve is: E : y^2 = x^3+4x+20 mod 29.

Calculate the point multiplication k · P (for k=9) using the Double-and-Add algorithm. Provide the intermediate results after each step.

As you know, point multiplication has to be first simplified to just point addition(s) and doubling(s) and, then, perform each step separately.

Hint: The final result is (4,10), and for that, if you use a Double-and-Add algorithm, you need to do 3 doublings and one addition. Please show all the steps for these four operations.

Explanation / Answer

9P = (1001)2P

1 :: P = (8, 10)

0 :: 2P = 2(8, 10) = (0, 22)

0 :: 2P + 2P = 2(0, 22) = (6, 17)

1 :: 4P + 4P + P = 2(6, 17) + (8, 10) = (4, 10)

On More Example with K=20 for reference

20P = (10100)2P

1 :: P = (8, 10)

0 :: 2P = 2(8, 10) = (0, 22)

1 :: 2P + 2P + P = 2(0, 22) + (8, 10) = (20, 3)

0 :: 5P + 5P = 2(20, 3) = (17, 19)

1 :: 10P + 10P + P = 2(17, 19) + (8, 10) = (19, 13)

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.