Re:The animated elliptic curve
by max_likelihood on Thursday June 16, 2022 @10:28PM
(#31773497)
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!
[ Parent
| on HN ]
Re:The animated elliptic curve
by syncsynchalt on Friday June 17, 2022 @12:03AM
(#31774000)
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
Re:The animated elliptic curve
by max_likelihood on Sunday June 19, 2022 @01:09PM
(#31801199)
Thanks for explaining and creating the gist! Makes sense now that everything (* / + -) needs to be done modulo 61.
Re:The animated elliptic curve
by edflsafoiewq on Thursday June 16, 2022 @11:25PM
(#31773808)
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).
Re:The animated elliptic curve
by max_likelihood on Sunday June 19, 2022 @01:06PM
(#31801174)
That was definitely a typo. Thanks for your response!