7 ms·

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)

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!

edflsafoiewq 4y ago
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).
- max_likelihood 4y ago
  That was definitely a typo. Thanks for your response!
deleted 4y ago
[deleted]
syncsynchalt 4y ago
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/ed02e39ad7adc8580b1086f6e34d8ab1 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 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 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
- max_likelihood 4y ago
  Thanks for explaining and creating the gist! Makes sense now that everything (* / + -) needs to be done modulo 61.

edflsafoiewq 4y ago

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

max_likelihood 4y ago
That was definitely a typo. Thanks for your response!

deleted 4y ago

[deleted]

syncsynchalt 4y ago

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/ed02e39ad7adc8580b1086f6e34d8ab1 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 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 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

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