Rings of Low Multiplicative Complexity

The complexity of the multiplication operation in finite fields is of interest for both theoretical and practical reasons. For example, an optimal normal basis for 2N has complexity 2N−1. A construction described in J. H. Silverman, (“Cryptographic Hardware and Embedded Systems,” Lecture Notes in Computer Science, Vol. 1717, pp. 122–134, Springer–Verlag, Berlin, 1999.) allows multiplication of complexity N+1 to be performed in 2N by working in a larger ring R of dimension N+1 over 2. In this paper we give a complete classification of all such rings and show that this construction is the only one which also has a certain useful permutability property.