The present paper is interested in a family of normal bases, considered by Sidel’nikov [Math. USSR-Sb., 61 (1988), pp. 485–494], with the property that all the elements in a basis can be obtained from one element by repeatedly applying to it a linear fractional function of the form $\varphi ( x ) = ( ax + b )/( cx + d ),a,b,c,d \in F_q $. Sidel’nikov proved that the products for such a basis $\{ \alpha _i \}$ are of the form $\alpha _i \alpha _j = e_{i - j} \alpha _i + e_{j - i} \alpha _j + \gamma ,i = j$, where $e_k ,\gamma \in F_q $. It is shown that every such basis can be formed by the roots of an irreducible factor of $F( x ) = cx^{q + 1} + dx^q - ax - b$. The following are constructed: (a) a normal basis of $F_{q^n } $ over $F_q $ with complexity at most $3n - 2$ for each divisor n of $q - 1$ and for $n = p$, where p is the characteristic of $F_q$; (b) a self-dual normal basis of $F_{q^n } $ over $F_q $ for $n = p$ and for each odd divisor n of $q - 1$ or $q + 1$. When $n = p$, the self-dual normal basis constructed of $F_{q^p } $ over $F_q$ also has complexity at most $3p - 2$. In all cases, the irreducible polynomials and the multiplication tables are given explicitly.

The authors describe a VLSI Galois field processor and how it can be applied to the implementation of elliptic curve groups. They demonstrate the feasibility of constructing very fast, and very secure, public key systems with a relatively simple device, and the possibility of putting such a system on a smart card. The registers necessary to implement the elliptic curve system will require less than 1 mm/sup 2/ (or less than 4%) of the area available on the card.>

In this paper we examine the development of a high-speed implementation of a system to perform exponentiation in fields of the form GF(2 n ). For sufficiently large n, this device has applications in public-key cryptography. The selection of representation and observations on the structure of multiplication have led to the development of an architecture which is of low complexity and high speed. A VLSI implementation has being fabricated with measured throughput for exponentiation for cryptographic purposes of approximately 300 kilobits per second.