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 & 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.   Google Scholar [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.   Google Scholar [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.  Google Scholar [4] C. Berrou and A. Glavieux, Near optimum error correcting coding and decoding: Turbo-codes, IEEE Transactions on Communications, 44 (1996), 1261-1271.   Google Scholar [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. Google Scholar [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. Google Scholar [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.   Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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. Google Scholar [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.   Google Scholar [13] R. Katti and J. Brennan, Low complexity multiplication in a finite field using ring representation, IEEE Transactions on Computers, 52 (2003), 418-427.   Google Scholar [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.   Google Scholar [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.   Google Scholar [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.  Google Scholar [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. Google Scholar [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.  Google Scholar [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.  Google Scholar [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.   Google Scholar [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. Google Scholar [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.   Google Scholar [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.  Google Scholar [24] A. Pincin, A new algorithm for multiplication in finite fields, IEEE Transactions on Computers, 38 (1989), 1045-1049.  doi: 10.1109/12.30855.  Google Scholar [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.   Google Scholar [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.  Google Scholar [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. Google Scholar [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.  Google Scholar [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. Google Scholar [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.   Google Scholar [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.   Google Scholar [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.  Google Scholar [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.   Google Scholar [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.  Google Scholar [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.   Google Scholar [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.   Google Scholar [37] H. Yi and S. Tang, Very small FPGA processor for multivariate signatures, Computer Journal, 59 (2016), 1091-1101.  doi: 10.1093/comjnl/bxw008.  Google Scholar [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.  Google Scholar

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.   Google Scholar [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.   Google Scholar [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.  Google Scholar [4] C. Berrou and A. Glavieux, Near optimum error correcting coding and decoding: Turbo-codes, IEEE Transactions on Communications, 44 (1996), 1261-1271.   Google Scholar [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. Google Scholar [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. Google Scholar [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.   Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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. Google Scholar [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.   Google Scholar [13] R. Katti and J. Brennan, Low complexity multiplication in a finite field using ring representation, IEEE Transactions on Computers, 52 (2003), 418-427.   Google Scholar [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.   Google Scholar [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.   Google Scholar [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.  Google Scholar [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. Google Scholar [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.  Google Scholar [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.  Google Scholar [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.   Google Scholar [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. Google Scholar [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.   Google Scholar [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.  Google Scholar [24] A. Pincin, A new algorithm for multiplication in finite fields, IEEE Transactions on Computers, 38 (1989), 1045-1049.  doi: 10.1109/12.30855.  Google Scholar [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.   Google Scholar [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.  Google Scholar [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. Google Scholar [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.  Google Scholar [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. Google Scholar [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.   Google Scholar [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.   Google Scholar [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.  Google Scholar [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.   Google Scholar [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.  Google Scholar [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.   Google Scholar [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.   Google Scholar [37] H. Yi and S. Tang, Very small FPGA processor for multivariate signatures, Computer Journal, 59 (2016), 1091-1101.  doi: 10.1093/comjnl/bxw008.  Google Scholar [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.  Google Scholar
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] 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 [2] Michael Grinfeld, Amy Novick-Cohen. Some remarks on stability for a phase field model with memory. Discrete & Continuous Dynamical Systems - A, 2006, 15 (4) : 1089-1117. doi: 10.3934/dcds.2006.15.1089 [3] Marco Cirant, Diogo A. Gomes, Edgard A. Pimentel, Héctor Sánchez-Morgado. On some singular mean-field games. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021006 [4] Seung-Yeal Ha, Jinwook Jung, Jeongho Kim, Jinyeong Park, Xiongtao Zhang. A mean-field limit of the particle swarmalator model. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2021011 [5] Tomáš Roubíček. An energy-conserving time-discretisation scheme for poroelastic media with phase-field fracture emitting waves and heat. Discrete & Continuous Dynamical Systems - S, 2017, 10 (4) : 867-893. doi: 10.3934/dcdss.2017044 [6] Arseny Egorov. Morse coding for a Fuchsian group of finite covolume. Journal of Modern Dynamics, 2009, 3 (4) : 637-646. doi: 10.3934/jmd.2009.3.637 [7] Murat Uzunca, Ayşe Sarıaydın-Filibelioǧlu. Adaptive discontinuous galerkin finite elements for advective Allen-Cahn equation. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 269-281. doi: 10.3934/naco.2020025 [8] Lunji Song, Wenya Qi, Kaifang Liu, Qingxian Gu. A new over-penalized weak galerkin finite element method. Part Ⅱ: Elliptic interface problems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2581-2598. doi: 10.3934/dcdsb.2020196 [9] Zengyun Wang, Jinde Cao, Zuowei Cai, Lihong Huang. Finite-time stability of impulsive differential inclusion: Applications to discontinuous impulsive neural networks. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2677-2692. doi: 10.3934/dcdsb.2020200 [10] Marita Holtmannspötter, Arnd Rösch, Boris Vexler. A priori error estimates for the space-time finite element discretization of an optimal control problem governed by a coupled linear PDE-ODE system. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021014

2019 Impact Factor: 1.233

Tools

Article outline

Figures and Tables