A Euclidean Algorithm for Normal Bases
- PDF / 239,888 Bytes
- 18 Pages / 439.37 x 666.142 pts Page_size
- 32 Downloads / 180 Views
A Euclidean Algorithm for Normal Bases B. Sunar
Published online: 1 August 2006 © Springer Science + Business Media B.V. 2006
Abstract Inversion in finite fields GF(2k) is a critical operation for many applications. A well-known representation basis, i.e., normal basis, provides an efficient squaring operation realized as a simple rotation of the operand coefficients. Inversion in normal basis is computed using methods derived from Fermat’s Little theorem, e.g., the Itoh–Tsujii algorithm or with the aid of basis conversion algorithms using the Extended Euclidean algorithm. In this paper we present alternative normal basis inversion algorithm derived from the polynomial version of the extended Euclidean algorithm. The normal basis Euclidean algorithm has (roughly) the same complexity as the polynomial version of the Euclidean algorithm. The proposed algorithm requires on average a linear number of multiplications. We also present a modification to our algorithm which delays the multiplications to the very end of the computation and thereby gives opportunity for recursive computation using only a logarithmic number of multiplications. Mathematics Subject Classifications (2000) 11A05 · 11A67 · 11T55 · 11T06 · 11T71. Key words extended Euclidean algorithm · finite fields · normal basis · inversion.
This work was supported by the National Science Foundation ITR Awards # 0112889 and CAREER Award # 0133297. To appear in Finite Fields: Applications and Implementations “Acta Applicandae Mathematicae,” Special Issue of Springer Journal. B. Sunar (B) Electrical & Computer Engineering, Worcester Polytechnic Institute, Worcester, MA 01609, USA e-mail: [email protected]
58
Acta Appl Math (2006) 93: 57–74
1. Introduction Arithmetic operations in the Galois field GF(2m) have many applications in coding theory, computer algebra, and cryptography [2, 10]. For these applications, time and area efficient algorithms and hardware architectures are desired for addition, multiplication, squaring, and inversion operations. The performance of these operations is closely related to the representation of the field elements. In a major advance in this area Massey–Omura [11] introduced a multiplication algorithm based on the normal basis representation of the field elements. The main advantage of using a normal basis is that the squaring operation becomes a cyclic shift of the binary representation. Due to the efficient squaring property significant effort went into developing efficient normal basis multipliers [5, 6, 9, 12]. On the other hand efforts in developing normal basis inversion algorithms have produced only a limited number of choices. Perhaps the most popular is the parallel Itoh and Tsujii [7] inversion k algorithm which is derived from Fermat’s Little Theorem, i.e., A2 −1 = 1 (for A 6 = 0 ∈ GF(2k)). Several derivatives of the Itoh–Tsujii algorithm have been proposed [3, 13]. The Itoh–Tsujii algorithm achieves inversion by computing the exponentiation k A−1 = A2 −2 (for A 6= 0 ∈ GF(2k)) using a clever recursive decomposition techni
Data Loading...
