Efficient calculation of point coordinates with elliptic curves over binary field

Question

I'm trying to find an efficient algorithm to calculate the $y$ coordinate of a an elliptic curve point given its $x$ coordinate, for elliptic curves over fields of the form $2^m$ with polynomial representation of the field elements.

I had the exact same problem with elliptic curves over prime fields, but it is very simple to solve:

$y^2 = x^2 + ax +b \implies y = \sqrt{x^2 +ax +b}$

With this equation, all we got to do is to calculate the value of the second member, check if the value is a quadratic residue modulo the prime number (using Euler's criterion) then calculate the root, if it exists, using Tonelli-Shanks algorithm.

For binary fields the equation is

$y^2 +xy = x^3 +ax^2 +b$

Fixing the value of $x$, the equation can be reduced to something like

$y^2 +uy +v = 0$

It is a simple quadratic equation, but I can not solve it with the polynomial arithmetic, since we have $y = \frac{-b \pm\sqrt{b^2 - 4ac}}{2a}$ and multiplying by an even number using this arithmetic results in $0$. Even worst, it would be necessary to divide by the scalar $2$ to find the roots, and there is no such operation defined.

Of course there is brute force, to test all polynomials with degree less than the degree of the reduction polynomial, but it is impractical as soon the the degree gets to high.

I'm new here and I would appreciate some help.

Answer 1

First, break it into a simpler problem: Divide by $u^2$ to rewrite $y^2 + uy + v = 0$ as $$(y/u)^2 + y/u + v/u^2 = 0;$$ then solve for $y/u$, and multiply the result by $u$.

$% Evidently mathjax's \operatorname fails to kern properly, so % \operatorname{Tr} has an awful gap between T and r. Worse, the % \operatorname command blindly substitutes \text{-} for - anywhere % in its argument, so \operatorname{T\kern-.98pt r} fails. (This % kern assumes cmr10 (actually, lmroman10, on which latinmodern-math % is based), where the true value is (1.5*23.5/36)pt, which is % approximately .695pt. No \mathchoice because mathjax doesn't do % smaller designed font sizes; it just scales cmr10 to other point % sizes.) \def\Trname{T\kern-.695pt r}% \DeclareMathOperator{\Tr}{\Trname}% \DeclareMathOperator{\GF}{GF}% % Fake \clap. Real one is (modulo math mode conditionals): % \def\clap#1{\hbox to 0pt{\hss#1\hss}} \def\clap#1{\mkern-10mu#1\mkern-10mu}% $How do you solve $t^2 + t + d = 0$ for $t$? (Here $t = y/u$ and $d = v/u^2$.) Suppose we are working in $\GF(2^m)$. It is necessary that $$\Tr(d) := \sum_{i=0}^{m-1} d^{2^i} = d + d^2 + d^4 + d^8 + \dotsb + d^{2^{m - 1}} = 0,$$ where $\Tr(d)$ is the trace of $d$ over $\GF(2^m)$ as a field extension of $\GF(2)$, for if $\alpha$ is a root of $t^2 + t + d$ in $\GF(2^m)$, then $\Tr(d) = \Tr(\alpha^2 + \alpha) = \Tr(\alpha^2) + \Tr(\alpha) = \alpha^{2^m} + \alpha = 0$. Now break this down into two cases.

1. $m$ is odd. In this case, the half-trace

   \begin{align*} H(d) := \sum_{i=0}^{\clap{(m - 1)/2}} d^{2^{2i}} = d + d^4 + d^{16} + \dotsb + d^{2^{m - 3}} + d^{2^{m - 1}} \end{align*}

   is related to the trace $\Tr(d)$ by

   \begin{align*} H(d)^2 &= \sum_{i=0}^{\clap{(m - 1)/2}} \bigl(d^{2^{2i}}\bigr)^2 = \sum_{i=0}^{\clap{(m - 1)/2}} d^{2^{2i + 1}} \\ &= d^2 + d^8 + d^{32} + \dotsb + d^{2^{m - 2}} + d^{2^m} \\ &= d^2 + d^8 + d^{32} + \dotsb + d^{2^{m - 2}} + d \\ &= \Tr(d) + H(d) + d, \end{align*}

   since squaring is linear in $\GF(2^m)$. If $t^2 + t + d$ has a root so that $\Tr(d) = 0$, then we have $H(d)^2 + H(d) + d = \Tr(d) = 0$; hence $H(d)$ is a root of $t^2 + t + d$.

2. $m$ is even. This case is a pain, and therefore left as an exercise for the reader who is less lazy than I am. (Hardly anyone ever uses elliptic curves over even-power binary extension fields in cryptography; usually the power is an odd prime.)