Parallel Itoh–Tsujii multiplicative inversion algorithm for a special class of trinomials | Designs, Codes and Cryptography Skip to main content
Log in

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

  • Published:
Designs, Codes and Cryptography Aims and scope Submit manuscript

Abstract

In this contribution, we derive a novel parallel formulation of the standard Itoh–Tsujii algorithm for multiplicative inverse computation over the field GF(2m). 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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Similar content being viewed by others

References

  • Itoh T and Tsujii S (1998). A fast algorithm for computing multiplicative inverses in GF(2m) using normal basis. Inf Comput 78: 171–177

    Article  Google Scholar 

  • Feng GL (1989). A VLSI architecture for fast inversion in GF(2m). IEEE Trans Comput 38(10): 1383–1386

    Article  Google Scholar 

  • Takagi N, Yoshiki J and Tagaki K (2001). A fast algorithm for multiplicative inversion in GF(2m) using normal basis. IEEE Trans Comput 50(5): 394–398

    Article  Google Scholar 

  • Hasan MA (2001) Efficient computation of multiplicative inverses for cryptographic applications. In: Proceedings of the 15th IEEE symposium on computer arithmetic, Vail, Colorado, USA

  • Yen S (1997). Improved normal basis inversion in GF(2m). IEE Electron Lett 33(3): 196–197

    Article  Google Scholar 

  • Gutub AA-A, Tenca AF, Savas E, Koc CK (2002) Scalable and unified hardware to compute montgomery inverse in GF(p) and GF(2n). In: Proceedings of the Cryptographic hardware and embedded systems—CHES 2002, 4th international workshop, redwood shores, vol 2523, CA, USA, pp 484–499

  • Rodríguez-Henríquez F, Saqib NA, Cruz-Cortés N (2005) A fast implementation of multiplicative inversion over GF(2m). In: Proceedings of the international symposium on information technology (ITCC 2005), vol 1, Las Vegas, Nevada, USA, pp 574–579

  • Guajardo J and Paar C (2002). Itoh–tsujii inversion in standard basis and its application in cryptography and codes. Des Codes Cryptogr 25: 207–216

    Article  MATH  Google Scholar 

  • Knuth DE (1997). The art of computer programming. Addison-Wesley, Reading, MA

    Google Scholar 

  • Rodríguez-Henríquez F, Morales-Luna G, López-Hernández J (2006) Low complexity bit-parallel square root computation over GF(2m) for all trinomials. Cryptology ePrint Archive, Report 2006/133, http://eprint.iacr.org/.

  • Wu H (2000). On complexity of squaring using polynomial basis in GF(2m). In: Stinson, STD (eds) Workshop on selected areas in cryptography (SAC 2000), vol LNCS 2012., pp 118–129. Springer, Berlin

    Google Scholar 

  • Wu H (1999) Low complexity bit-parallel finite field arithmetic using polynomial basis. in: Proceedings of the cryptographic hardware and embedded systems—CHES 1999, first international workshop. ser. Lecture notes in computer science, vol 1717. Springer, Berlin, pp 280–291

  • IEEE standards documents (2004) IEEE P1363: standard specifications for public key cryptography. Draft Version D18. IEEE, http://grouper.ieee.org/groups/1363/

  • Fong K, Hankerson D, López J and Menezes A (2004). Field inversion and point halving revisited. IEEE Trans Comput 53(8): 1047–1059

    Article  Google Scholar 

  • Fong K, Hankerson D, López J and Menezes A (2004). Field inversion and point halving revisited. IEEE Trans Comput 53(8): 1047–1059

    Article  Google Scholar 

  • Menezes AJ, Oorschot PC and Vanstone SA (1996). Handbook of applied cryptography. CRC Press, Boca Raton, FL

    Google Scholar 

  • Rodríguez-Henríquez F, Morales-Luna G, Saqib NA, Cruz-Cortés N (2007) A parallel version of the Itoh-Tsujii multiplicative inversion algorithm. In: Proceedings of International Workshop on Applied Reconfigurable Computing (ARC2007), Lecture notes in computer science, Mangaratiba, Brazil, March 2007, Vol 4419. Springer, pp. 226–237

  • Rodríguez-Henríquez F, Saqib NA and Díaz-Pérez A (2004). A fast parallel implementation of elliptic curve point multiplication over GF(2m). Elsevier J Microprocessors Microsyst 28(8): 329–339

    Article  Google Scholar 

  • Goodman J and Chandrakasan AP (2001). An energy-efficient reconfigurable public-key cryptography processor. IEEE J Solid-State Circuits 36(11): 1808–1820

    Article  Google Scholar 

  • Bednara M, Daldrup M, Shokrollahi J, Teich J, von zur Gathen J (2002) Reconfigurable implementation of elliptic curve crypto algorithms. In: Proceedings of the 9th reconfigurable architectures workshop (RAW-02), Fort Lauderdale, FL, USA

  • Lutz J (2003) High performance elliptic curve cryptographic co-processor. Master’s thesis, University of Waterloo

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Francisco Rodríguez-Henríquez.

Additional information

Communicated by P. Wild.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Rodríguez-Henríquez, F., Morales-Luna, G., Saqib, N.A. et al. Parallel Itoh–Tsujii multiplicative inversion algorithm for a special class of trinomials. Des. Codes Cryptogr. 45, 19–37 (2007). https://doi.org/10.1007/s10623-007-9073-6

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10623-007-9073-6

Keywords

AMS Classifications

Navigation