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($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.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- number theoryimplementation
- 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} }