Rings of Low Multiplicative Complexity

AbstractThe complexity of the multiplication operation in finite fields is of interest for both theoretical and practical reasons. For example, an optimal normal basis for F2N 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 F2N by working in a larger ring R of dimension N+1 over F2. 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