# Is there any reference about the half-trace when m is even in F(2^m)

There is a algorithm listed in D.1.6, Algorithm 3, it seems that it is used to solve the quadratic equation when $$m$$ is even in $$F(2^m)$$. However, I can not find any reference about this algorithm, as well as the definition about half-trace when $$m$$ is even. Can anyone introduce some basic ideas or reference about this algorithm, many thanks.

Good reference for this include section II.2.4 of Elliptic Curves in Cryptography (Blake, Seroussi, Smart) or section 11.2.6 of the Handbook of elliptic and hyperelliptic curve cryptography (Cohen and Frey).

For completeness, I'll give a brief overview of quaddratic equation in characteristic 2. In fields of characteristic 2, quadratic equations can be converted by a linear change of variable to one of the two forms $$x^2+\beta=0$$ $$x^2+x+\beta=0.$$ In the first case there is a single repeated root and by the field equation $$X^{2^m}-X=0$$ we can compute this as $$x=\beta^{2^{m-1}}$$.

In the second case there will be no roots or two roots of the form $$z$$ and $$z+1$$ because $$(z+1)^2+(z+1)=z^2+z$$. If we take the trace of $$x^2+x+\beta$$ we see get $$\mathrm{Tr}(x^2)+\mathrm Tr(x)+\mathrm{Tr}(\beta)=\mathrm{Tr}(x)+\mathrm Tr(x)+\mathrm{Tr}(\beta)=\mathrm{Tr}(\beta)$$ and so we can see that the two root case corresponds to equations with $$\mathrm{Tr}(\beta)=0$$.

For odd $$m$$ we note that the equation could be written $$x^2+x=\mathrm{Tr}(\beta)+\beta=\beta^{2^{m-1}}+\beta^{2^{m-2}}+\cdots+\beta^2$$ $$=(\beta^{2^m-2})^2+(\beta^{2^m-4})^2+\cdots+(\beta^2)^2+\beta^{2^m-2}+\cdots+\beta^2$$ $$=(\beta^{2^m-2}+\beta^{2^m-4}+\cdots+\beta^2)^2+(\beta^{2^m-2}+\beta^{2^m-4}+\cdots+\beta^2)$$ so that we may take $$x=\beta^{2^m-2}+\beta^{2^m-4}+\cdots+\beta^2$$ for one solution (and add 1 of the other).

For even $$m$$ we require an auxiliary element $$\tau$$ of trace 1 so that $$x^2+x=\tau\mathrm{Tr}(\beta)+\beta\mathrm{Tr}(\tau)=$$ $$=\tau(\beta^{2^{m-1}}+\beta^{2^{m-2}}+\cdots+\beta^2)+\beta(\tau^{2^{m-1}}+\cdots+\tau^2)$$ $$=(\beta^{2^{m-2}}\tau^{2^{m-1}}+\beta^{2^{m-3}}(\tau^{2^{m-1}}+\tau^{2^{m-2}})+\cdots+\beta(\tau^{2^{m-1}}+\cdots+\tau^2))^2+(\beta^{2^{m-2}}\tau^{2^{m-1}}+\beta^{2^{m-3}}(\tau^{2^{m-1}}+\tau^{2^{m-2}})+\cdots+\beta(\tau^{2^{m-1}}+\cdots+\tau^2))$$ allowing us to take $$x=\beta^{2^{m-2}}\tau^{2^{m-1}}+\beta^{2^{m-3}}(\tau^{2^{m-1}}+\tau^{2^{m-2}})+\cdots+\beta(\tau^{2^{m-1}}+\cdots+\tau^2)$$ as one solution (adding 1 for the other).

Algorithm 3 above chooses a random $$\tau$$, efficiently computes the above expression as $$z$$ while computing $$w=\tau\mathrm{Tr}(\beta)$$ at the same time. At step 4 it checks to see if $$w=0$$ and if so deduces that $$\mathrm{Tr}(\beta)=0$$ and a solution can exist. At step 6 it tests if $$z^2+z=\tau(\mathrm{Tr}(\beta)+\beta(\mathrm{Tr}(\tau)=0$$. If this is the case, then $$\mathrm{Tr}(\tau)=0$$ and we must try again. As 50% of elements have non-zero trace, we should not need many attempts.

• Thank you very much for your explanation! Mar 29 at 3:04