Design of Multiplexer-Based Multi-Exponentiation on the Normal Bases

Abstract—Finite field is mainly used in communications. In those arithmetic operations, modular exponentiation is an important unit for most public-key cryptosystems and some error-correcting codes. In this paper, we propose an algorithm to compute multi-exponentiation on the normal basis. This algorithm, a multiplexer-based design, expands from Chiou and Lee's proposal. The main objective of this algorithm is to reduce the complexity of space and to speed up the performance. We also provide a strategy to design the multi-exponentiation unit when the number of elements in multi-exponentiation is a large and composite number. Due to its regularity and simplicity, the design and expansion to a high-order finite field exponentiation is much easier to realize