© The Institution of Engineering and Technology
Gaussian normal basis (GNB) of the even-type is popularly used in elliptic curve cryptosystems. Efficient GNB multipliers could be realised by Toeplitz matrix-vector decomposition to realise subquadratic space complexity architectures. In this study, Dickson polynomial representation is proposed as an alternative way to represent an GNB of characteristic two. The authors have derived a novel recursive Dickson–Karatsuba decomposition to achieve a subquadratic space-complexity parallel GNB multiplier. By theoretical analysis, it is shown that the proposed subquadratic multiplier saves about 50% bit-multiplications compared with the corresponding subquadratic GNB multiplication using Toeplitz matrix-vector product approach.
References
-
-
1)
-
22. Dickson, L.E.: ‘The analytic presentation of substitutions on a power of a prime number of letters with a discussion of the linear group’, Annals Math., 1897, 11, pp. 65–120 (doi: 10.2307/1967217).
-
2)
-
9. Lee, C.-Y., Chiou, C.W.: ‘Scalable Gaussian normal basis multipliers over GF(2m) using Hankel matrix-vector representation’, Signal Process. Syst., 2012, 69, (2), pp. 197–211 (doi: 10.1007/s11265-011-0654-2).
-
3)
-
8. Lee, C.-Y.: ‘Concurrent error detection architectures for Gaussian normal basis multiplication over GF(2m)’, Integration, 2010, 43, (1), pp. 113–123.
-
4)
-
23. Lidl, R., Mullen, G., Turnwald, G.: ‘Dickson polynomials, vol. 65 of Longman Scientific & Technical, Harlow‘, Pitman Monogr. Surv. Pure Appl. Math., 1993.
-
5)
-
3. Ash, D.W., Blake, I.F., Vanstone, S.A.: ‘Low complexity normal bases’, Discrete Appl. Math., 1989, 25, (3), pp. 191–210 (doi: 10.1016/0166-218X(89)90001-2).
-
6)
-
4. Lee, C.-Y., Chiou, C.W.: ‘Efficient design of low-complexity bit-parallel systolic Hankel multipliers to implement multiplication in normal and dual bases of GF(2m)’, IEICE Trans., 2005, 88-A, (11), pp. 3169–3179 (doi: 10.1093/ietfec/e88-a.11.3169).
-
7)
-
15. Weimerskirch, A., Paar, C.: ‘Generalizations of the Karatsuba Algorithm for Efficient Implementations’. , University of Ruhr, Bochum, Germany, 2003.
-
8)
-
5. Wang, Z., Fan, S.: ‘Efficient montgomery-based semi-systolic multiplier for even-type GNB of GF(2m)’, IEEE Trans. Comput., 2012, 61, (3), pp. 415–419 (doi: 10.1109/TC.2010.272).
-
9)
-
1. Public key cryptography for the financial services industry: the elliptic curve digital signature algorithm (ECDSA), , 1999.
-
10)
-
12. Lidl, R., Niederreiter, H.: ‘Introduction to finite fields and their applications’ (Cambridge University Press, 1997, 2nd edn.).
-
11)
-
13. Lee, C.-Y., Chen, Y.-H., Chiou, C.W., Lin, J.-M.: ‘Unified parallel systolic multiplier over GF(2m)’, J. Comput. Sci. Technol., 2007, 22, (1), pp. 28–38 (doi: 10.1007/s11390-007-9003-0).
-
12)
-
14. Karatsuba, A., Ofman, Y.: ‘Multiplication of multidigit numbers on automata’, ISoviet Physics-Doklady (English translation), 1993, 7, (7), pp. 595–596.
-
13)
-
25. Mullin, R.C., Onyszchuk, I.M., Vanstone, S.A., Wilson, R.M.: ‘Optimal normal bases in GF(2m)’, Discrete Appl. Math., 1989, 22, (2), pp. 149–161 (doi: 10.1016/0166-218X(88)90090-X).
-
14)
-
24. Massey, J., Omura, J.: ‘Computational method and apparatus for finite arithmetic’, 1986.
-
15)
-
18. Pan, J.-S., Lee, C.-Y., Meher, P.K.: ‘Low-latency digit-serial and digit-parallel systolic multipliers for large binary extension fields’, IEEE Trans. Circuits Syst., 2013, 60-I, (12), pp. 3195–3204 (doi: 10.1109/TCSI.2013.2264694).
-
16)
-
2. Digital Signature Standard (DSS), Federal Information Processing Standards Publication 186-2, 2000.
-
17)
-
6. 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’, Signal Process. Syst., 2008, 52, (3), pp. 313–324 (doi: 10.1007/s11265-008-0164-z).
-
18)
-
7. Lee, C.-Y., Meher, P.K., Patra, J.C.: ‘Concurrent error detection in bit-serial normal basis multiplication over GF(2m) using multiple parity prediction schemes’, IEEE Trans. VLSI Syst., 2010, 18, (8), pp. 1234–1238 (doi: 10.1109/TVLSI.2009.2020593).
-
19)
-
11. Gao, S., Lenstra, H.W.Jr: ‘Optimal normal bases’, Des. Codes Cryptography, 1992, 2, (4), pp. 315–323 (doi: 10.1007/BF00125200).
-
20)
-
10. Hua, Y., Lin, J.-M., Chiou, C., Lee, C.-Y., Liu, Y.: ‘Low space-complexity digit-serial dual basis systolic multiplier over Galois field GF(2m) using Hankel matrix and Karatsuba algorithm’, IET Inf. Sec., 2013, 7, (2), pp. 75–86 (doi: 10.1049/iet-ifs.2012.0227).
-
21)
-
26. Hasan, M.A., Nègre, C.: ‘Low space complexity multiplication over binary fields with Dickson polynomial representation’, IEEE Trans. Comput., 2011, 60, (4), pp. 602–607 (doi: 10.1109/TC.2010.132).
-
22)
-
17. Pan, J., Azarderakhsh, R., Kermani, M.M., et al: ‘Low-latency digit-serial systolic double basis multiplier over GF(2m) using subquadratic toeplitz matrix-vector product approach’, IEEE Trans. Comput., 2014, 63, (5), pp. 1169–1181 (doi: 10.1109/TC.2012.239).
-
23)
-
19. Park, S.-M., Hong, D., Seo, C.: ‘Subquadratic space complexity multiplier for GF(2n) using type 4 Gaussian normal bases’, ETRI Journal, 2013, 35, (3), pp. 523–529 (doi: 10.4218/etrij.13.0112.0596).
-
24)
-
21. Ozbudak, F., Akleylek, S., Cenk, M.: ‘A new representation of elements of binary fields with sub-quadratic space complexity multiplication of polynomials’, IEICE Trans., 2013, 96-A, (10), pp. 2016–2024.
-
25)
-
20. Fan, H., Hasan, M.A.: ‘Subquadratic computational complexity schemes for extended binary field multiplication using optimal normal bases’, IEEE Trans. Comput., 2007, 56, (10), pp. 1435–1437 (doi: 10.1109/TC.2007.1076).
-
26)
-
16. Fan, H., Hasan, M.: ‘A new approach to subquadratic space complexity parallel multipliers for extended binary fields’, IEEE Trans. Comput., 2007, 56, (2), pp. 224–233 (doi: 10.1109/TC.2007.19).
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cds.2014.0276
Related content
content/journals/10.1049/iet-cds.2014.0276
pub_keyword,iet_inspecKeyword,pub_concept
6
6