Scalable and systolic Montgomery multiplier over GF(2m) generated by trinomials

C.-Y. Lee; C.W. Chiou; J.-M. Lin; C.-C. Chang

Scalable and systolic Montgomery multiplier over GF(2^m) generated by trinomials

Access Full Text

Scalable and systolic Montgomery multiplier over GF(2^m) generated by trinomials

Author(s): C.-Y. Lee ; C.W. Chiou ; J.-M. Lin ; C.-C. Chang
DOI: 10.1049/iet-cds:20060314

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

Buy article PDF

Buy Knowledge Pack

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

IET Circuits, Devices & Systems — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

Author(s): C.-Y. Lee ¹ ; C.W. Chiou ² ; J.-M. Lin ³ ; C.-C. Chang ³
- Affiliations: 1: Department of Computer Information and Network Engineering, Lunghwa University of Science and Technology, Taiwan, Republic of China
  2: Department of Computer Science and Information Engineering, Ching Yun University, Chung-Li, Taiwan, Republic of China
  3: Department of Information Engineering and Computer Science, Feng Chia University, Taichung City, Taiwan, Republic of China
Source: Volume 1, Issue 6, December 2007, p. 477 – 484
DOI: 10.1049/iet-cds:20060314 , Print ISSN 1751-858X, Online ISSN 1751-8598

Published

A Montgomery's algorithm in GF(2^m) based on the Hankel matrix–vector representation is proposed. The hardware architecture obtained from this algorithm indicates low-complexity bit-parallel systolic multipliers with irreducible trinomials. The results reveal that the proposed multiplier saves approximately 36% of space complexity as compared to an existing systolic Montgomery multiplier for trinomials. A scalable and systolic Montgomery multiplier is also developed by applying the block-Hankel matrix–vector representation. The proposed scalable systolic architecture is demonstrated to have significantly less time–area product complexity than existing digit-serial systolic architectures. Furthermore, the proposed architectures have regularity, modularity and local interconnectability, making them highly appropriate for VLSI implementation.

References

1. 1)
  - ‘M74HC08, Quad 2-Input AND Gate’, STMicroelectronics 2001, http://www.st.com/stonline/books/pdf/docs/1885.pdf.
2. 2)
  - S.T.J. Fenn , D. Taylor , M. Benaissa . A dual basis bit-serial systolic multiplier for GF(2m). Integr. VLSI J , 139 - 149
3. 3)
  - P.L. Montgomery . Modular multiplication without trial division. Math. Comput. , 519 - 521
4. 4)
  - Mentens, N., Őrs, S.B., Preneel, B.: `An FPGA implementation of an elliptic curve processor over GF(2', Proc. 2004 Great Lakes Symp. on VLSI (GLSVLSI 2004), 2004, p. 454–457.
5. 5)
  - N.-Y. Kim , K.-Y. Yoo . Digit-serial AB2 systolic architecture in GF(2m). IEE Proc., Circuits Devices Syst. , 6 , 608 - 614
6. 6)
  - C.Y. Lee , E.H. Lu , J.Y. Lee . Bit-parallel systolic multipliers for GF(2m) fields defined by all-one and equally-spaced polynomials. IEEE Trans. Comput. , 5 , 385 - 393
7. 7)
  - C. Paar , P. Fleischmann , P. Soria-Rodriguez . Fast arithmetic for public-key algorithms in Galois fields with composite exponents. IEEE Trans. Comput. , 10 , 1025 - 1034
8. 8)
  - C.Y. Lee . Low complexity bit-parallel systolic multiplier over GF(2m) using irreducible trinomials. IEE Proc., Comput. Digit. Tech. , 1 , 39 - 42
9. 9)
  - Gutub, A.A.-A., Tenca, A.F., Savas, E., Koc, C.K.: `Scalable and unified hardware to compute Montgomery inverse in GF(', Cryptographic hardware and embedded systems – CHES 2002, 2002, LNCS, 2523.
10. 10)
  - ‘M74HC86, Quad exclusive OR gate’, STMicroelectronics 2001http://www.st.com/stonline/books/pdf/docs/2006.pdf.
11. 11)
  - R. Lidl , H. Niederreiter . (1997) Finite fields.
12. 12)
  - C.W. Chiou , C.Y. Lee , A.W. Deng , J.M. Lin . Concurrent error detection in Montgomery multiplication over GF(2m). IEICE Trans. Fundam. , 2 , 566 - 574
13. 13)
  - R. Lidl , H. Niederreiter . (1994) Introduction to finite fields and their applications.
14. 14)
  - C.Y. Lee , E.H. Lu , L.F. Sun . Low-complexity bit-parallel systolic architecture for computing AB2+C in a class of finite field GF(2m). IEEE Trans. Circuits Syst. II , 5 , 519 - 523
15. 15)
  - O. Nibouche , A. Bouridane , M. Nibouche . Architectures for Montgomery's multiplication. IEE Proc., Comput. Digit. Tech. , 6 , 361 - 368
16. 16)
  - C. Lee , J. Horng , I. Jou , E. Lu . Low-complexity bit parallel systolic Montgomery multipliers for special classes of GF(2m). Trans. Comput. , 9 , 1061 - 1070
17. 17)
  - Kwon, S., Kim, C.H., Hong, C.P.: `Unidirectional two dimensional systolic array for multiplication in GF(2', 6thInt. Workshop on Fuzzy Logic and Applications, WILF 2005, 2006, LNCS, 3849, p. 420–426.
18. 18)
  - C.Y. Lee , C.W. Chiou , J.M. Lin . Concurrent error detection in a bit-parallel systolic multiplier for dual basis of GF(2m). J. Electron. Test Theory Appl. , 5 , 539 - 549
19. 19)
  - N.Y. Kim , H.S. Kim , K.Y. Yoo . Computation of AB2 multiplication in GF(2m) using low-complexity systolic architecture. IEE Proc., Circuits Devices Syst. , 2 , 119 - 123
20. 20)
  - C.-L. Wang , J.-L. Lin . Systolic array implementation of multipliers for finite fields GF(2m). IEEE Trans. Circuits Syst. , 7 , 796 - 800
21. 21)
  - `Digital signature standard', FIPS Publication 186-2, January 2000.
22. 22)
  - B.B. Zhou . A new bit-serial systolic multiplier over GF(2m). IEEE Trans. Comput. , 6 , 749 - 751
23. 23)
  - Savas, E., Tenca, A.F., Koç, Ç.K.: `A scalable and unified multiplier architecture for finite fields GF(', Cryptographic hardware and embedded systems – CHES 2000, 2000, LNCS, 1965, p. 281–296.
24. 24)
  - Ç.K. Koç , T. Acar . Montgomery multiplication in GF(2k). Des. Codes Cryptogr. , 57 - 69
25. 25)
  - M74HC279, Quad S̄-R̄ Latch’, STMicroelectronics 2001http://www.st.com/stonline/books/pdf/docs/1937.pdf.
26. 26)
  - B. Sunar , C.K. Koc . Mastrovito multiplier for all trinomials. IEEE Trans. Comput. , 5 , 522 - 527
27. 27)
  - C.Y. Lee , C.W. Chiou . Design of low-complexity bit-parallel systolic Hankel multipliers to implement multiplication in normal and dual bases of GF(2m). IEICE Trans. Fundam. , 11 , 3169 - 3179
28. 28)
  - S.M. Kang , Y. Leblebici . (1999) CMOS digital integrated circuits-analysis and design.
29. 29)
  - H. Wu . Montgomery multiplier and squarer for a class of finite fields. IEEE Trans. Comput. , 5 , 521 - 529
30. 30)
  - N. Weste , K. Eshraghian . (1985) Principles of CMOS VLSI design, a system perspective.
31. 31)
  - J.H. Guo , C.L. Wang . Digit-serial systolic multiplier for finite fields GF(2m). IEE Proc., Comput. Digit. Tech. , 2 , 143 - 148
32. 32)
  - S.Y. Kung . (1988) VLSI array processors.
33. 33)
  - C.H. Kim , C.P. Hong , S. Kwon . A digit-serial multiplier for finite field GF(2m). IEEE Trans. VLSI , 4 , 476 - 483
34. 34)
  - C.W. Chiou , C.Y. Lee , A.W. Deng , J.M. Lin . Efficient VLSI implementation for Montgomery multiplication in GF(2m). Tamkang J. Sci. Eng. , 4 , 365 - 372
35. 35)
  - M74HC257, Quad 2 Channel Multiplexer (3-State), STMicroelectronics 2001http://www.st.com/stonline/books/pdf/docs/1932.pdf.

Login

Not registered yet?

Share

Tools

Login to add to favourites

Key

Scalable and systolic Montgomery multiplier over GF(2^m) generated by trinomials

Scalable and systolic Montgomery multiplier over GF(2^m) generated by trinomials

Buy article PDF

Buy Knowledge Pack

Thank you

References

Related content