Two Normal Basis Multiplication Algorithms for GF(2ⁿ)

For software implementations, word-level normal basis multiplication algorithms utilize the full data-path of the processor, and hence are more efficient than the bit-level multiplication algorithm presented in the IEEE standard P1363-2000. In this paper, two word-level normal basis multiplication algorithms are proposed for GF(2ⁿ). The first algorithm is suitable for high complexity normal bases, while the second algorithm is fast for type-Ⅰ optimal normal bases and low complexity normal bases. Theoretical analyses and experimental results both indicate that the presented algorithms are efficient in GF(2²³³), GF(2²⁸³), GF(2⁴⁰⁹), and GF(2⁵⁷¹), which are four of the five binary fields recommended by the National Institute of Standards and Technology (NIST) for the elliptic curve digital signature algorithm (ECDSA) applications.