High-performance and high-speed implementation of polynomial basis Itoh–Tsujii inversion algorithm over GF(2 m )

High-performance and high-speed implementation of polynomial basis Itoh–Tsujii inversion algorithm over GF(2 m )

For access to this article, please select a purchase option:

Buy article PDF
(plus tax if applicable)
Buy Knowledge Pack
10 articles for $120.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Your details
Why are you recommending this title?
Select reason:
IET Information Security — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

In this study high-performance and high-speed field-programmable gate array (FPGA) implementations of polynomial basis Itoh–Tsujii inversion algorithm (ITA) over GF(2 m ) constructed by irreducible trinomials and pentanomials are presented. The proposed structures are designed by one field multiplier and k -times squarer blocks or exponentiation by 2 k , where k is a small positive integer. The k -times squarer blocks have an efficient tree structure with low critical path delay, and the multiplier is based on a proposed high-speed digit-serial architecture with minimum hardware resources. Furthermore, to reduce the computation time of ITA, the critical path of the circuit is broken to finer path using several registers. The computation times of the structure on Virtex-4 FPGA family are 0.262, 0.192 and 0.271 µs for GF(2163), GF(2193) and GF(2233), respectively. The comparison results with other implementations of the polynomial basis Itoh–Tsujii inversion algorithm verify the improvement in the proposed architecture in terms of speed and performance.


    1. 1)
      • 1. Itoh, T., Tsujii, S.: ‘A fast algorithm for computing multiplicative inverses in GF(2m) using normal bases’, Inf. Comput., 1988, 78, (3), pp. 171177.
    2. 2)
      • 2. Rodrıiguez-Henrıiquez, F., Saqib, N.A., Cruz-Cortes, N.: ‘A fast implementation of multiplicative inversion over GF (2m)’. Proc. of the Int. Conf. on Information Technology: Coding and Computing (ITCC05), 2005, vol. 1, pp. 574579.
    3. 3)
      • 3. Rodrıiguez-Henrıiquez, F., Morales-Luna, G., Saqib, N.A., et al: ‘Parallel Itoh-Tsujii multiplicative inversion algorithm for a special class of trinomials’, Des. Codes Cryptogr., 2007, 45, (1), pp. 1937.
    4. 4)
      • 4. Rebeiro, C., Sinha Roy, S., Mukhopadhyay, D.: ‘Revisiting the Itoh-Tsujii inversion algorithm for FPGA platforms’, IEEE Trans. Very Large Scale Integr. (VLSI) Syst., 2011, 19, (8), pp. 15081512.
    5. 5)
      • 5. Sinha Roy, S., Rebeiro, C., Mukhopadhyay, D.: ‘Accelerating Itoh-Tsujii multiplicative inversion algorithmfor FPGAs’. Proc. of the 21st edition of the Great Lakes Symp. on Great Lakes Symp. on VLSI, 2011, pp. 6772.
    6. 6)
      • 6. Venkatasubramani, V.R., Murali, N., Rajaram, S.: ‘An improved quad Itoh-Tsujii algorithm for FPGAs’, IEICE Electron. Express, 2013, 10, (18), pp. 16.
    7. 7)
      • 7. Sinha Roy, S., Rebeiro, C., Mukhopadhyay, D.: ‘Theoretical modeling of the Itoh-Tsujii inversion algorithm for enhanced performance on k-LUT based FPGAs’. Proc. of the IEEE Conf. Design, Automation and Test (DATE), 14–18 March 2011, pp. 16.
    8. 8)
      • 8. Sinha Roy, S., Rebeiro, C., Mukhopadhyay, D.: ‘Generalized high speed Itoh-Tsujii multiplicative inversion architecture for FPGAs’, Integr. VLSI J., 2012, 45, (3), pp. 307315.
    9. 9)
      • 9. Parrilla, L., Lloris, A., Castillo, E., et al: ‘Minimum-clock-cycle Itoh-Tsujii algorithm hardware implementation for cryptography applications over GF(2m) fields’, Electron. Lett., 2012, 48, (18), pp. 11261128.
    10. 10)
      • 10. Brauer, A.: ‘on addition chains’, Bull. Amer. Math. Soc., 1939, 45, (10), pp. 736739.
    11. 11)
      • 11. Knuth, D.E.: ‘The art of computer programming’ (Addison-Wesley, Reading, MA, 1997, 3rd edn.).
    12. 12)
      • 12. Kodali, R.K., Amanchi, C.N., Kumar, S., et al: ‘FPGA implementation of Itoh-Tsujii inversion algorithm’. Proc. of the IEEE Int. Conf. on Recent Advances and Innovations in Engineering (ICRAIE-2014), May 09–11, 2014, Jaipur, India, pp. 15.
    13. 13)
      • 13. Guajardo, J., Paar, C.: ‘Itoh-Tsujii inversion in standard basis andits application in cryptography and codes’, Des. Codes Cryptogr., 2002, 25, (2), pp. 207216.
    14. 14)
      • 14. Hankerson, D., Menezes, A., Vanstone, S.: ‘Guide to elliptic curve cryptography’ (Springer, New York, 2003, 1st edn.).
    15. 15)
      • 15. Rodriguez-Henriquez, F., Saqib, N.A., Diaz-Perez, A., et al: ‘Cryptographic algorithms on reconfigurable hardware’ (Springer, New York, 2006, 1st edn.).
    16. 16)
      • 16. Deschamps, J.P., Imaña, J.L., Sutter, G.D.: ‘Hardware implementation of finite-field arithmetic’ (McGraw-Hill, New York, 2009, 1st edn.).
    17. 17)
      • 17. Cohen, H., Frey, G., Avanzi, R., et al: ‘Handbook of elliptic and hyperelliptic curve cryptography’ (CRC Press, Boca Raton, 2006, 1st edn.).
    18. 18)
      • 18. Xiong, X., Fan, H.: ‘GF(2m) bit-parallel squarer using generalized polynomial basis for new class of irreducible pentanomials’, Electron. Lett., 2014, 50, (9), pp. 655657.
    19. 19)
      • 19. Wu, H.: ‘Low complexity bit-parallel finite field arithmetic using polynomial basis’. Proc. of Cryptographic Hardware and Embedded Systems-CHES 1999, (LNCS 1717), pp. 280291.
    20. 20)
      • 20. Bosma, W., Cannon, J., Playoust, C.: ‘The magma algebra system I: The user language’, J. Symb. Comput., 1997, 24, pp. 235265.
    21. 21)
      • 21. Jia-feng, X., Jian-jun, H., Wei-hua, G.: ‘Low latency systolic multipliers for finite field GF(2m) based on irreducible polynomials’ (Central South University Press, Springer-Verlag Berlin Heidelberg, 2012), pp. 12831289.
    22. 22)
      • 22. Fan, J., Verbauwhede, I.: ‘A digit-serial architecture for inversion and multiplication in GF(2m)’. Proc. of the IEEE Workshop on Signal Processing Systems, 8–10 October 2008, Washington, DC, pp. 712.
    23. 23)
      • 23. Pan, J.S., Lee, C.Y., Kumar Meher, P.: ‘Low-latency digit-serial and digit-parallel systolic multipliers for large binary extension fields’, IEEE Trans. Circuits Syst. I Reg. Pap., 2013, 60, (12), pp. 31953204.
    24. 24)
      • 24. Kim, C.H., Kwon, S., Hong, C.P.: ‘A fast digit-serial systolic multiplier for finite field GF(2m)’. Proc. of the IEEE Conf. Destin Automation Conf. Asia and south pacific, ASP-DAC, 2005, vol. 2, pp. 12681271.
    25. 25)
      • 25. Kim, C.H., Han, S.D., Hong, C.P.: ‘Digit-serial systolic multiplier for finite field GF(2m)’. IEE Proc. on 14th Annual IEEE Int. Conf. of ASIC/SOC, 2001, pp. 361365.
    26. 26)
      • 26. Lee, T.-Y., Liu, M.-J., Fan, C.-C., et al: ‘Low complexity digit-serial multiplier over GF(2m) using Karatsuba technology’. Seventh Int. Conf. on Complex, Intelligent, and Software Intensive Systems, 2013, pp. 461466.
    27. 27)
      • 27. Kumar, S., Wollinger, T., Paar, C.: ‘Optimum digit serial GF(2m) multipliers for curve-based cryptography’, IEEE Trans. Comput., 2006, 55, (10), pp. 13061311.
    28. 28)
      • 28. Kim, C.H., Hong, C.P., Kwon, S.: ‘A digit-serial multiplier for finite field GF(2m)’, IEEE Trans. Very Large Scale Integr. (VLSI) Syst., 2005, 13, (4), pp. 476483.
    29. 29)
      • 29. Morales-Sandoval, M., Feregrino-Uribe, C., Kitsos, P.: ‘Bit-serial and digit-serial GF(2m) Montgomery multipliers using linear feedback shift registers’, IET Comput. Digit. Tech., 2011, 5, (2), pp. 8694.
    30. 30)
      • 30. Rodriguez-Henriquez, F., Koc, C.K.: ‘On fully parallel karatsuba multipliers for GF(2m)’. Proc. of the Int. Conf. on Computer Science and Technology (CST), Cancun, Mexico, 2003, pp. 405410.
    31. 31)
      • 31. Rodriguez-Henriquez, F., Saqib, N.A., Diaz-Perez, A.: ‘A fast parallel implementation of elliptic curve point multiplication over GF(2m)’, Microprocess. Microsyst., 2004, 28, (5–6), pp. 329339.
    32. 32)
      • 32. Rebeiro, C., Mukhopadhyay, D.: ‘Power attack resistant efficient FPGA architecture for Karatsuba multiplier’. Proc. of the 21st Int. Conf. on VLSI Design, IEEE Computer Society, Washington, DC, USA, 2008, pp. 706711.
    33. 33)
      • 33. Rebeiro, C., Mukhopadhyay, D.: ‘Hybrid masked Karatsuba multiplier for GF(2233)’. Proc. of the 11th IEEE VLSI Design and Test Symp., Calcutta, India, August 8–11, 2007, pp. 379387.

Related content

This is a required field
Please enter a valid email address