Scalable and systolic Montgomery multiplier over GF(2m) generated by trinomials
Scalable and systolic Montgomery multiplier over GF(2m) 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.
Thank you
Your recommendation has been sent to your librarian.
- Author(s): C.-Y. Lee 1 ; C.W. Chiou 2 ; J.-M. Lin 3 ; C.-C. Chang 3
-
-
View affiliations
-
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
-
Affiliations:
1: Department of Computer Information and Network Engineering, Lunghwa University of Science and Technology, 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
A Montgomery's algorithm in GF(2m) 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.
Inspec keywords: computational complexity; VLSI; Hankel matrices; Galois fields; systolic arrays; multiplying circuits
Other keywords:
Subjects: Algebra; Microprocessor chips; Logic circuits; Microprocessors and microcomputers; Logic and switching circuits
References
-
-
1)
- ‘M74HC08, Quad 2-Input AND Gate’, STMicroelectronics 2001, http://www.st.com/stonline/books/pdf/docs/1885.pdf.
-
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)
- P.L. Montgomery . Modular multiplication without trial division. Math. Comput. , 519 - 521
-
4)
- Mentens, N., Ő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)
- N.-Y. Kim , K.-Y. Yoo . Digit-serial AB2 systolic architecture in GF(2m). IEE Proc., Circuits Devices Syst. , 6 , 608 - 614
-
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)
- 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)
- C.Y. Lee . Low complexity bit-parallel systolic multiplier over GF(2m) using irreducible trinomials. IEE Proc., Comput. Digit. Tech. , 1 , 39 - 42
-
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)
- ‘M74HC86, Quad exclusive OR gate’, STMicroelectronics 2001http://www.st.com/stonline/books/pdf/docs/2006.pdf.
-
11)
- R. Lidl , H. Niederreiter . (1997) Finite fields.
-
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)
- R. Lidl , H. Niederreiter . (1994) Introduction to finite fields and their applications.
-
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)
- O. Nibouche , A. Bouridane , M. Nibouche . Architectures for Montgomery's multiplication. IEE Proc., Comput. Digit. Tech. , 6 , 361 - 368
-
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)
- 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)
- 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)
- 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)
- C.-L. Wang , J.-L. Lin . Systolic array implementation of multipliers for finite fields GF(2m). IEEE Trans. Circuits Syst. , 7 , 796 - 800
-
21)
- `Digital signature standard', FIPS Publication 186-2, January 2000.
-
22)
- B.B. Zhou . A new bit-serial systolic multiplier over GF(2m). IEEE Trans. Comput. , 6 , 749 - 751
-
23)
- Savas, E., Tenca, A.F., Koç, Ç.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)
- Ç.K. Koç , T. Acar . Montgomery multiplication in GF(2k). Des. Codes Cryptogr. , 57 - 69
-
25)
- M74HC279, Quad S̄-R̄ Latch’, STMicroelectronics 2001http://www.st.com/stonline/books/pdf/docs/1937.pdf.
-
26)
- B. Sunar , C.K. Koc . Mastrovito multiplier for all trinomials. IEEE Trans. Comput. , 5 , 522 - 527
-
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)
- S.M. Kang , Y. Leblebici . (1999) CMOS digital integrated circuits-analysis and design.
-
29)
- H. Wu . Montgomery multiplier and squarer for a class of finite fields. IEEE Trans. Comput. , 5 , 521 - 529
-
30)
- N. Weste , K. Eshraghian . (1985) Principles of CMOS VLSI design, a system perspective.
-
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)
- S.Y. Kung . (1988) VLSI array processors.
-
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)
- 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)
- M74HC257, Quad 2 Channel Multiplexer (3-State), STMicroelectronics 2001http://www.st.com/stonline/books/pdf/docs/1932.pdf.
-
1)