## Cryptology ePrint Archive: Report 2007/103

**Another Look at Square Roots and Traces (and Quadratic Equations) in Fields of Even Characteristic**

*Roberto Avanzi*

**Abstract: **We discuss irreducible polynomials that can be
used to speed up square root extraction in fields of characteristic two.
We call such polynomials \textit{square root friendly}.
The obvious applications are to point halving methods for elliptic curves
and divisor halving methods for hyperelliptic curves.

We note the existence of square root friendly trinomials of a given
degree when we already know that an irreducible trinomial of the same
degree exists, and formulate a conjecture on the degrees of the terms of
square root friendly polynomials.
We also give a partial result
that goes in the direction of the conjecture.

Irreducible polynomials $p(X)$ such that the square root
$\zeta$ of a zero $x$ of $p(X)$ is a sparse polynomial are considered
and those for which $\zeta$ has minimal degree are characterized.
In doing this we discover a surprising connection
these polynomials
and those defining polynomial bases
with an extremal number of trace one elements.

We also show how to improve the speed of solving quadratic equations and
that the increase in the time required to perform modular reduction is
marginal and does not affect performance adversely.
Experimental results confirm that the new polynomials mantain their
promises; These results generalize work by Fong et al.\ to polynomials
other than trinomials. Point halving gets a speed-up of $20\%$ and the
performance of scalar multiplication based on point halving is improved
by at least $11\%$.

**Category / Keywords: **Binary fields, Polynomial basis, Square root extraction, Trace computation, Quadratic equations, Point halving, Divisor halving.

**Date: **received 22 Mar 2007, last revised 30 May 2007

**Contact author: **roberto avanzi at gmail com

**Available format(s): **PDF | BibTeX Citation

**Note: **Extended version with new results of previous note.

**Version: **20070530:120625 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]