1
$\begingroup$

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. enter image description here

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you very much for your explanation! $\endgroup$ Mar 29 at 3:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.