International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Parallel Itoh-Tsujii Multiplicative Inversion Algorithm for a Special Class of Trinomials

Authors:
Francisco Rodríguez-Henríquez
Guillermo Morales-Luna
Nazar A. Saqib
Nareli Cruz-Cortés
Download:
URL: http://eprint.iacr.org/2006/035
Search ePrint
Search Google
Abstract: In this contribution, we derive a novel parallel formulation of the standard Itoh-Tsujii algorithm for multiplicative inverse computation over GF($2^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^m + X^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^193$) after 20 clock cycles in about $0.94\mu$S.
BibTeX
@misc{eprint-2006-21528,
  title={Parallel Itoh-Tsujii Multiplicative Inversion Algorithm for a Special Class of Trinomials},
  booktitle={IACR Eprint archive},
  keywords={foundations / number theory, implementation},
  url={http://eprint.iacr.org/2006/035},
  note={ francisco@cs.cinvestav.mx, gmorales@cs.cinvestav.mx 13179 received 31 Jan 2006},
  author={Francisco Rodríguez-Henríquez and Guillermo Morales-Luna and Nazar A. Saqib and Nareli Cruz-Cortés},
  year=2006
}