# [Community Puzzle] Elliptic curve cryptography

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

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)`.

2 Likes

Thank you! I finally found the bug: it was indeed in the â€śmodulo divisionâ€ť code.

My code passes the first 3 tests (short and medium), but fails on the nexts (long).
Any idea what the cause could be ? I have no clue how to debug my code in this scenario
Edit: itâ€™s not a performance issue I get an answer, just not the right one.

my advise: be careful with your modular arithmethic code - avoid any possibility of a 64-bit integer overflow at EVERY step of the calculation.

1 Like

But to no avail unfortunately, my wrong answer didnâ€™t change in the process. The BigInt js library can handle huge numbers so I kinda expected this.

Iâ€™ve put my code on pastebin in case a good soul has some free time Iâ€™m feeling stuck tbh.
Edit : solved !

I am not a good human debugger in a language I donâ€™t knowâ€¦ But my modular arithmetics code is slightly different from yours. I can send you my solution in PM if that can help for your own debugging.

1 Like

@Djoums The point of `BigInt` is to avoid the limitations of JS numbers, hence `BigInt(parseInt(readline(), 16))` is not the best idea .
`BigInt(readline())` is simpler and will solve your issue (the `"0x"` prefix is good enough to indicate an hex input).