Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Thank you so much for creating this! Under the Curve61 point addition example, I was trying to follow the formula for adding two points: P:(x1, y1) + Q(x2, y2) = R(x3=l^2-x1-x2, y3=l(x1-x3)-y1) where l=(y2-y1)/(x2-x1). I tried to use the example P:(5, 7) + 23P:(2, 24) = (226/9, 2888/7) != 24P:(59, 55) and was wondering where I've gone wrong? Appreciate your response!


After a few missteps where I transcribed the vars wrong (laugh) I wrote out the calcs and was able to reach the correct result. Here's my step-by-step process, hope this helps!

https://gist.github.com/syncsynchalt/ed02e39ad7adc8580b1086f...

Looking at your comment the disconnect seems to be at the division step: when performing a division such as 226/9, look up or calculate the multiplicative inverse for 9 (you can use the table at https://curves.ulfheim.net/inverse61.html), which is 34, and multiply by that instead. This is explained at https://curves.ulfheim.net/#division-multiplicative-inverse

In F61, 226/9 = 226*34 = 7684 % 61 = 59.

In F61, 2888/27 = 2888*52 = 150176 % 61 = 55.

(you can also proactively reduce those numerators and calculate with some smaller numbers):

(226%61)/9 => 43/9

(2888%61)/27 => 21/27


Thanks for explaining and creating the gist! Makes sense now that everything (* / + -) needs to be done modulo 61.


You haven't gone wrong, those are equal in F_61.

    226 / 9
  = (226*34) / (9*34)
  = 7684 / 306
  = 7684 / 1            (since 306 = 1 mod 61)
  = 59 / 1              (since 7684 = 59 mod 61)
I think y3=2888/7 is a typo for 2888/27, which also equals 55 by a similar calculation (1/27 = 52 mod 61).


That was definitely a typo. Thanks for your response!




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: