Optimal tower fields

Selçuk Baktır

doi:10.1109/TC.2004.83

Return

Optimal tower fields

2004-10-01

PRE

Selçuk Baktır

Berk Sunar

DOI：10.1109/TC.2004.83

Original

Original request for help

Save

Abstract

En 中文

We introduce a new tower field representation, optimal tower fields (OTFs), that facilitates efficient finite field operations. The recursive direct inversion method we present has significantly lower complexity than the known best method for inversion in optimal extension fields (OEFs), i.e., Itoh-Tsujii's inversion technique. The complexity of our inversion algorithm is shown to be O(m(2)), significantly better than that of the Itoh-Tsujii algorithm, i.e., O(m(2) (log(2) m)). This complexity is further improved to O(m(log23)) by utilizing the Karatsuba-Ofman algorithm. In addition, we show that OTFs may be converted to OEF representation via a simple permutation of the coefficients and, hence, OTF operations may be utilized to achieve the OEF arithmetic operations whenever a corresponding OTF representation exists. While the original OTF multiplication and squaring operations require slightly more additions than their OEF counterparts, due to the free conversion, both OTF operations may be achieved with the complexity of OEF operations.

Keywords:

optimal tower fields

OEF

finite fields

multiplication

inversion

elliptic curve cryptography

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.