Ternary extension fields GF(3m) have been used in cryptographic applications based on bilinear-mappings in elliptic curve cryptography. In this paper, we focus on accelerating inversion in GF(3m) which is an indispensable operation in such applications. We propose a fast execution-time inversion algorithm which decomposes (m−1) of GF(3m) into several factors and a remainder and restricts the remainder to belong to the shortest addition chain of a suitable factor. Thus, unlike other algorithms that not decompose (m−1) and search for large near-optimal addition chains for (m−1) to compute the inverse, our algorithm relies on much smaller and known chains for the suitable factors. In decomposing (m−1) with the use of small and known chains for the suitable factors, as far as we know, our proposal is the fastest polynomial-time inversion algorithm in comparison with its counterparts.
Digital Object Identifier (DOI)
Mahmoud, Walid and Wu, Huapeng
"Accelerating Finite Field Inversion in GF(3m) for Elliptic Curve Cryptography,"
Applied Mathematics & Information Sciences: Vol. 10
, Article 2.
Available at: https://dc.naturalspublishing.com/amis/vol10/iss5/2