Rings of low multiplicative complexity

The complexity of the multiplication operation in finite fields is of inter est for both theoretical and practical reasons. For example, an optimal nor mal basis for F-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 F-2N. by wor king in a larger ring R of dimension N + 1 over F-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. (C) 2000 Academic Press.