Parallel Itoh–Tsujii multiplicative inversion algorithm for a special class of trinomials

• Published in: Designs, codes, and cryptography codes, and cryptography, 2007-10, Vol.45 (1), p.19-37
• Main Authors: Rodríguez-Henríquez, Francisco, Morales-Luna, Guillermo, Saqib, Nazar A., Cruz-Cortés, Nareli
• Format: Article
• Language: English
• ISSN: 0925-1022; 1573-7586
• DOI: 10.1007/s10623-007-9073-6

In this contribution, we derive a novel parallel formulation of the standard Itoh-Tsujii algorithm for multiplicative inverse computation over the field GF(2 super(m)). The main building blocks used by our algorithm are: field multiplication, field squaring and field square root operators. It achieves its best performance when using a special class of irreducible trinomials, namely, P(x) = x super(m) + x super(k) + 1, with m and k odd numbers and when implemented in hardware platforms. Under these conditions, our experimental results show that our parallel version of the Itoh-Tsujii algorithm yields a speedup of about 30% when compared with the standard version of it. Implemented in a Virtex 3200E FPGA device, our design is able to compute multiplicative inversion over GF(2 super(193)) after 20 clock cycles in about 0.94 mu S.