[Community Puzzle] Elliptic curve cryptography

https://www.codingame.com/training/hard/elliptic-curve-cryptography

Send your feedback or ask for help here!

Created by @Coni,validated by @_CG_Nick,@Fireball0923 and @Niako.
If you have any issues, feel free to ping them.

1 Like

This puzzle is very hard to debug, because only the final result is known and there are many steps where things can go wrong.
I have a nasty bug that I cannot find for weeks.
I fail even simplest test case #01. Here k = 2, so I assume I need to find “2 * G”.

Could anyone please write what is the expected L in this operation? (Maybe my modulo arithmethics functions are wrong.)

Or could you please give what is the result of
point(0, 0) + point(1, 1)
and of
point(1, 1) + point(1, 1)

(1,1)
(4602044434169447759, 4602044434169447760)

1 Like

Actually the operation + only makes sense on the elliptic curve (y^2 = x^3 + 7 mod P in this puzzle), while points (0,0) and (1,1) are not on this curve, so there is no right answer to your question…
The first answer given by @nicola1 seems to imply that (0,0) is the neutral element of the group, which is not the case (and actually it’s not even in the group).

That said, for the operation G+G, we have L = 2032944238605471208 and the result is (2685467149996858908, 1223440626623933451).

1 Like

Thank you! I finally found the bug: it was indeed in the “modulo division” code.