×

A survey of some recent bit-parallel \(\mathrm{GF}(2^n)\) multipliers. (English) Zbl 1372.94426

Summary: This paper surveys bit-parallel multipliers for finite field \(\mathrm{GF}(2^n)\) according to (i) quadratic and subquadratic arithmetic complexities of the underlying algorithms, (ii) various bases used for representing the field elements, and (iii) design approaches that rely on polynomial and matrix operations. Techniques for constructing space- and time-efficient multipliers are reviewed, and complexities of recent quadratic and subquadratic multipliers are summarized. For quadratic multipliers, the emphasis is placed on polynomial bases and their generalization. Low-degree Karatsuba-Toom formulae and their multiplication complexities are considered primarily for the subquadratic multipliers.

MSC:

94A60 Cryptography
11T06 Polynomials over finite fields
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
11Y16 Number-theoretic algorithms; complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Mullen, G. L.; Panario, D., Handbook of Finite Fields (2013), CRC Press · Zbl 1319.11001
[2] Menezes, A. J.; van Oorschot, P. C.; Vanstone, S. A., Handbook of Applied Cryptography (1997), CRC Press · Zbl 0868.94001
[3] Hankerson, D.; Vanstone, S.; Menezes, A. J., Guide to Elliptic Curve Cryptography (2004), Springer · Zbl 1059.94016
[4] Rodríguez-Henríquez, F.; Saqib, N. A.; Díaz-Pèrez, A.; Koç, Ç. K., Cryptographic Algorithms on Reconfigurable Hardware (2006), Springer
[5] Koç, Ç. K., Cryptographic Engineering (2009), Springer
[6] Gashkov, S. B.; Sergeev, I. S., Bit-Parallel Circuits for Arithmetic in Finite Fields (2008) · Zbl 1197.94231
[7] Elia, M.; Leone, M., On the inherent space complexity of fast parallel multipliers for \(GF(2^m)\), IEEE Trans. Comput., 51, 346-351 (2002) · Zbl 1391.94911
[8] von zur Gathen, J.; Gerhard, J., Modern Computer Algebra (2003), Cambridge Univ. Press · Zbl 1055.68168
[9] Elia, M.; Leone, M.; Visentin, C., Low complexity bit-parallel multipliers for \(GF(2^m)\) with generator polynomial \(x^m + x^k + 1\), IEE Electron. Lett., 35, 551-552 (1999)
[10] Leone, M., A new low complexity parallel multiplier for a class of finite fields, (Proc. Cryptographic Hardware and Embedded Systems. Proc. Cryptographic Hardware and Embedded Systems, CHES 2001. Proc. Cryptographic Hardware and Embedded Systems. Proc. Cryptographic Hardware and Embedded Systems, CHES 2001, Lect. Notes Comput. Sci., vol. 2162 (2001)), 160-170 · Zbl 1012.94541
[11] Grabbe, C.; Bednara, M.; Shokrollahi, J.; Teich, J.; von zur Gathen, J., FPGA designs of parallel high performance \(GF(2^{233})\) multipliers, (Proc. Int. Symposium on Circuits and Systems, vol. II. Proc. Int. Symposium on Circuits and Systems, vol. II, ISCAS 2003 (2003)), 268-271
[12] Rodríguez-Henríquez, F.; Koç, Ç. K., On fully parallel Karatsuba multipliers for \(GF(2^m)\), (Proc. Int. Conf. Computer Science and Technology. Proc. Int. Conf. Computer Science and Technology, CST 2003 (2003), ACTA Press), 405-410
[13] von zur Gathen, J.; Shokrollahi, J., Efficient FPGA-based Karatsuba multipliers for polynomials over \(F_2\), (Proc. 12th Workshop on Selected Areas in Cryptography. Proc. 12th Workshop on Selected Areas in Cryptography, SAC 2005 (2006), Springer), 359-369 · Zbl 1151.94594
[14] Zhou, G.; Michalik, H.; Hinsenkamp, L., Complexity analysis and efficient implementations of bit parallel finite field multipliers based on Karatsuba-Ofman algorithm on FPGAs, IEEE Trans. Very Large Scale Integr. (VLSI) Syst., 18, 1057-1066 (2010)
[15] Ghosh, S.; Roychowdhury, D.; Das, A., High speed cryptoprocessor for \(\eta_T\) pairing on 128-bit secure supersingular elliptic curves over characteristic two fields, (Proc. CHES 2011. Proc. CHES 2011, Lect. Notes Comput. Sci., vol. 6917 (2011)), 442-458 · Zbl 1285.94063
[16] Adikari, J.; Hasan, M. A.; Negre, C., Towards faster and greener cryptoprocessor for Eta pairing on supersingular elliptic curve over \(F_{2^{1223}}\), (Proc. 19th Workshop on Selected Areas in Cryptography. Proc. 19th Workshop on Selected Areas in Cryptography, SAC 2012 (2013)), 166-183 · Zbl 1327.94024
[17] Elia, M.; Leone, M., A basis-independent algorithm to design fast parallel multipliers over \(GF(2^m)\), (Proc. International Conference on Information Technology: Coding and Computing. Proc. International Conference on Information Technology: Coding and Computing, ITCC04 (2004)), 553-559
[18] Hasan, M. A.; Bhargava, V. K., Modular construction of low complexity parallel multipliers for a class of finite fields \(GF(2^m)\), IEEE Trans. Comput., 41, 962-971 (1992) · Zbl 1397.65332
[19] Reyhani-Masoleh, A.; Hasan, M. A., Low complexity bit parallel architectures for polynomial basis multiplication over \(GF(2^m)\), IEEE Trans. Comput., 53, 945-959 (2004)
[20] Morii, M.; Kasahara, M.; Whiting, D., Efficient bit-serial multiplication and the discrete-time Wiener-Hopf equation over finite fields, IEEE Trans. Inf. Theory, 35, 1177-1184 (1989) · Zbl 0694.94024
[21] Hasan, M. A.; Bhargava, V. K., Division and bit-serial multiplication over \(GF(q^m)\), IEE Proc., Comput. Digit. Tech., 139, 230-236 (1992)
[22] Furness, R.; Fenn, S. T.J.; Benaissa, M., \(GF(2^m)\) multiplication over triangular basis for design of Reed-Solomon codes, IEE Proc., Comput. Digit. Tech., 145, 437-443 (1998)
[23] Rodríguez-Henríquez, F.; Koç, Ç. K., Parallel multipliers based on special irreducible pentanomials, IEEE Trans. Comput., 52, 1535-1542 (2003) · Zbl 1192.11080
[24] Fan, H.; Hasan, M. A., Fast bit parallel-shifted polynomial basis multipliers in \(GF(2^n)\), IEEE Trans. Circuits Syst. I, Regul. Pap., 53, 2606-2615 (2006) · Zbl 1374.11091
[25] Cilardo, A., Fast parallel \(GF(2^m)\) polynomial multiplication for all degrees, IEEE Trans. Comput., 62, 929-943 (2013) · Zbl 1365.65300
[26] Zhang, T.; Parhi, K. K., Systematic design of original and modified Mastrovito multipliers for general irreducible polynomials, IEEE Trans. Comput., 50, 734-748 (2001) · Zbl 1396.65178
[27] Song, L.; Parhi, K. K., Low complexity modified Mastrovito multipliers over finite fields \(GF(2^m)\), (Proc. IEEE International Symposium on Circuits and Systems, vol. 1 (1999)), 508-512
[28] Fan, H.; Dai, Y., The key function of normal basis multipliers in \(GF(2^n)\), IEE Electron. Lett., 38, 1431-1432 (2002)
[29] Scott, M., Optimal irreducible polynomials for \(GF(2^m)\) arithmetic (2007), IACR Cryptology ePrint Archive, Report 2007/192
[30] Ahmadi, O.; Menezes, A., Irreducible polynomials of maximum weight, Util. Math., 72, 111-123 (2007) · Zbl 1127.11078
[31] Wu, H., A new finite field multiplier using redundant representation, IEEE Trans. Comput., 57, 1023-1031 (2008) · Zbl 1390.65199
[32] Lee, C.-Y.; Meher, P. K., Efficient bit-parallel multipliers over finite fields \(GF(2^m)\), Comput. Electr. Eng., 36, 955-968 (2010) · Zbl 1215.68278
[33] Wu, H., Bit-parallel finite field multiplier and squarer using polynomial basis, IEEE Trans. Comput., 51, 750-758 (2002) · Zbl 1391.94814
[34] von zur Gathen, J.; Nöecker, M., Exponentiation in finite fields: theory and practice, (Proc. Applicable Algebra in Eng., Comm., and Computing. Proc. Applicable Algebra in Eng., Comm., and Computing, AAECC-12 (1997)), 88-113 · Zbl 1039.11515
[35] Afanasyev, V.; Gehrmann, C.; Smeets, B., Fast message authentication using efficient polynomial evaluation, (Proc. Fast Software Encryption Workshop (1997)), 109-204 · Zbl 1385.94081
[36] Fenn, S. T.J.; Benaissa, M.; Taylor, D., \(GF(2^m)\) multiplication and division over the dual basis, IEEE Trans. Comput., 45, 319-327 (1996) · Zbl 1055.68500
[37] Sunar, B.; Koç, Ç. K., Mastrovito multiplier for all trinomials, IEEE Trans. Comput., 48, 522-527 (1999) · Zbl 1231.68043
[38] Halbutogullari, A.; Koç, Ç. K., Mastrovito multiplier for general irreducible polynomials, IEEE Trans. Comput., 49, 503-518 (2000) · Zbl 1391.94757
[39] Montgomery, P. L., Modular multiplication without trial division, Math. Comput., 44, 519-521 (1985) · Zbl 0559.10006
[40] Brent, R. P.; Zimmermann, P., Modern Computer Arithmetic (2010), Cambridge Univ. Press
[41] Koç, Ç. K.; Acar, T., Montgomery multiplication in \(GF(2^k)\), Des. Codes Cryptogr., 14, 57-69 (1998) · Zbl 0887.11054
[42] Fan, H.; Sun, J.; Gu, M.; Lam, K., Obtaining more Karatsuba-like formulae over the binary field, IET Inf. Secur., 6, 14-19 (2012)
[43] Fan, H.; Hasan, M. A., Relationship between \(GF(2^m)\) Montgomery and shifted polynomial basis multiplication algorithms, IEEE Trans. Comput., 55, 1202-1206 (2006)
[44] Cilardo, A.; Mazzeo, A.; Mazzocca, N., Representation of elements in \(F_{2^m}\) enabling unified field arithmetic for elliptic curve cryptography, IEE Electron. Lett., 41, 798-800 (2005)
[45] Wu, H., Montgomery multiplier and squarer for a class of finite fields, IEEE Trans. Comput., 51, 521-529 (2002) · Zbl 1391.94815
[46] Hariri, A.; Reyhani-Masoleh, A., Bit-serial and bit-parallel Montgomery multiplication and squaring over \(GF(2^m)\), IEEE Trans. Comput., 58, 1332-1345 (2009) · Zbl 1367.94315
[47] Fan, H.; Dai, Y., Fast bit-parallel \(GF(2^n)\) multiplier for all trinomials, IEEE Trans. Comput., 54, 485-490 (2005)
[48] Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley Publishing Company · Zbl 0326.68005
[49] Park, S. M.; Chang, K. Y.; Hong, D., Efficient bit-parallel multiplier for irreducible pentanomials using a shifted polynomial basis, IEEE Trans. Comput., 55, 1211-1215 (2006)
[50] Cilardo, A., Efficient bit-parallel \(GF(2^m)\) multiplier for a large class of irreducible pentanomials, IEEE Trans. Comput., 58, 1001-1008 (2009) · Zbl 1367.65252
[51] Hasan, M. A.; Bhargava, V. K., Bit-serial systolic divider and multiplier for finite fields \(GF(2^m)\), IEEE Trans. Comput., 41, 972-980 (1992) · Zbl 1397.65331
[52] Mastrovito, E., VLSI designs for multiplication over finite fields \(GF(2^m)\), (Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (1989)), 297-309 · Zbl 0673.94024
[53] Lee, S. O.; Jung, S. W.; Kim, C. H.; Yoon, J.; Koh, J.; Kim, D., Design of bit parallel multiplier with lower time complexity, (Proc. ICICS’ 2003. Proc. ICICS’ 2003, Lect. Notes Comput. Sci., vol. 2971 (2004)), 127-139 · Zbl 1092.68505
[54] Negre, C., Efficient parallel multiplier in shifted polynomial basis, J. Syst. Archit., 53, 109-116 (2007)
[55] Wu, H.; Hasan, M. A.; Blake, I. F., New low-complexity bit-parallel finite field multipliers using weakly dual bases, IEEE Trans. Comput., 47, 1223-1234 (1998) · Zbl 1391.94816
[56] Petra, N.; Caro, D. D.; Strollo, A. G., A novel architecture for Galois fields \(GF(2^m)\) multipliers based on Mastrovito scheme, IEEE Trans. Comput., 56, 1470-1483 (2007) · Zbl 1390.68042
[57] Berlekamp, E. R., Bit-serial Reed-Solomon encoders, IEEE Trans. Inf. Theory, 28, 869-874 (1982) · Zbl 0492.94016
[58] Fenn, S. T.J.; Benaissa, M.; Taylor, D., Bit-serial Berlekamp-like multipliers for \(GF(2^m)\), IEE Electron. Lett., 31, 1893-1894 (1995)
[59] Gollmann, D., Dual bases and bit-serial multiplication in \(F_{q^n}\), Theor. Comput. Sci., 226, 45-59 (1999) · Zbl 1098.94608
[60] Wang, M. Z.; Blake, I. F., Bit serial multiplication in finite fields, SIAM J. Discrete Math., 3, 140-148 (1990) · Zbl 0696.12014
[61] Stinson, D. R., On bit-serial multiplication and dual bases in \(GF(2^m)\), IEEE Trans. Inf. Theory, 37, 1733-1736 (1991) · Zbl 0742.94011
[62] Jungnickel, D., Finite Fields: Structure and Arithmetics (1993), Mannheim · Zbl 0779.11058
[63] Fenn, S. T.J.; Benaissa, M.; Taylor, D., Division in \(GF(2^m)\), IEE Electron. Lett., 28, 2259-2261 (1992)
[64] Park, S. M.; Chang, K. Y., Fast bit-parallel shifted polynomial basis multiplier using weakly dual basis over \(GF(2^m)\), IEEE Trans. Very Large Scale Integr. (VLSI) Syst., 19, 2317-2321 (2011)
[65] Hasan, M. A.; Bhargava, V. K., Architecture for low complexity rate-adaptive Reed-Solomon encoder, IEEE Trans. Comput., 44, 938-942 (1995) · Zbl 1057.68528
[66] Beth, T.; Cook, B. M.; Gollmann, D., Architectures for exponentiation in \(GF(2^n)\), (Proc. CRYPTO’86 (1987)), 302-310 · Zbl 0637.94016
[67] Park, S. M.; Chang, K. Y., Low complexity bit-parallel squarer for \(GF(2^n)\) defined by irreducible trinomials, IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 89-A, 2451-2452 (2006)
[68] Park, S. M., Explicit formulae of polynomial basis squarer for pentanomials using weakly dual basis, Integr. VLSI J., 45, 205-210 (2012)
[69] Xiong, X.; Fan, H., \(GF(2^n)\) bit-parallel squarer using generalized polynomial basis for new class of irreducible pentanomials, IEE Electron. Lett., 50, 655-657 (2014)
[70] Canright, D., A very compact S-box for AES, (Proc. Cryptographic Hardware and Embedded Systems. Proc. Cryptographic Hardware and Embedded Systems, Lect. Notes Comput. Sci., vol. 3659 (2005)), 441-455 · Zbl 1319.94054
[71] Mozaffari-Kermani, M.; Reyhani-Masoleh, A., Efficient and high-performance parallel hardware architectures for the AES-GCM, IEEE Trans. Comput., 61, 1165-1178 (2012) · Zbl 1365.94449
[72] Namin, A. H.; Wu, H.; Ahmadi, M., High-speed architectures for multiplication using reordered normal basis, IEEE Trans. Comput., 61, 164-172 (2012) · Zbl 1365.65314
[73] Reyhani-Masoleh, A.; Hasan, M. A., A new construction of Massey-Omura parallel multiplier over \(GF(2^m)\), IEEE Trans. Comput., 51, 511-520 (2002) · Zbl 1231.68041
[74] Mullin, R.; Onyszchuk, I.; Vanstone, S.; Wilson, R., Optimal normal bases in \(GF(p^n)\), Discrete Appl. Math., 22, 149-161 (1988/1989) · Zbl 0661.12007
[75] Azarderakhsh, R.; Reyhani-Masoleh, A., A modified low complexity digit-level Gaussian normal basis multiplier, (Proc. Third Int. Workshop Arithmetic of Finite Fields. Proc. Third Int. Workshop Arithmetic of Finite Fields, WAIFI 2010. Proc. Third Int. Workshop Arithmetic of Finite Fields. Proc. Third Int. Workshop Arithmetic of Finite Fields, WAIFI 2010, Lect. Notes Comput. Sci., vol. 6087 (2010)), 25-40 · Zbl 1231.68033
[76] Azarderakhsh, R.; Reyhani-Masoleh, A., Low-complexity multiplier architectures for single and hybrid-double multiplications in Gaussian normal bases, IEEE Trans. Comput., 62, 744-757 (2013) · Zbl 1365.65298
[77] Gao, S.; Gathen, J.; Panario, D., Gauss periods: orders and cryptographical applications, Math. Comput., 67, 343-352 (1998) · Zbl 1036.11530
[78] Fan, H.; Dai, Y., Normal basis multiplication algorithm for \(GF(2^n)\), IEE Electron. Lett., 40, 1112-1113 (2004)
[79] Fan, H.; Dai, Y., Normal basis multiplication algorithms for \(GF(2^n) (2005)\), (full version)
[80] Nogami, Y.; Kato, H.; Nekado, K.; Uehara, S.; Morikawa, Y., Finding a basis conversion matrix using a polynomial basis derived by a small multiplicative cyclic group, IEEE Trans. Inf. Theory, 58, 4936-4947 (2012) · Zbl 1365.94452
[81] Negre, C., Finite field arithmetic using quasi-normal bases, Finite Fields Appl., 13, 635-647 (2007) · Zbl 1130.11073
[82] Baudet, G. M.; Preparata, F. P.; Vuillemin, J., Area-time optimal VLSI circuits for convolution, IEEE Trans. Comput., 32, 684-688 (1983) · Zbl 0513.94030
[83] Fürer, M.; Mehlhorn, K., \(A T^2\)-optimal Galois field multiplier for VLSI, (Proc. VLSI Algorithms and Architectures. Proc. VLSI Algorithms and Architectures, Lect. Notes Comput. Sci., vol. 227 (1986)), 217-225
[84] Fürer, M.; Mehlhorn, K., \(A T^2\)-optimal Galois field multiplier for VLSI, IEEE Trans. Comput., 38, 1333-1336 (1989) · Zbl 1395.68355
[85] Bernstein, D. J., Multidigit multiplication for mathematicians (2001), Technical Report
[86] Karatsuba, A.; Ofman, Y., Multiplication of multidigit numbers on automata, Sov. Phys. Dokl., 7, 595-596 (1963), (English translation)
[87] Toom, A. L., The complexity of a scheme of functional elements realizing the multiplication of integers, Sov. Math. Dokl., 714-716 (1963), (English translation) · Zbl 0203.15604
[88] Paar, C., Efficient VLSI architectures for bit-parallel computation in Galois fields (1994), University of Essen: University of Essen Germany, Ph.D. thesis
[89] Afanasyev, V. B., Complexity of VLSI implementation of finite field arithmetic, (Proc. II Intern. Workshop on Algebraic and Combinatorial Coding Theory. Proc. II Intern. Workshop on Algebraic and Combinatorial Coding Theory, USSR (1990)), 6-7
[90] Paar, C., A new architecture for a parallel finite field multiplier with low complexity based on composite fields, IEEE Trans. Comput., 45, 856-861 (1996) · Zbl 1049.68501
[91] Rodríguez-Henríquez, F.; Morales-Luna, G.; Saqib, N. A.; Cortés, N. C., Parallel Itoh-Tsujii multiplicative inversion algorithm for a special class of trinomials, Des. Codes Cryptogr., 45, 19-37 (2007) · Zbl 1215.11118
[92] Sunar, B., A generalized method for constructing subquadratic complexity \(GF(2^k)\) multipliers, IEEE Trans. Comput., 53, 1097-1105 (2004) · Zbl 1231.68045
[93] Winograd, S., Arithmetic Complexity of Computations (1980), SIAM · Zbl 0441.68045
[94] Averbuch, A.; Bshouty, N. H.; Kaminski, M., A classification of algorithms for multiplying polynomials of small degree over finite fields, J. Algorithms, 13, 577-588 (1992) · Zbl 0769.11049
[95] Montgomery, P., Five, six, and seven-term Karatsuba-like formulae, IEEE Trans. Comput., 54, 362-369 (2005) · Zbl 1171.11329
[96] Barbulescu, R.; Detrey, J.; Estibals, N.; Zimmermann, P., Finding optimal formulae for bilinear maps, (Proc. International Workshop of the Arithmetics of Finite Fields. Proc. International Workshop of the Arithmetics of Finite Fields, WAIFI 2012. Proc. International Workshop of the Arithmetics of Finite Fields. Proc. International Workshop of the Arithmetics of Finite Fields, WAIFI 2012, Lect. Notes Comput. Sci., vol. 7369 (2012)), 168-186 · Zbl 1293.68310
[97] Bodrato, M., Towards optimal Toom-Cook multiplication for univariate and multivariate polynomials in characteristic 2 and 0, (Proc. First Int. Workshop Arithmetic of Finite Fields. Proc. First Int. Workshop Arithmetic of Finite Fields, WAIFI 2007. Proc. First Int. Workshop Arithmetic of Finite Fields. Proc. First Int. Workshop Arithmetic of Finite Fields, WAIFI 2007, Lect. Notes Comput. Sci., vol. 4547 (2007)), 116-133 · Zbl 1213.68715
[98] Bernstein, D. J., Batch binary Edwards, (Proc. CRYPTO 2009. Proc. CRYPTO 2009, Lect. Notes Comput. Sci., vol. 5677 (2009)), 317-336 · Zbl 1248.94052
[99] Cenk, M.; Negre, C.; Hasan, M. A., Improved three-way split formulas for binary polynomial and Toeplitz matrix vector products, IEEE Trans. Comput., 62, 1345-1361 (2013) · Zbl 1365.94414
[100] Weimerskirch, A.; Paar, C., Generalizations of the Karatsuba algorithm for efficient implementations (2006), IACR Cryptology ePrint Archive, Report 2006/224
[101] Hasan, M. A.; Negre, C., Multiway splitting method for Toeplitz matrix vector product, IEEE Trans. Comput., 62, 1467-1471 (2013) · Zbl 1365.94433
[102] Lempel, A.; Seroussi, G.; Winograd, S., On the complexity of multiplication in finite fields, Theor. Comput. Sci., 22, 285-296 (1983) · Zbl 0498.68027
[103] Fan, H.; Hasan, M. A., Comments on ‘Five, six, and seven-term Karatsuba-like formulae’, IEEE Trans. Comput., 56, 716-717 (2007) · Zbl 1284.11162
[104] Cenk, M.; Özbudak, F., Improved polynomial multiplication formulas over \(F_2\) using Chinese remainder theorem, IEEE Trans. Comput., 58, 572-576 (2009) · Zbl 1367.11083
[105] Oseledets, I., Improved \(n\)-term Karatsuba-like formulas in \(GF(2)\), IEEE Trans. Comput., 60, 1212-1216 (2011) · Zbl 1366.11114
[106] Cenk, M.; Özbudak, F., Multiplication of polynomials modulo \(x^n\), Theor. Comput. Sci., 412, 3451-3462 (2011) · Zbl 1216.68123
[107] Oseledets, I., Optimal Karatsuba-like formulae for certain bilinear forms in \(GF(2)\), Linear Algebra Appl., 429, 2052-2066 (2008) · Zbl 1153.15022
[108] Kaminski, M., A lower bound for polynomial multiplication, Theor. Comput. Sci., 40, 319-322 (1985) · Zbl 0607.94010
[109] Kaminski, M.; Bshouty, N. H., Multiplicative complexity of polynomial multiplication over finite fields, J. ACM, 36, 150-170 (1989) · Zbl 0677.12007
[110] Fan, H.; Sun, J.; Gu, M.; Lam, K., Overlap-free Karatsuba-Ofman polynomial multiplication algorithms, IET Inf. Secur., 4, 8-14 (2010)
[111] Moenck, R. T., Practical fast polynomial multiplication, (Proc. 1976 ACM Symposium on Symbolic and Algebraic Computation (1976)), 136-148 · Zbl 0453.68013
[112] Hanrot, G.; Zimmermann, P., A long note on Mulders’ short product, J. Symb. Comput., 37, 391-401 (2004) · Zbl 1161.65301
[113] Zhou, G.; Michalik, H., Comments on ‘A new architecture for a parallel finite field multiplier with low complexity based on composite field’, IEEE Trans. Comput., 59, 1007-1008 (2010) · Zbl 1368.68036
[114] Negre, C., Efficient binary polynomial multiplication based on optimized Karatsuba reconstruction (2012), Technical Report hal-00724778, Team DALI/LIRMM, on Hyper Articles en Ligne (HAL)
[115] Negre, C., Improved three-way split approach for binary polynomial multiplication based on optimized reconstruction (2013), Technical Report hal-00788646, Team DALI/LIRMM, on Hyper Articles en Ligne (HAL)
[116] Fan, H.; Hasan, M. A., A new approach to subquadratic space complexity parallel multipliers for extended binary fields, IEEE Trans. Comput., 56, 224-233 (2007) · Zbl 1390.65178
[117] Hasan, M. A.; Méloni, N.; Namin, A. H.; Negre, C., Block recombination approach for subquadratic space complexity binary field multiplication based on Toeplitz matrix-vector product, IEEE Trans. Comput., 61, 151-163 (2012) · Zbl 1365.65113
[118] Hasan, M. A.; Negre, C., Low space complexity multiplication over binary fields with Dickson polynomial representation, IEEE Trans. Comput., 60, 602-607 (2011) · Zbl 1368.68224
[119] Akleylek, S.; Cenk, M.; Özbudak, F., Polynomial multiplication over binary fields using Charlier polynomial representation with low space complexity, (Proc. INDOCRYPT 2010. Proc. INDOCRYPT 2010, Lect. Notes Comput. Sci., vol. 6498 (2010)), 227-237 · Zbl 1253.94040
[120] Özbudak, F.; Akleylek, S.; Cenk, M., A new representation of elements of binary fields with subquadratic space complexity multiplication of polynomials, IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 96-A, 2016-2024 (2013)
[121] Akleylek, S., On the representation of finite fields (2010), Middle East Technical University: Middle East Technical University Turkey, Ph.D. thesis
[122] Bajard, J.-C.; Negre, C.; Plantard, T., Subquadratic space complexity binary field multiplier using double polynomial representation, IEEE Trans. Comput., 59, 1585-1597 (2010) · Zbl 1366.94476
[123] Bajard, J.-C.; Imbert, L.; Jullien, G. A., Parallel Montgomery multiplication in \(GF(2^k)\) using trinomial residue arithmetic, (Proc. 17th IEEE Symposium on Computer Arithmetic. Proc. 17th IEEE Symposium on Computer Arithmetic, ARITH-17 (2005)), 164-171
[124] Hasan, M. A., On matrix-vector product based sub-quadratic arithmetic complexity schemes for field multiplication, (Proc. SPIE 6697, 669702 (2007))
[125] Han, J.; Fan, H., \(GF(2^n)\) shifted polynomial basis multipliers based on subquadratic Toeplitz matrix-vector product approach for all irreducible pentanomials, IEEE Trans. Comput. (2014), in press
[126] Adikari, J.; Barsoum, A.; Hasan, M. A.; Namin, A. H.; Negre, C., Improved area-time tradeoffs for field multiplication using optimal normal bases, IEEE Trans. Comput., 62, 193-199 (2013) · Zbl 1365.65296
[127] Giorgi, P.; Negre, C.; Plantard, T., Subquadratic binary field multiplier in double polynomial system, (Proc. Int. Conf. Security and Cryptography. Proc. Int. Conf. Security and Cryptography, SECRYPT’07 (2007))
[128] Halbutogullari, A.; Koç, Ç. K., Parallel multiplication in \(GF(2^k)\) using polynomial residue arithmetic, Des. Codes Cryptogr., 20, 155-173 (2000) · Zbl 0976.94019
[129] Mullin, R. C.; Mahalanobis, A., Dickson bases and finite fields (2005), University of Waterloo: University of Waterloo Waterloo, Technical Report cacr2005-03
[130] Eisenbarth, T.; Kumar, S.; Paar, C.; Poschmann, A.; Uhsadel, L., A survey of lightweight-cryptography implementations, IEEE Des. Test Comput., 24 (2007)
[131] Beuchat, J.-L.; Miyoshi, T.; Oyama, Y.; Okamoto, E., Multiplication over \(F_{p^m}\) on FPGA: a survey, (Proc. ARC 2007. Proc. ARC 2007, Lect. Notes Comput. Sci., vol. 4419 (2007)), 214-225
[132] Guajardo, J.; Güneysu, T.; Kumar, S. S.; Paar, C.; Pelzl, J., Efficient hardware implementation of finite fields with applications to cryptography, Acta Appl. Math., 93, 75-118 (2006) · Zbl 1105.12003
[133] Erdem, S. S.; Yanik, T.; Koç, Ç. K., Polynomial basis multiplication over \(GF(2^m)\), Acta Appl. Math., 93, 33-55 (2006) · Zbl 1108.11089
[134] Batina, L.; Ors, S. B.; Preneel, B.; Vandewalle, J., Hardware architectures for public key cryptography, Integr. VLSI J., 34, 1-64 (2003)
[135] Goodman, J.; Chandrakasan, A., An energy efficient reconfigurable public-key cryptography processor architecture, (Proc. CHES 2000. Proc. CHES 2000, Lect. Notes Comput. Sci., vol. 1965 (2000)), 175-190 · Zbl 0998.68672
[136] Savaş, E.; Tenca, A. F.; Koç, Ç. K., A scalable and unified multiplier architecture for finite fields \(GF(p)\) and \(GF(2^m)\), (Proc. CHES 2000. Proc. CHES 2000, Lect. Notes Comput. Sci., vol. 1965 (2000)), 277-292 · Zbl 0998.68687
[137] Grobschädl, J., A bit-serial unified multiplier architecture for finite fields \(GF(p)\) and \(GF(2^m)\), (Proc. CHES 2001. Proc. CHES 2001, Lect. Notes Comput. Sci., vol. 2162 (2001)), 202-219
[138] Wolkerstorfer, J., Dual-field arithmetic unit for \(GF(p)\) and \(GF(2^m)\), (Proc. CHES 2002. Proc. CHES 2002, Lect. Notes Comput. Sci., vol. 2523 (2002)), 500-514 · Zbl 1020.94528
[139] Eberle, H.; Gura, N.; Shantz, S.; Gupta, V.; Rarick, L.; Sundaram, S., A public-key cryptographic processor for RSA and ECC, (Proc. Application-Specific Systems, Architectures, and Processors. Proc. Application-Specific Systems, Architectures, and Processors, ASAP (2004)), 98-110
[140] Satoh, A.; Takano, K., A scalable dual-field elliptic curve cryptographic processor, IEEE Trans. Comput., 52, 449-460 (2003)
[141] Järvinen, K.; Skyttä, J., On parallelization of high-speed processors for elliptic curve cryptography, IEEE Trans. Very Large Scale Integr. (VLSI) Syst., 16, 1162-1175 (2008)
[142] Azarderakhsh, R.; Reyhani-Masoleh, A., Efficient FPGA implementations of point multiplication on binary Edwards and generalized Hessian curves using Gaussian normal basis, IEEE Trans. Very Large Scale Integr. (VLSI) Syst., 20, 1453-1466 (2012)
[143] Namin, A. H.; Wu, H.; Ahmadi, M., A word-level finite field multiplier using normal basis, IEEE Trans. Comput., 60, 890-895 (2011) · Zbl 1366.94521
[144] Azarderakhsh, R.; Järvinen, K.; Dimitrov, V., Fast inversion in \(GF(2^m)\) with normal basis using hybrid-double multipliers, IEEE Trans. Comput., 63, 1041-1047 (2014) · Zbl 1364.65307
[145] Song, L.; Parhi, K. K., Low-energy digit-serial/parallel finite field multipliers, J. VLSI Signal Process., 19, 149-166 (1998)
[146] Kumar, S.; Wollinger, T.; Paar, C., Optimum digit serial \(GF(2^m)\) multipliers for curve-based cryptography, IEEE Trans. Comput., 55, 1306-1311 (2006)
[147] Zhou, G.; Michalik, H.; Hinsenkamp, L., Improving throughput of AES-GCM with pipelined Karatsuba multipliers on FPGAs, (Proc. 5th Workshop on Reconfigurable Computing: Architectures, Tools and Applications. Proc. 5th Workshop on Reconfigurable Computing: Architectures, Tools and Applications, ARC 2009 (2009)), 193-203
[148] Lee, C.-Y.; Horng, J.-S.; Jou, I.-C.; Lu, E.-H., Low-complexity bit-parallel systolic Montgomery multipliers for special classes of \(GF(2^m)\), IEEE Trans. Comput., 54, 1061-1070 (2005)
[149] Meher, P. K., Systolic and super-systolic multipliers for finite field \(GF(2^m)\) based on irreducible trinomials, IEEE Trans. Circuits Syst. I, Regul. Pap., 55, 1031-1040 (2008)
[150] Hasan, M. A., Look-up table-based large finite field multiplication in memory constrained cryptosystems, IEEE Trans. Comput., 49, 749-758 (2000) · Zbl 1391.94758
[151] Mahboob, A.; Ikram, N., Lookup table based multiplication technique for \(GF(2^m)\) with cryptographic significance, IEE Proc., Commun., 152, 965-974 (2005)
[152] Hasan, M. A.; Negre, C., Sequential multiplier with sub-linear gate complexity, J. Cryptogr. Eng., 2, 91-97 (2012)
[153] Smart, N. P., Elliptic curves over small fields of odd characteristic, J. Cryptol., 12, 141-151 (1999) · Zbl 0938.94008
[154] Boneh, D.; Franklin, M. K., Identity-based encryption from the Weil pairing, (Proc. CRYPTO 2001 (2001)), 213-229 · Zbl 1002.94023
[155] Page, D.; Smart, N. P., Hardware implementation of finite fields of characteristic three, (Proc. CHES 2002. Proc. CHES 2002, Lect. Notes Comput. Sci., vol. 2523 (2002)), 529-539 · Zbl 1028.68003
[156] Beuchat, J.-L.; Brisebarre, N.; Detrey, J.; Okamoto, E.; Rodríguez-Henríquez, F., A comparison between hardware accelerators for the modified Tate pairing over \(F_{2^m}\) and \(F_{3^m}\), (Proc. Pairing 2008. Proc. Pairing 2008, Lect. Notes Comput. Sci., vol. 5209 (2008)), 297-315 · Zbl 1186.94424
[157] Granger, R.; Page, D.; Stam, M., Hardware and software normal basis arithmetic for pairing based cryptography in characteristic three, IEEE Trans. Comput., 54, 852-860 (2005)
[158] Grabher, P.; Page, D., Hardware acceleration of the Tate pairing in characteristic three, (Proc. Cryptographic Hardware and Embedded Systems. Proc. Cryptographic Hardware and Embedded Systems, CHES 2005. Proc. Cryptographic Hardware and Embedded Systems. Proc. Cryptographic Hardware and Embedded Systems, CHES 2005, Lect. Notes Comput. Sci., vol. 3659 (2005)), 398-411 · Zbl 1319.94065
[159] Bajard, J.-C.; Imbert, L.; Negre, C., Arithmetic operations in finite fields of medium prime characteristic using the Lagrange representation, IEEE Trans. Comput., 55, 1167-1177 (2006)
[160] Beuchat, J.-L.; Detrey, J.; Estibals, N.; Okamoto, E.; Rodríguez-Henríquez, F., Fast architectures for the \(\eta_T\) pairing over small-characteristic supersingular elliptic curves, IEEE Trans. Comput., 60, 266-281 (2011) · Zbl 1366.94477
[161] Bodrato, M., Notes on low degree Toom-Cook multiplication with small characteristic (2007), Centro “Vito Volterra”, Università di Roma “Tor Vergata”, Technical Report 621
[162] Mrabet, N. E.; Guillevic, A.; Ionica, S., Efficient multiplication in finite field extensions of degree 5, (Proc. Africacrypt 2011. Proc. Africacrypt 2011, Lect. Notes Comput. Sci., vol. 6737 (2011)), 188-205 · Zbl 1280.12001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.