Solving Quadratic equations in Galois Field (2^163)

Question

Hello I am working on implementing a message to elliptic curve point mapping hardware circuit I have done some research and found out the koblitz mapping method: I will be using a field of binary polynomials F(2^163) the equation will be of the form of : $$ y^2 + xy = x^3 + x^2 + 1 $$

The given algorithm consists of checking the Tr "Trace of polynomial" at first and then solving the quadratic equation based on the chosen coordinate "x" that satisfied the needed trace conditions and obtain "y" the second coordinate I have given to understand that finding the trace of any polynomial C in field 163 is XORing(bit0,bit157) of the given polynomial

But after calculating the Trace and finding the x coordinates I do not understand how to solve the quadratic equation in hardware and how to implement it I have found some reading material suggesting of calculating the H(C) which is the half trace of the polynomial C but my questions are:

1.What is trace of a polynomial and how it is calculated? is it by xoring all bit together from 0 to m-1 ?

2. what is half trace ? and how does it relate to trace? and why is it used to solving quadratic equation isn't it a 1 -bit answer

3. how can I solve the given equation to obtain the y coordinate and if there are 2 Y answers which one will be chosen?

Thank you I really appreciate the help. I could not find clear reading material on this matter with a simplified and easy to read algorithm/pseudo-code

Added: I found the following algorithm but I do not know what it's name? and how are the parameters a2n and a2n+1 computed and how they vary for different fields lets say (163)

algorithm for solving the equation taken from: A Low-Power Design for an Elliptic Curve Digital Signature Chip (Rich Schroeppel, Tim Draelos, Russell Miller, Rita Gonzales, Cheryl Beaver)

Answer 1

I'll try to give additional explanation on algebraic number and the link with EC.

Let $q=2^{163}$ the finite Field $F_q=GF(q)$, as selected by NIST has some features for doing cryptography. This field has been generated with the irreduccible pentanomial you gave in the table. To understand what the trace of the polynomial is, it corresponds to the coefficient of monom of degré 162, which is Zero in this case. And remembering that any finite field could never be algebraically closed, we can considere all the 163 roots of p, $\{x_0..., x_{162} \}$, which are conjugate each other. The trace of the polynomial is simply the sum of all its roots. But as they are all conjugate, only one root suffices to calculate the trace by repeating square. (Cf ref books). Then we see, that we can define the trace of any element in $F_q$ by $Tr(\alpha)=\sum_{i=0}^{i=162}\alpha^{2^{2^i}}$. This define a linear map (endomorphism) from $F_q$ to $F_2=\{0,1\}$!

Now the "Trace" map, is useful to help in solving quadratic equation. if $\lambda$ is a solution in $F_q$ of $\lambda^2 + \lambda = b$, then so is $\lambda+1$. This show that the equation is solvable only if $Tr(b)=0$

And the link with EC ? As fkraiem observes it, you have nothing to do! NIST has done all the work by selecting the field of appropriate size, generating polynomial and indicates how to get the trace for any algebraic element in $F_q$. For this case of K-163 (Koblits Curve) or B-163 (random Curve), and a given $\mu \in F_q$, $Tr(\mu)=\mu_{157}+\mu_0$ snipped from the table you show us.

When we want to select randomly a point on a given standardized curve EC: $y^2+xy=x^3+a_2.x^2+a_6$, we begin by chosing the abscisse $x\neq 0$, and then try to compute the corresponding y! setting $z=\frac{y}{x}$ gives $z^2+z=x+a_2+\frac{a_6}{x^2}$, which allow us to understand why the trace of the second member must be Zero in the algorithm 2 shown above.

The Half Trace, can be explained by the fact that in a finite field there is exactly the same number of quadratic and Non-quadratic residues.

Then the Half trace is defined by $\tau(\alpha)=\sum_{i=0}^{\frac{n-1}{2}}\alpha^{2^{2i}}$(Ref N. Smart Elliptic Curves in Cryptography), which gives the solution of the equation. There are generally 2 solutions, and you can select one to build the point, the other allow to select the opposite point. And when a solution is chosen, the point is $P=(\alpha, \lambda.\alpha)$, and a straiforward calculation allow to check that it belong to EC!

@user3368764: I'd a look to the paper you indicate. They use a tower factorization of finite field $GF(2^{178})$. As 178=2.89, a first field extention $GF(2^{89})=GF(2)/(u^{89}+u^{38}+1)$, followed by $GF(2^{89})/(v^2+v+1)$ allow to get $GF(2^{178})$. If you plan to design a hardware for $GF(2^{163})$ it can't be used for another field. Arithmetic in Binary is simple, but unfortunaltly not flexible.

Now Let's return to Nigel Smart's book for depicting the solution of $\lambda^2+\lambda+\beta=0\cdots$! Recall that any finite field of $q=2^{163}$ elements, field'elements are charaterized by $X^q=X$. Then with the definition of Half Trace : $$\tau(\beta)=\sum_{i=0}^{\frac{n-1}{2}}\beta^{2^{2i}}=\beta+\beta^{2^2}+\beta^{2^4}+\cdots+\beta^{2^{n-3}}+\beta^{2^{n-1}}$$ In a binary field, the square is a linear operator, which gives: $$\tau(\beta)^2=\beta^2+\beta^{2^3}+\beta^{2^5}+\cdots+\beta^{2^{n-2}}+\beta^{2^{n}}$$ As $\beta^{2^{n}}=\beta$, it remains: $\tau(\beta)^2+\tau(\beta)=\beta+Tr(\beta)$ which mean that if $Tr(\beta)=0$; then $\tau(\beta)$ is a solution of the quadratic equation

Answer 2

1. Actually, you don't compute the trace of a polynomial per se, but of a finite-field element, which is expressed as a polynomial-like expresssion with $u$ acting as the indeterminate. ($u$, as you are probably aware, is a root of the generating polynomial $p(t)$.) Mathematically, the trace of $u$ is $$\mathrm{Tr}(u) = u + u^2 + u^4 + \cdots + u^{2^{162}}$$ and if you are willing to do the arithmetic, you will see that it is equal to what you are given.
2. I have never heard of the term "half-trace". EDIT: It seems that it can be used to make square roots extraction faster using more sophisticated algorithms than the obvious one. I guess you can look into that as an optimisation once you have a working implementation using more basic algorithms.
3. The usual quadratic formula to solve $ax^2+bx+c=0$ does not apply in characteristic $2$ since the denominator $2a$ is then equal to $0$. The situation is a lot more complicated, and is described for example in this article.