Low space complexity CRT-based bit-parallel GF (2(n)) polynomial basis multipliers for irreducible trinomials

摘要

This paper presents new space complexity records for the fastest parallel GF (2(n)) multipliers for about 22% values of n such that a degree-n irreducible trinomial f = u(n) + u(k) + 1 exists over GF (2). By selecting the largest possible value of k epsilon (n/2, 2n/3], we further reduce the space complexities of the Chinese remainder theorem (CRT)-based hybrid polynomial basis multipliers. Our experimental results show that among the 539 values of n epsilon [5, 999] such that f is irreducible for some k epsilon [2, n 2], there are 317 values of n such that k epsilon (n/2, 2n/3]. For these irreducible trinomials, the space complexities of the CRT -based hybrid multipliers are reduced by 14.3% on average. As a comparison, the previous CRT -based multipliers considered the case k epsilon [2, n/2], and the improvement rate is 8.4% on average for only 290 values of n among these 539 values of n.