PARALLEL MULTIPLICATION IN F{sub}(2n) USING CONDENSED MATRIX REPRESENTATION

摘要

In this paper we explore a matrix representation of binary fields F{sub}(2n) defined by an irreducible trinomial P = X{sup}n + X{sup}k + 1. We obtain a multiplier with time complexity of T{sub}A + ([log_2 (n)])T{sub}X and space complexity of (2n - 1) n AND and (2n - 1)(n - 1) XOR. This multiplier reaches the lower bound on time complexity. Until now this was possible only for binary field defined by AOP (Silverman, 1999), which are quite few. The interest of this multiplier remains theoretical since the size of the architecture is roughly two times bigger than usual polynomial basis multiplier (Mastrovito, 1991; Koc and Sunar, 1999).