Paper 2015/028

Optimal software-implemented Itoh--Tsujii inversion for GF($2^m$)

Jeremy Maitin-Shepard


Field inversion in GF($2^m$) dominates the cost of modern software implementations of certain elliptic curve cryptographic operations, such as point encoding/hashing into elliptic curves. Itoh--Tsujii inversion using a polynomial basis and precomputed table-based multi-squaring has been demonstrated to be highly effective for software implementations, but the performance and memory use depend critically on the choice of addition chain and multi-squaring tables, which in prior work have been determined only by suboptimal ad-hoc methods and manual selection. We thoroughly investigated the performance/memory tradeoff for table-based linear transforms used for efficient multi-squaring. Based upon the results of that investigation, we devised a comprehensive cost model for Itoh--Tsujii inversion and a corresponding optimization procedure that is empirically fast and provably finds globally-optimal solutions. We tested this method on 8 binary fields commonly used for elliptic curve cryptography; our method found lower-cost solutions than the ad-hoc methods used previously, and for the first time enables a principled exploration of the time/memory tradeoff of inversion implementations.

Available format(s)
Publication info
Preprint. MINOR revision.
finite fieldsinversionnumber theory
Contact author(s)
jeremy @ jeremyms com
2015-01-14: received
Short URL
Creative Commons Attribution


      author = {Jeremy Maitin-Shepard},
      title = {Optimal software-implemented Itoh--Tsujii inversion for GF($2^m$)},
      howpublished = {Cryptology ePrint Archive, Paper 2015/028},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.