Is there a way (different than projective closure) to obtain inversion free elliptic curve addition formulas ?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ For which curves? But in general, I believe we have such formulas for all curves, but sometimes you need to resort to special representations. You may find a lot of information on hyperelliptic.org/EFD/g1p/index.html $\endgroup$– LeryJul 10, 2017 at 17:03
-
$\begingroup$ Sorry I needed to be more clear. I mean an elliptic curve defined over a field characteristic different than 2 or 3. $\endgroup$– codillaJul 12, 2017 at 20:55
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Pick pretty much any projective coordinate system, and there is a plethora of inversion-free addition formulae. For example, here's a library of inversion-free formulae for addition and doubling in short Weierstrass curves with $a = -3$, which covers all the NIST prime curves and many curves deployed for DH and signatures before Curve25519, using standard projective coordinates: https://hyperelliptic.org/EFD/g1p/auto-shortw-projective-3.html
However, if you want affine coordinates in the end, I don't think you're likely to find a way to avoid inversions altogether—at best you can put off inversions until the end and do only a small number of them, possibly only 1, depending on what you're doing. E.g., $x$-restricted scalar multiplication on a Montgomery curve—as used by the X25519 Diffie–Hellman function—requires only one inversion at the end of the computation.
answered Aug 10, 2017 at 6:03
$\begingroup$
$\endgroup$
5
Let $E / \mathbb{F}_p : y^2 = x^3 + ax + b$ be an elliptic curve, let's say for some prime $p>3$. Let $P = (x_P,y_P)$ and $Q = (x_Q,y_Q)$. Let \begin{align*} s &= (y_P-y_Q)(x_P-x_Q)^{p-2}, \\ x_R &= s^2 - x_P - x_Q, \\ y_R &= y_P + s(x_R - x_P). \end{align*} Then $(x_R,y_R)=P+Q$. These are inversion-free addition formulas (yes I know I'm kinda cheating).
-
$\begingroup$ These are the standard formulas with division replaced by the equivalent exponentiation? $\endgroup$– SEJPMJul 10, 2017 at 20:32
-
1$\begingroup$ Yup looks like $s = \frac{y_P - y_Q}{x_P - x_Q}$ is replaced with $s = (y_P - y_Q)(x_P - x_Q)^{p-2}$ since $\frac{1}{x_P - x_Q} = (x_P - x_Q)^{p-2}$ in the case where $p$ is prime. $\endgroup$ Jul 10, 2017 at 20:48
-
$\begingroup$ Yeah, as I said its cheating, but every answer is going to implicitly have an inversion in there $\endgroup$ Jul 11, 2017 at 4:07
-
1$\begingroup$ This isn't cheating simply because you replaced inversion by exponentiation. Although you have expanded the domain from the expression with inversion, on the points on which the inversion was not defined you don't actually give the correct answer. For example, for $(0, 1) + (0, -1)$ this gives the point $(0, 1)$ instead of the point $\infty \ne (0, 1)$. $\endgroup$ Aug 28, 2017 at 16:08
-
$\begingroup$ @SqueamishOssifrage Yeah if an inversion is done you would implicitly assume that the element is actually invertible, and I do the same (but I could have made that more explicit!) $\endgroup$ Sep 5, 2017 at 0:21