# Given paramaters of an Edward's curve and x, determine a y value if it exists

I'm making a demonstration cryptosystem using ECC ElGamal. I've currently got a working implementation of Edward's Curve operations and a basic ElGamal implementation (Encrypts only points on the curve), and in order to perform the mapping operation described in this answer, I need to determine the $$y$$ value of a point on an Edward's curve $$g$$ given an $$x$$. I have a basic understanding of the way an Edward's curve works but the finite fields are a bit much for me to be confident in properly implementing this based on intuition. Any help is appreciated.

The equation for an Edwards curve is $$x^2 + y^2 = 1 + dx^2y^2$$. Assuming you know the curve parameters then, given that you know $$x$$, you are solving the above equation for one unknown, namely $$y$$. We can rewrite this as a quadratic equation in one unknown and solve it. Note that all operations are $$\bmod{p}$$ where $$p$$ is the characteristic of the field the curve is defined over (remember that dividing by $$z$$ is equivalent to multiplying by $$z^{-1}\bmod{p}$$, square roots also have different rules).

$$x^2 + y^2 = 1 + dx^2y^2$$ $$y^2 - dx^2y^2 + x^2 - 1 = 0$$ $$(1 - dx^2)y^2 + (x^2 - 1) = 0$$

Now let $$a = (1 - dx^2)$$, $$b = 0$$, and $$c = (x^2 - 1)$$ (so we have $$ay^2 + by + c = 0$$ i.e. a quadratic equation). Note that you can also move some terms around in the upper equation and end up at the same result.

$$y = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$$ $$y = \frac{-0 \pm \sqrt{0 - 4(1 - dx^2)(x^2 - 1)}}{2(1 - dx^2)}$$ $$y = \frac{\pm \sqrt{-4(1 - dx^2)(x^2 - 1)}}{2(1 - dx ^2)}$$ $$y = \pm \sqrt{\frac{1 - x^2}{1 - dx^2}}$$

Now substitute in $$x$$ and $$d$$. Note that there are two solutions to the equation. Without your x coordinate having some sort of encoding that indicates which y value should be used it is impossible to recover the "correct" y as both values result in distinct valid points.

• Thank you! When you say all operations are mod p, does that mean every operation I do in the final equation has to be mod p – ThePlasmaRailgun Oct 9 '18 at 23:05
• This doesn't appear to be an appropriate solution for extremely large values of d or x, Python's sqrt operator returns an overflow error. – ThePlasmaRailgun Oct 10 '18 at 1:17
• Well in this case the square root is a modular square root (since it's in a field), which is different than pythons sqrt function (which additionally operates on floats not integers, the max value that a float can represent is usually much less than the values numbers take in a cryptographic context). Use Tonelli-Shanks to find square roots in the context of modular arithmetic. – puzzlepalace Oct 10 '18 at 5:51
• Thanks, just figured that out before you posted. However, it's currently very slow because I'm calulating for each x value what the y value is if it exists. Is there a similar check to just see if a y value exists in a way that is faster than calculating the y value? – ThePlasmaRailgun Oct 10 '18 at 18:42
• It'll boil down to finding out whether the term $\frac{1 - x^2}{1 - dx^2}$ has a modular square root. See this math SE answer for more details. – puzzlepalace Oct 11 '18 at 20:44