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

Francisco Rodríguez-Henríquez; Guillermo Morales-Luna; Nazar A.  Saqib; Nareli Cruz-Cortés

Paper 2006/035

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

Francisco Rodríguez-Henríquez, Guillermo Morales-Luna, Nazar A. Saqib, and Nareli Cruz-Cortés

Abstract

In this contribution, we derive a novel parallel formulation of the standard Itoh-Tsujii algorithm for multiplicative inverse computation over GF(). 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, , with and 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() after 20 clock cycles in about S.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Published elsewhere. Unknown where it was published
Keywords: number theory implementation
Contact author(s): francisco @ cs cinvestav mx
gmorales @ cs cinvestav mx
History: 2006-02-06: received
Short URL: https://ia.cr/2006/035
License: CC BY

BibTeX

@misc{cryptoeprint:2006/035,
      author = {Francisco Rodríguez-Henríquez and Guillermo Morales-Luna and Nazar A.  Saqib and Nareli Cruz-Cortés},
      title = {Parallel Itoh-Tsujii Multiplicative Inversion Algorithm for a Special Class of Trinomials},
      howpublished = {Cryptology {ePrint} Archive, Paper 2006/035},
      year = {2006},
      url = {https://eprint.iacr.org/2006/035}
}