Timeline for Is there an economic way to check if an elliptic curve point in Jacobian coordiate is the same as a compressed point
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 18, 2017 at 5:47 | vote | accept | deadalnix | ||
| Mar 21, 2017 at 8:21 | comment | added | CurveEnthusiast | @MeysamGhahramani The definition of "cheap" is of course very context-dependent. There are definitely many circumstances where the division is not considered cheap. Note that the op is already using projective coordinates, but is trying to avoid decompression of $y$. I don't really see a way around either a division, or a square-root. | |
| Mar 20, 2017 at 21:02 | comment | added | Meysam Ghahramani | @deadalnix, If computing the multiplicative inverse is your problem, in projective coordination we don't compute any multiplicative inverse. for details you can see the page 88 of guide to elliptic curve cryptography, Darrel Hankerson, Alfred Menezes, Scott Vanstone. | |
| Mar 20, 2017 at 20:53 | comment | added | deadalnix | So no more than 1000 per second, and if the machine does nothing else. It is quite substantial. This is why I want to avoid the inversion in the first place. | |
| Mar 20, 2017 at 20:48 | comment | added | Meysam Ghahramani | @poncho, $O(n^3)$ or $O(n^2)$? Note that, $n$ is a number of digits of number, and we are talking about elliptic curves. Is it not cheap? I computed the inverse of $100000$ bit numbers in less that millisecond, by MAGMA. I'm sorry, maybe I don't know the meaning of cheap. | |
| Mar 20, 2017 at 20:16 | comment | added | poncho | So, an $O(n^3)$ algorithm is "cheap"? That's obviously a meaning of cheap that I'm not familiar with... | |
| Mar 20, 2017 at 19:14 | history | edited | Meysam Ghahramani | CC BY-SA 3.0 |
added 49 characters in body
|
| Mar 20, 2017 at 19:07 | comment | added | Meysam Ghahramani | Dear @poncho, I think that in Euclidean algorithm, simple and cheap are same, because of its low complexity. | |
| Mar 20, 2017 at 19:04 | history | edited | Meysam Ghahramani | CC BY-SA 3.0 |
added 49 characters in body
|
| Mar 20, 2017 at 19:00 | comment | added | poncho | Simple $\ne$ cheap... | |
| Mar 20, 2017 at 18:56 | history | answered | Meysam Ghahramani | CC BY-SA 3.0 |