Paper 2007/103

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

Roberto Avanzi


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\%$.

Note: Extended version with new results of previous note.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Binary fieldsPolynomial basisSquare root extractionTrace computationQuadratic equationsPoint halvingDivisor halving.
Contact author(s)
roberto avanzi @ gmail com
2007-05-30: last of 10 revisions
2007-03-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Roberto Avanzi},
      title = {Another Look at Square Roots and Traces (and Quadratic Equations) in Fields of Even Characteristic},
      howpublished = {Cryptology ePrint Archive, Paper 2007/103},
      year = {2007},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.