Is there a way (different than projective closure) to obtain inversion free elliptic curve addition formulas ?
-
$\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$ – Lery Jul 10 '17 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$ – codilla Jul 12 '17 at 20:55
$\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 '17 at 6:03
$\begingroup$
$\endgroup$
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$ – SEJPM♦ Jul 10 '17 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$ – puzzlepalace Jul 10 '17 at 20:48
-
$\begingroup$ Yeah, as I said its cheating, but every answer is going to implicitly have an inversion in there $\endgroup$ – CurveEnthusiast Jul 11 '17 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$ – Squeamish Ossifrage Aug 28 '17 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$ – CurveEnthusiast Sep 5 '17 at 0:21
