Efficient hardware structure for extended Euclidean-based inversion over

Efficient hardware structure for extended Euclidean-based inversion over

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 Computers & Digital Techniques — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

In this study, an efficient hardware structure for implementation of extended Euclidean algorithm (EEA) inversion based on a modified algorithm is presented. In the proposed algorithm, one iteration performs the operations corresponding to two iterations in previously reported EEA-based inversion algorithm. The proposed structure is implemented based on a modified algorithm with low path-delay and hardware consumption. The circuit performs one iteration of the algorithm in one clock cycle. Furthermore, to increase speed and reduce the latency of the structure, the authors applied the loop unrolling technique by replicating the body of the loop. Loop unrolling replaces a loop body by several copies of the body. The authors chose the number of copies based on the trade-off between hardware resources, critical path delay and the number of clock cycles. Therefore, the time and area parameters can be adjusted by different choices. The proposed architecture is simple, low cost and also the number of clock cycles in the structure are reduced compared to existing EEA-based works. The structure over two binary finite fields and has been successfully verified and implemented on Virtex-5 XC5VLX110 field-programmable gate array. The comparison with other previous implementations of the inversion operation verifies that the proposed method has better improvement in terms of area × time complexity.


    1. 1)
      • 1. Hankerson, D., Menezes, A., Vanstone, S.: ‘Guide to elliptic curve cryptography’ (Springer-Verlag, New York, 2003, 1st edn.).
    2. 2)
      • 2. Fournaris, A.P., Koufopavlou, O.: ‘Applying systolic multiplication-inversion architectures based on modified extended Euclidean algorithm for GF(2k) in elliptic curve cryptography’, Comput. Electr. Eng., 2007, 33, (5), pp. 333348.
    3. 3)
      • 3. Kim, S., Chang, N.S., Kim, C.H., et al: ‘A fast inversion algorithm and low-complexity architecture over GF(2m)’. Proc. Int. Conf. on Computational Intelligence and Security, Xi,an, China, 2005 (LNCS, 3802), pp. 18.
    4. 4)
      • 4. Yan, Z.: ‘Digit-Serial systolic architectures for inversions over GF(2m)’. Proc. IEEE Workshop on Signal Processing Systems Design and Implementation, Banff, Alberta, Canada, 2006, pp. 7782.
    5. 5)
      • 5. Ibrahim, A., Gebali, F.: ‘Scalable and unified digit-serial processor array architecture for multiplication and inversion over GF(2m)’, IEEE Trans. Circuits Syst. I, Regul. Pap., 2017, pp, (99), pp. 113.
    6. 6)
      • 6. Ibrahim, A., Alsomani, T., Gebali, F.: ‘Unified systolic array architecture for finite field multiplication and inversion’, Comput. Electr. Eng., 2017, 61, pp. 104115.
    7. 7)
      • 7. Guo, J.-H., Wang, C.-L.: ‘Bit-serial systolic array implementation of Euclid's algorithm for inversion arid division in GF(2m)’. Proc. Int. Symp. on VLSI Technology Systems and Applications, Taipei, Taiwain, 1997, pp. 113117.
    8. 8)
      • 8. Yan, Z., Sarwate, D.V., Liu, Z.: ‘Hardware-efficient systolic architectures for inversion in GF(2m)’, IEE Proc. Inf. Secur., 2005, 152, (1), pp. 3145.
    9. 9)
      • 9. Lee, C.-Y., Chiou, C.-W.: ‘New bit-parallel systolic architectures for computing multiplication, multiplicative inversion and division in GF(2m) under polynomial basis and normal basis representations’, J. Signal Process. Syst., 2008, 52, pp. 313324.
    10. 10)
      • 10. Fan, J., Verbauwhede, I.: ‘A digit-serial architecture for inversion and multiplication in GF(2m)’. Proc. IEEE Workshop on Signal Processing Systems, Washington DC, USA, 2008, pp. 712.
    11. 11)
      • 11. Yan, Z., Sarwate, D.V.: ‘Reduced-complexity pipelined architectures for finite field inversions’. Proc. IEEE Workshop on Signal Processing Systems Design and Implementation, Banff, Alberta, Canada, 2006, pp. 5661.
    12. 12)
      • 12. Ibrahim, A., Alsomani, T., Gebali, F.: ‘New systolic array architecture for finite field inversion’, Can. J. Electr. Comput. Eng., 2017, 40, (1), pp. 2330.
    13. 13)
      • 13. Yan, Z., Sarwate, D.V., Liu, Z.: ‘High-speed systolic architectures for finite field inversion’, Integr. VLSI J., 2005, 38, (3), pp. 383398.
    14. 14)
      • 14. Rashidi, B., Rezaeian Farashahi, R., Sayedi, S.M.: ‘High-performance and high-speed implementation of polynomial basis Itoh-Tsujii inversion algorithm over GF(2m)’, IET Inf. Secur., 2016, 11, (2), pp. 6677.
    15. 15)
      • 15. 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.
    16. 16)
      • 16. Venkatasubramani, V.R., Murali, N., Rajaram, S.: ‘An improved quad Itoh-Tsujii algorithm for FPGAs’, IEICE Electron. Express, 2013, 10, (18), pp. 16.
    17. 17)
      • 17. 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.
    18. 18)
      • 18. Rashidi, B.: ‘High-speed hardware implementation of Gaussian normal basis inversion algorithm over F2m’, Microelectron. J., 2017, 63, pp. 138147.
    19. 19)
      • 19. Jarvinen, P., Dimitrov, S., Azarderakhsh, R.: ‘A generalization of addition chains and fast inversions in binary fields’, IEEE Trans. Comput., 2015, 64, (9), pp. 24212432.
    20. 20)
      • 20. Hu, J., Wei, W.G.J., Cheung, R.: ‘Fast and generic inversion architectures over GF(2m) using modified Itoh-Tsujii algorithms’, IEEE Trans. Circuits Syst. II, Express Briefs, 2015, 62, (4), pp. 367371.
    21. 21)
      • 21. Guo, J.-H., Wang, C.-L.: ‘Hardware-efficient systolic architecture for inversion and division in GF(2m)’, IEE Proc., Comput. Digit. Tech., 1998, 145, (8), pp. 272278.
    22. 22)
      • 22. Brunner, H., Curiger, A., Hofstetter, M.: ‘On computing multiplicative inverses in GF(2m)’, IEEE Trans. Comput., 1993, 42, pp. 10101015.
    23. 23)
      • 23. Knuth, D.E.: ‘The art of computer programming’, vol. 2, (Addison-Wesley, Boston, MA, USA, 1981).
    24. 24)
      • 24. Fingeroff, M.: ‘High-level synthesis: blue book’ (Xlibris Corporation, Bloomington, IN, USA, 2010, 1st edn.).
    25. 25)
      • 25. U.S. Department of Commerce: ‘National institute of standards and technology, digital signature standard (DSS)’, Federal Information Processings Standards Publication 186-2, January 2000.
    26. 26)
      • 26. Bosma, W., Cannon, J., Playoust, C.: ‘The Magma algebra system I: the user language’, J. Symb. Comput., 1997, 24, pp. 235265.

Related content

This is a required field
Please enter a valid email address