# American Institute of Mathematical Sciences

August & September  2019, 12(4&5): 1135-1145. doi: 10.3934/dcdss.2019078

## Efficient systolic multiplications in composite fields for cryptographic systems

 School of Computer Engineering Shenzhen Polytechnic, Shenzhen 518055, China

* Corresponding author: Haibo Yi

Received  July 2017 Revised  December 2017 Published  November 2018

Multiplications in finite fields are playing a key role in areas of cryptography and mathematic. We present approaches to exploit systolic architecture for multiplications in composite fields, which are expected to reduce the time-area product substantially. We design a pipelined architecture for multiplications in composite fields $GF({({2^n})^2})$, where $n$ is a positive integer. Besides, we design systolic architectures for multiplications and additions in finite fields $GF(2^n)$. By integrating main improvements and other minor optimizations for multiplications in $GF({({2^n})^2})$, the non-pipelined versions of our design takes $8n+4$ AND gates and $8n$ XOR gates to compute multiplications with the executing time of $nT_{AND}+4nT_{XOR}$, where $T_{AND}$ and ${T_{XOR}}$ are delays of AND and XOR gates respectively; with the aid of pipelining, the pipelined version of our design has a throughput rate of one result per $2nT_{XOR}$. Other words, the time complexity and area complexity of our design are $O(n)$. Thus, the complexity of time-area product of our design is $O(n^2)$. Experimental results and comparisons show that our design provides significant reductions in executing time and area of multiplications.

Citation: Haibo Yi. Efficient systolic multiplications in composite fields for cryptographic systems. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1135-1145. doi: 10.3934/dcdss.2019078
##### References:
 [1] N. Ahmad and S. M. R. Hasan, Low-power compact composite field AES S-Box/Inv S-Box design in 65 nm CMOS using Novel XOR Gate, Integration the VLSI Journal, 46 (2013), 333-344. [2] R. Azarderakhsh, Mozaffari-kermani M. high-performance two-dimensional finite field multiplication and exponentiation for cryptographic applications, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 34 (2015), 1569-1576. [3] S. Ballet and R. Rolland, Multiplication algorithm in a finite field and tensor rank of the multiplication, Journal of Algebra, 272 (2004), 173-185.  doi: 10.1016/j.jalgebra.2003.09.031. [4] C. Berrou and A. Glavieux, Near optimum error correcting coding and decoding: Turbo-codes, IEEE Transactions on Communications, 44 (1996), 1261-1271. [5] D. Canright, A very compact S-box for AES, Cryptographic Hardware and Embedded Systems - CHES 2005, International Workshop, Edinburgh, Uk, August 29 - September 1, 2005, Proceedings. DBLP, 2005, 441-455. [6] M. Cenk, C. K. Koc and F. Ozbudak, Polynomial multiplication over finite fields using field extensions and interpolation, IEEE Symposium on Computer Arithmetic, IEEE Computer Society, 2009, 84-91. [7] A. Cichocki and R. Unbehauen, Neural networks for solving systems of linear equations and related problems, IEEE Transactions on Circuits and Systems I Fundamental Theory and Applications, 39 (1992), 124-138. [8] M. Diab, Systolic architectures for multiplication over finite field $GF(2^m)$, International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, Springer-Verlag, 1991, 329-340. doi: 10.1007/3-540-54195-0_62. [9] A. Hariri, Concurrent error detection in montgomery multiplication over binary extension fields, IEEE Transactions on Computers, 60 (2011), 1341-1353.  doi: 10.1109/TC.2010.258. [10] M. A. Hasan, Look-up table based large finite field multiplication in memory constrained cryptosystems, Cryptography and Coding, IMA International Conference, Cirencester, Uk, December 20-22, 1999, Proceedings. DBLP, 1746 (1999), 213-221. doi: 10.1007/3-540-46665-7_25. [11] Z. Huang, G. Q. Bai and H. Y. Chen, FPGA Implementation of Systolic Array for Modular Multiplication Using a Fine-grained Approach, Microelectronics and Computer, 2005. [12] S. K. Jain, L. Song and K. K. Parhi, Efficient semisystolic architectures for finite-field arithmetic, IEEE Transactions on Very Large Scale Integration Systems, 6 (1998), 101-113. [13] R. Katti and J. Brennan, Low complexity multiplication in a finite field using ring representation, IEEE Transactions on Computers, 52 (2003), 418-427. [14] C. H. Kim, C. P. Hong and S. Kwon, A digit-serial multiplier for finite field $GF(2^m)$, IEEE Transactions on Very Large Scale Integration Systems, 13 (2005), 476-483. [15] C. Y. Lee and W. C. Che, New bit-parallel systolic architectures for computing multiplication, multiplicative inversion and division in $gf(2^m)$ under polynomial basis and normal basis representations, Journal of Signal Processing Systems, 52 (2008), 313-324. [16] D. J. C. Mackay, Good error-correcting codes based on very sparse matrices, IEEE Transactions on Information Theory, 45 (1999), 399-431.  doi: 10.1109/18.748992. [17] P. K. Meher, Systolic formulation for low-complexity serial-parallel implementation of unified finite field multiplication over $GF(2^m)$, IEEE International Conf. on Application -specific Systems, Architectures and Processors. 2007, 134-139. [18] P. K. Meher, Systolic and super-systolic multipliers for finite field $GF(2^m)$ based on irreducible trinomials, IEEE Transactions on Circuits and Systems, 55 (2008), 1031-1040.  doi: 10.1109/TCSI.2008.916622. [19] A. H. Namin, H. Wu and M. Ahmadi, Comb architectures for finite field multiplication in $F(2^m)$, IEEE Transactions on Computers, 56 (2007), 909-916.  doi: 10.1109/TC.2007.1047. [20] S. H. Namin, H. Wu and M. Ahmadi, Low-power design for a digit-serial polynomial basis finite field multiplier using factoring technique, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 25 (2017), 441-449. [21] P. Ning and Y. L. Yin, Efficient software implementation for finite field multiplication in normal basis, International Conference on Information and Communications Security, Springer-Verlag, 2001,177-188. [22] J. S. Pan, C. Y. Lee and P. K. Meher, Low-latency digit-serial and digit-parallel systolic multipliers for large binary extension fields, IEEE Transactions on Circuits & Systems I Regular Papers, 60 (2013), 3195-3204. [23] A. Petzoldt, S. Bulygin and J. Buchmann, Selecting parameters for the rainbow signature scheme, Post-Quantum Cryptography, Third International Workshop, PQCrypto 2010, Darmstadt, Germany, May 25-28, 2010. Proceedings. DBLP, 2010,218-240. doi: 10.1007/978-3-642-12929-2_16. [24] A. Pincin, A new algorithm for multiplication in finite fields, IEEE Transactions on Computers, 38 (1989), 1045-1049.  doi: 10.1109/12.30855. [25] A. Reyhani-Masoleh and M. A. Hasan, Low complexity bit parallel architectures for polynomial basis multiplication over $GF(2^m)$, IEEE Transactions on Computers, 53 (2004), 945-959. [26] A. Satoh, S. Morioka and K. Takano, et al., A compact rijndael hardware architecture with S-box optimization, Advances in Cryptology-ASIACRYPT 2001., Springer Berlin Heidelberg, 2248 (2001), 239-254. doi: 10.1007/3-540-45682-1_15. [27] T. Shirai, K. Shibutani and T. Akishita, et al., The 128-bit blockcipher CLEFIA, Proceedings of the 14th International Conference on Fast Software Encryption, Springer-Verlag, 2007,181-195. [28] M. Sudan, Decoding of reed solomon codes beyond the error-correction bound, Journal of Complexity, 13 (1997), 180-193.  doi: 10.1006/jcom.1997.0439. [29] S. Tang, H. Yi and J. Ding, et al., High-speed hardware implementation of rainbow signature on FPGAs, Post-Quantum Cryptography. Springer Berlin Heidelberg, 2011,228-243. [30] C. L. Wang and J. L. Lin, Systolic array implementation of multipliers for finite fields $GF(2^m)$, IEEE Transactions on Circuits and Systems, 38 (1991), 796-800. [31] C. W. Wu and M. K. Chang, Bit-level systolic arrays for finite-field multiplications, Journal of Signal Processing Systems, 10 (1995), 85-92. [32] H. Wu, Bit-parallel finite field multiplier and squarer using polynomial basis, IEEE Transactions on Computers, 51 (2002), 750-758.  doi: 10.1109/TC.2002.1017695. [33] J. Xie, J. J. He and P. K. Meher, Low latency systolic montgomery multiplier for finite field $GF(2^m)$ based on pentanomials, IEEE Transactions on Very Large Scale Integration Systems, 21 (2013), 385-389. [34] J. Xie, P. K. Meher and Z. H. Mao, Low-latency high-throughput systolic multipliers over $GF(2^m)$ for NIST recommended pentanomials, IEEE Transactions on Circuits & Systems I Regular Papers, 62 (2015), 881-890.  doi: 10.1109/TCSI.2014.2386782. [35] H. Yi and W. Li, Fast three-input multipliers over small composite fields for multivariate public key cryptography, International Journal of Security and Its Applications, 9 (2015), 165-178. [36] H. Yi, W. Li and Z. Nie, Fast hardware implementations of inversions in small finite fields for special irreducible polynomials on FPGAs, International Journal of Security and Its Applications, 19 (2016), 109-C120. [37] H. Yi and S. Tang, Very small FPGA processor for multivariate signatures, Computer Journal, 59 (2016), 1091-1101.  doi: 10.1093/comjnl/bxw008. [38] H. Yi, S. Tang and R. Vemuri, Fast inversions in small finite fields by using binary trees, The Computer Journal, 59 (2016), 1102-1112.  doi: 10.1093/comjnl/bxw009.

show all references

##### References:
 [1] N. Ahmad and S. M. R. Hasan, Low-power compact composite field AES S-Box/Inv S-Box design in 65 nm CMOS using Novel XOR Gate, Integration the VLSI Journal, 46 (2013), 333-344. [2] R. Azarderakhsh, Mozaffari-kermani M. high-performance two-dimensional finite field multiplication and exponentiation for cryptographic applications, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 34 (2015), 1569-1576. [3] S. Ballet and R. Rolland, Multiplication algorithm in a finite field and tensor rank of the multiplication, Journal of Algebra, 272 (2004), 173-185.  doi: 10.1016/j.jalgebra.2003.09.031. [4] C. Berrou and A. Glavieux, Near optimum error correcting coding and decoding: Turbo-codes, IEEE Transactions on Communications, 44 (1996), 1261-1271. [5] D. Canright, A very compact S-box for AES, Cryptographic Hardware and Embedded Systems - CHES 2005, International Workshop, Edinburgh, Uk, August 29 - September 1, 2005, Proceedings. DBLP, 2005, 441-455. [6] M. Cenk, C. K. Koc and F. Ozbudak, Polynomial multiplication over finite fields using field extensions and interpolation, IEEE Symposium on Computer Arithmetic, IEEE Computer Society, 2009, 84-91. [7] A. Cichocki and R. Unbehauen, Neural networks for solving systems of linear equations and related problems, IEEE Transactions on Circuits and Systems I Fundamental Theory and Applications, 39 (1992), 124-138. [8] M. Diab, Systolic architectures for multiplication over finite field $GF(2^m)$, International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, Springer-Verlag, 1991, 329-340. doi: 10.1007/3-540-54195-0_62. [9] A. Hariri, Concurrent error detection in montgomery multiplication over binary extension fields, IEEE Transactions on Computers, 60 (2011), 1341-1353.  doi: 10.1109/TC.2010.258. [10] M. A. Hasan, Look-up table based large finite field multiplication in memory constrained cryptosystems, Cryptography and Coding, IMA International Conference, Cirencester, Uk, December 20-22, 1999, Proceedings. DBLP, 1746 (1999), 213-221. doi: 10.1007/3-540-46665-7_25. [11] Z. Huang, G. Q. Bai and H. Y. Chen, FPGA Implementation of Systolic Array for Modular Multiplication Using a Fine-grained Approach, Microelectronics and Computer, 2005. [12] S. K. Jain, L. Song and K. K. Parhi, Efficient semisystolic architectures for finite-field arithmetic, IEEE Transactions on Very Large Scale Integration Systems, 6 (1998), 101-113. [13] R. Katti and J. Brennan, Low complexity multiplication in a finite field using ring representation, IEEE Transactions on Computers, 52 (2003), 418-427. [14] C. H. Kim, C. P. Hong and S. Kwon, A digit-serial multiplier for finite field $GF(2^m)$, IEEE Transactions on Very Large Scale Integration Systems, 13 (2005), 476-483. [15] C. Y. Lee and W. C. Che, New bit-parallel systolic architectures for computing multiplication, multiplicative inversion and division in $gf(2^m)$ under polynomial basis and normal basis representations, Journal of Signal Processing Systems, 52 (2008), 313-324. [16] D. J. C. Mackay, Good error-correcting codes based on very sparse matrices, IEEE Transactions on Information Theory, 45 (1999), 399-431.  doi: 10.1109/18.748992. [17] P. K. Meher, Systolic formulation for low-complexity serial-parallel implementation of unified finite field multiplication over $GF(2^m)$, IEEE International Conf. on Application -specific Systems, Architectures and Processors. 2007, 134-139. [18] P. K. Meher, Systolic and super-systolic multipliers for finite field $GF(2^m)$ based on irreducible trinomials, IEEE Transactions on Circuits and Systems, 55 (2008), 1031-1040.  doi: 10.1109/TCSI.2008.916622. [19] A. H. Namin, H. Wu and M. Ahmadi, Comb architectures for finite field multiplication in $F(2^m)$, IEEE Transactions on Computers, 56 (2007), 909-916.  doi: 10.1109/TC.2007.1047. [20] S. H. Namin, H. Wu and M. Ahmadi, Low-power design for a digit-serial polynomial basis finite field multiplier using factoring technique, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 25 (2017), 441-449. [21] P. Ning and Y. L. Yin, Efficient software implementation for finite field multiplication in normal basis, International Conference on Information and Communications Security, Springer-Verlag, 2001,177-188. [22] J. S. Pan, C. Y. Lee and P. K. Meher, Low-latency digit-serial and digit-parallel systolic multipliers for large binary extension fields, IEEE Transactions on Circuits & Systems I Regular Papers, 60 (2013), 3195-3204. [23] A. Petzoldt, S. Bulygin and J. Buchmann, Selecting parameters for the rainbow signature scheme, Post-Quantum Cryptography, Third International Workshop, PQCrypto 2010, Darmstadt, Germany, May 25-28, 2010. Proceedings. DBLP, 2010,218-240. doi: 10.1007/978-3-642-12929-2_16. [24] A. Pincin, A new algorithm for multiplication in finite fields, IEEE Transactions on Computers, 38 (1989), 1045-1049.  doi: 10.1109/12.30855. [25] A. Reyhani-Masoleh and M. A. Hasan, Low complexity bit parallel architectures for polynomial basis multiplication over $GF(2^m)$, IEEE Transactions on Computers, 53 (2004), 945-959. [26] A. Satoh, S. Morioka and K. Takano, et al., A compact rijndael hardware architecture with S-box optimization, Advances in Cryptology-ASIACRYPT 2001., Springer Berlin Heidelberg, 2248 (2001), 239-254. doi: 10.1007/3-540-45682-1_15. [27] T. Shirai, K. Shibutani and T. Akishita, et al., The 128-bit blockcipher CLEFIA, Proceedings of the 14th International Conference on Fast Software Encryption, Springer-Verlag, 2007,181-195. [28] M. Sudan, Decoding of reed solomon codes beyond the error-correction bound, Journal of Complexity, 13 (1997), 180-193.  doi: 10.1006/jcom.1997.0439. [29] S. Tang, H. Yi and J. Ding, et al., High-speed hardware implementation of rainbow signature on FPGAs, Post-Quantum Cryptography. Springer Berlin Heidelberg, 2011,228-243. [30] C. L. Wang and J. L. Lin, Systolic array implementation of multipliers for finite fields $GF(2^m)$, IEEE Transactions on Circuits and Systems, 38 (1991), 796-800. [31] C. W. Wu and M. K. Chang, Bit-level systolic arrays for finite-field multiplications, Journal of Signal Processing Systems, 10 (1995), 85-92. [32] H. Wu, Bit-parallel finite field multiplier and squarer using polynomial basis, IEEE Transactions on Computers, 51 (2002), 750-758.  doi: 10.1109/TC.2002.1017695. [33] J. Xie, J. J. He and P. K. Meher, Low latency systolic montgomery multiplier for finite field $GF(2^m)$ based on pentanomials, IEEE Transactions on Very Large Scale Integration Systems, 21 (2013), 385-389. [34] J. Xie, P. K. Meher and Z. H. Mao, Low-latency high-throughput systolic multipliers over $GF(2^m)$ for NIST recommended pentanomials, IEEE Transactions on Circuits & Systems I Regular Papers, 62 (2015), 881-890.  doi: 10.1109/TCSI.2014.2386782. [35] H. Yi and W. Li, Fast three-input multipliers over small composite fields for multivariate public key cryptography, International Journal of Security and Its Applications, 9 (2015), 165-178. [36] H. Yi, W. Li and Z. Nie, Fast hardware implementations of inversions in small finite fields for special irreducible polynomials on FPGAs, International Journal of Security and Its Applications, 19 (2016), 109-C120. [37] H. Yi and S. Tang, Very small FPGA processor for multivariate signatures, Computer Journal, 59 (2016), 1091-1101.  doi: 10.1093/comjnl/bxw008. [38] H. Yi, S. Tang and R. Vemuri, Fast inversions in small finite fields by using binary trees, The Computer Journal, 59 (2016), 1102-1112.  doi: 10.1093/comjnl/bxw009.
Pipelined Architecture for Multiplications in $GF({({2^n})^2})$
Systolic Component $MUL$ in $GF(2^n)$
Computing Systolic Multiplication in $GF(2^n)$
Systolic Component $ADD$ in $GF(2^n)$
Executing Time and Area for Non-Pipelined Multiplication in $GF((2^n)^2)$
 Stage Clock Cycle Executing Time Area (Logic Gates) 0 $2n$ $2nT_{XOR}$ $4n+2$ AND gates, $4n$ XOR gates 1 $2n$ $2nT_{XOR}$ $4n$ AND gates, $4n$ XOR gates 2 $n$ $nT_{AND}$ $2$ AND gates Total $5n$ $nT_{AND}+4nT_{XOR}$ $8n+4$ AND gates, $8n$ XOR gates
 Stage Clock Cycle Executing Time Area (Logic Gates) 0 $2n$ $2nT_{XOR}$ $4n+2$ AND gates, $4n$ XOR gates 1 $2n$ $2nT_{XOR}$ $4n$ AND gates, $4n$ XOR gates 2 $n$ $nT_{AND}$ $2$ AND gates Total $5n$ $nT_{AND}+4nT_{XOR}$ $8n+4$ AND gates, $8n$ XOR gates
Executing Time for Pipelined Multiplications in $GF((2^n)^2)$
 Input Starting Time Ending Time $a,b$ 0 $nT_{AND}+4nT_{XOR}$ $a^{'},b^{'}$ $2nT_{XOR}$ $nT_{AND}+6nT_{XOR}$ $a^{''},b^{''}$ $4nT_{XOR}$ $nT_{AND}+8nT_{XOR}$ $a^{'''},b^{'''}$ $6nT_{XOR}$ $nT_{AND}+10nT_{XOR}$ $\ldots$ $\ldots$
 Input Starting Time Ending Time $a,b$ 0 $nT_{AND}+4nT_{XOR}$ $a^{'},b^{'}$ $2nT_{XOR}$ $nT_{AND}+6nT_{XOR}$ $a^{''},b^{''}$ $4nT_{XOR}$ $nT_{AND}+8nT_{XOR}$ $a^{'''},b^{'''}$ $6nT_{XOR}$ $nT_{AND}+10nT_{XOR}$ $\ldots$ $\ldots$
Performance Evaluation of Our Design for Multiplications in $GF((2^n)^2)$
 Field Clock Cycle Executing Time Throughput Cells Area (Logic Gates) $GF((2^n)^2)$ $5n$ $nT_{AND}$+$4nT_{XOR}$ $2nT_{XOR}$ $4$ $8n+4$ AND gates $8n$ XOR gates
 Field Clock Cycle Executing Time Throughput Cells Area (Logic Gates) $GF((2^n)^2)$ $5n$ $nT_{AND}$+$4nT_{XOR}$ $2nT_{XOR}$ $4$ $8n+4$ AND gates $8n$ XOR gates
ASIC, Altera FPGA and Xilinx FPGA Implementations
 Finite Field $T_0^{0}$ $T_1^{0}$ $A_0^{0}$ $T_2^{1}$ $T_3^{1}$ $A_1^{1}$ $U_0^{1}$ $T_4^{2}$ $T_5^{2}$ $A_2^{2}$ $U_1^{2}$ $GF((2^2)^2)$ 1.4 0.6 478.8 16.8 7.1 48 $\ll$1% 17.8 7.2 45 $\ll$1% $GF((2^4)^2)$ 2.8 1.2 904.4 34.4 14.1 89 $\ll$1% 35.9 14.2 83 $\ll$1% $GF((2^{13})^2)$ 9.1 3.7 2819.6 116.4 44.6 245 < 1% 117.3 46.3 232 < 1% $GF((2^{17})^2)$ 11.9 4.8 3670.8 147.7 58.4 313 < 1% 152.6 60.8 298 < 1% $GF((2^{31})^2)$ 21.7 8.8 6650.2 271.1 102.4 557 < 1% 275.9 110.4 537 < 1% $GF((2^{37})^2)$ 25.9 10.3 7926.8 321.9 125.9 634 < 1% 329.3 131.7 614 < 1% $GF((2^{61})^2)$ 42.7 17.1 13034.2 541.4 211.8 1023 < 1% 542.9 217.2 998 1.44% $GF((2^{67})^2)$ 46.7 18.8 14310.8 574.2 233.1 1124 < 1% 589.6 238.5 1097 1.58% $GF((2^{119})^2)$ 83.3 33.4 25376.4 1055.9 411.9 2012 1.41% 1059.3 423.6 1927 2.79% $GF((2^{127})^2)$ 88.9 33.6 27078.8 1134.6 446.3 2119 1.47% 1141.6 456.8 2078 3.01% $^{0}$ ASIC (TSMC-0.18$\mu$m CMOS) implementations: $T_0$ (ns) is the executing time of non-pipelined designs; $T_1$ (ns) is the executing time of pipelined designs; $A_0$ ($\mu m^2$) is area. $^{1}$ Altera FPGA (Stratix Ⅱ EP2S180F1508C3) implementations: $T_2$ (ns) is the executing time of non-pipelined designs; $T_3$ (ns) is the executing time of pipelined designs; $A_1$ is combinational ALUTs; $U_0$ is the utilization rate of combinational ALUTs. $^{2}$ Xilinx FPGA (Virtex 5 XC5VLX110T) implementations: $T_4$ (ns) is the executing time of non-pipelined designs; $T_5$ (ns) is the executing time of pipelined designs; $A_2$ is slice LUTs; $U_1$ is the utilization rate of slice LUTs.
 Finite Field $T_0^{0}$ $T_1^{0}$ $A_0^{0}$ $T_2^{1}$ $T_3^{1}$ $A_1^{1}$ $U_0^{1}$ $T_4^{2}$ $T_5^{2}$ $A_2^{2}$ $U_1^{2}$ $GF((2^2)^2)$ 1.4 0.6 478.8 16.8 7.1 48 $\ll$1% 17.8 7.2 45 $\ll$1% $GF((2^4)^2)$ 2.8 1.2 904.4 34.4 14.1 89 $\ll$1% 35.9 14.2 83 $\ll$1% $GF((2^{13})^2)$ 9.1 3.7 2819.6 116.4 44.6 245 < 1% 117.3 46.3 232 < 1% $GF((2^{17})^2)$ 11.9 4.8 3670.8 147.7 58.4 313 < 1% 152.6 60.8 298 < 1% $GF((2^{31})^2)$ 21.7 8.8 6650.2 271.1 102.4 557 < 1% 275.9 110.4 537 < 1% $GF((2^{37})^2)$ 25.9 10.3 7926.8 321.9 125.9 634 < 1% 329.3 131.7 614 < 1% $GF((2^{61})^2)$ 42.7 17.1 13034.2 541.4 211.8 1023 < 1% 542.9 217.2 998 1.44% $GF((2^{67})^2)$ 46.7 18.8 14310.8 574.2 233.1 1124 < 1% 589.6 238.5 1097 1.58% $GF((2^{119})^2)$ 83.3 33.4 25376.4 1055.9 411.9 2012 1.41% 1059.3 423.6 1927 2.79% $GF((2^{127})^2)$ 88.9 33.6 27078.8 1134.6 446.3 2119 1.47% 1141.6 456.8 2078 3.01% $^{0}$ ASIC (TSMC-0.18$\mu$m CMOS) implementations: $T_0$ (ns) is the executing time of non-pipelined designs; $T_1$ (ns) is the executing time of pipelined designs; $A_0$ ($\mu m^2$) is area. $^{1}$ Altera FPGA (Stratix Ⅱ EP2S180F1508C3) implementations: $T_2$ (ns) is the executing time of non-pipelined designs; $T_3$ (ns) is the executing time of pipelined designs; $A_1$ is combinational ALUTs; $U_0$ is the utilization rate of combinational ALUTs. $^{2}$ Xilinx FPGA (Virtex 5 XC5VLX110T) implementations: $T_4$ (ns) is the executing time of non-pipelined designs; $T_5$ (ns) is the executing time of pipelined designs; $A_2$ is slice LUTs; $U_1$ is the utilization rate of slice LUTs.
Comparison of Our Design with Other multiplications in $GF((2^n)^2)$
 Pan et al. [22] Xie et al. [34] Namin et al. [20] Hariri et al. [9] Ours O(Time) $n^2$ $n$ $nlog_22n$ $log_22n$ $n$ O(Area) $n\sqrt {2n}$ $n^2$ $n$ $n^2$ $n$ O(Time$^*$Area) $n^3\sqrt {2n}$ $n^3$ $n^2log_22n$ $n^2log_22n$ $n^2$
 Pan et al. [22] Xie et al. [34] Namin et al. [20] Hariri et al. [9] Ours O(Time) $n^2$ $n$ $nlog_22n$ $log_22n$ $n$ O(Area) $n\sqrt {2n}$ $n^2$ $n$ $n^2$ $n$ O(Time$^*$Area) $n^3\sqrt {2n}$ $n^3$ $n^2log_22n$ $n^2log_22n$ $n^2$
 [1] Grégory Berhuy, Jean Fasel, Odile Garotta. Rank weights for arbitrary finite field extensions. Advances in Mathematics of Communications, 2021, 15 (4) : 575-587. doi: 10.3934/amc.2020083 [2] Laura Aquilanti, Simone Cacace, Fabio Camilli, Raul De Maio. A Mean Field Games model for finite mixtures of Bernoulli and categorical distributions. Journal of Dynamics and Games, 2021, 8 (1) : 35-59. doi: 10.3934/jdg.2020033 [3] Angela Aguglia, Antonio Cossidente, Giuseppe Marino, Francesco Pavese, Alessandro Siciliano. Orbit codes from forms on vector spaces over a finite field. Advances in Mathematics of Communications, 2022, 16 (1) : 135-155. doi: 10.3934/amc.2020105 [4] Jaime Gutierrez. Reconstructing points of superelliptic curves over a prime finite field. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022022 [5] Sylvain Sorin, Cheng Wan. Finite composite games: Equilibria and dynamics. Journal of Dynamics and Games, 2016, 3 (1) : 101-120. doi: 10.3934/jdg.2016005 [6] L. Bakker. Semiconjugacy of quasiperiodic flows and finite index subgroups of multiplier groups. Conference Publications, 2005, 2005 (Special) : 60-69. doi: 10.3934/proc.2005.2005.60 [7] Hakan Özadam, Ferruh Özbudak. A note on negacyclic and cyclic codes of length $p^s$ over a finite field of characteristic $p$. Advances in Mathematics of Communications, 2009, 3 (3) : 265-271. doi: 10.3934/amc.2009.3.265 [8] Keisuke Hakuta, Hisayoshi Sato, Tsuyoshi Takagi. On tameness of Matsumoto-Imai central maps in three variables over the finite field $\mathbb F_2$. Advances in Mathematics of Communications, 2016, 10 (2) : 221-228. doi: 10.3934/amc.2016002 [9] Farzane Amirzade, Mohammad-Reza Sadeghi, Daniel Panario. QC-LDPC construction free of small size elementary trapping sets based on multiplicative subgroups of a finite field. Advances in Mathematics of Communications, 2020, 14 (3) : 397-411. doi: 10.3934/amc.2020062 [10] Tetsuya Ishiwata, Kota Kumazaki. Structure preserving finite difference scheme for the Landau-Lifshitz equation with applied magnetic field. Conference Publications, 2015, 2015 (special) : 644-651. doi: 10.3934/proc.2015.0644 [11] Liupeng Wang, Yunqing Huang. Error estimates for second-order SAV finite element method to phase field crystal model. Electronic Research Archive, 2021, 29 (1) : 1735-1752. doi: 10.3934/era.2020089 [12] Yi Shi, Kai Bao, Xiao-Ping Wang. 3D adaptive finite element method for a phase field model for the moving contact line problems. Inverse Problems and Imaging, 2013, 7 (3) : 947-959. doi: 10.3934/ipi.2013.7.947 [13] Wenya Qi, Padmanabhan Seshaiyer, Junping Wang. A four-field mixed finite element method for Biot's consolidation problems. Electronic Research Archive, 2021, 29 (3) : 2517-2532. doi: 10.3934/era.2020127 [14] Pavel Krejčí, Elisabetta Rocca, Jürgen Sprekels. Phase separation in a gravity field. Discrete and Continuous Dynamical Systems - S, 2011, 4 (2) : 391-407. doi: 10.3934/dcdss.2011.4.391 [15] Marco Castrillón López, Mark J. Gotay. Covariantizing classical field theories. Journal of Geometric Mechanics, 2011, 3 (4) : 487-506. doi: 10.3934/jgm.2011.3.487 [16] Franco Flandoli, Matti Leimbach. Mean field limit with proliferation. Discrete and Continuous Dynamical Systems - B, 2016, 21 (9) : 3029-3052. doi: 10.3934/dcdsb.2016086 [17] Sophie Guillaume. Evolution equations governed by the subdifferential of a convex composite function in finite dimensional spaces. Discrete and Continuous Dynamical Systems, 1996, 2 (1) : 23-52. doi: 10.3934/dcds.1996.2.23 [18] Franz W. Kamber and Peter W. Michor. The flow completion of a manifold with vector field. Electronic Research Announcements, 2000, 6: 95-97. [19] Peijun Li, Yuliang Wang. Near-field imaging of obstacles. Inverse Problems and Imaging, 2015, 9 (1) : 189-210. doi: 10.3934/ipi.2015.9.189 [20] Xinfu Chen, G. Caginalp, Christof Eck. A rapidly converging phase field model. Discrete and Continuous Dynamical Systems, 2006, 15 (4) : 1017-1034. doi: 10.3934/dcds.2006.15.1017

2020 Impact Factor: 2.425

## Metrics

• HTML views (733)
• Cited by (0)

• on AIMS