TY - JOUR
T1 - Parallel Itoh-Tsujii multiplicative inversion algorithm for a special class of trinomials
AU - Rodríguez-Henríquez, Francisco
AU - Morales-Luna, Guillermo
AU - Saqib, Nazar A.
AU - Cruz-Cortés, Nareli
PY - 2007/10
Y1 - 2007/10
N2 - In this contribution, we derive a novel parallel formulation of the standard Itoh-Tsujii algorithm for multiplicative inverse computation over the field 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(2193) after 20 clock cycles in about 0.94 μS.
AB - In this contribution, we derive a novel parallel formulation of the standard Itoh-Tsujii algorithm for multiplicative inverse computation over the field 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(2193) after 20 clock cycles in about 0.94 μS.
KW - Cryptography
KW - FPGA design
KW - Multiplicative inversion
KW - Polynomial basis
UR - http://www.scopus.com/inward/record.url?scp=34548500763&partnerID=8YFLogxK
U2 - 10.1007/s10623-007-9073-6
DO - 10.1007/s10623-007-9073-6
M3 - Artículo
SN - 0925-1022
VL - 45
SP - 19
EP - 37
JO - Designs, Codes, and Cryptography
JF - Designs, Codes, and Cryptography
IS - 1
ER -