American Institute of Mathematical Sciences

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

Efficient systolic multiplications in composite fields for cryptographic systems

Haibo Yi ,

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.

Keywords: Multiplication, multiplier, composite field, finite field, systolic.
Mathematics Subject Classification: 12Y05.
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

Figure 1.  Pipelined Architecture for Multiplications in $GF({({2^n})^2})$
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  Systolic Component $MUL$ in $GF(2^n)$
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  Computing Systolic Multiplication in $GF(2^n)$
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 4.  Systolic Component $ADD$ in $GF(2^n)$
Figure Options

Download full-size image

Download as PowerPoint slide

Table 1.  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
Table Options

Download as excel

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
Table 2.  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$
Table Options

Download as excel

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$
Table 3.  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
Table Options

Download as excel

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
Table 4.  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.
Table Options

Download as excel

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.
Table 5.  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$
Table Options

Download as excel

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]

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 & Games, 2020  doi: 10.3934/jdg.2020033
[2]

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
[3]

Wenya Qi, Padmanabhan Seshaiyer, Junping Wang. A four-field mixed finite element method for Biot's consolidation problems. Electronic Research Archive, , () : -. doi: 10.3934/era.2020127
[4]

Parikshit Upadhyaya, Elias Jarlebring, Emanuel H. Rubensson. A density matrix approach to the convergence of the self-consistent field iteration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 99-115. doi: 10.3934/naco.2020018
[5]

Illés Horváth, Kristóf Attila Horváth, Péter Kovács, Miklós Telek. Mean-field analysis of a scaling MAC radio protocol. Journal of Industrial & Management Optimization, 2021, 17 (1) : 279-297. doi: 10.3934/jimo.2019111
[6]

Josselin Garnier, Knut Sølna. Enhanced Backscattering of a partially coherent field from an anisotropic random lossy medium. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 1171-1195. doi: 10.3934/dcdsb.2020158
[7]

Claudianor O. Alves, Rodrigo C. M. Nemer, Sergio H. Monari Soares. The use of the Morse theory to estimate the number of nontrivial solutions of a nonlinear Schrödinger equation with a magnetic field. Communications on Pure & Applied Analysis, 2021, 20 (1) : 449-465. doi: 10.3934/cpaa.2020276
[8]

Jann-Long Chern, Sze-Guang Yang, Zhi-You Chen, Chih-Her Chen. On the family of non-topological solutions for the elliptic system arising from a product Abelian gauge field theory. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3291-3304. doi: 10.3934/dcds.2020127
[9]

Daniele Bartolucci, Changfeng Gui, Yeyao Hu, Aleks Jevnikar, Wen Yang. Mean field equations on tori: Existence and uniqueness of evenly symmetric blow-up solutions. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3093-3116. doi: 10.3934/dcds.2020039
[10]

Alain Bensoussan, Xinwei Feng, Jianhui Huang. Linear-quadratic-Gaussian mean-field-game with partial observation and common noise. Mathematical Control & Related Fields, 2021, 11 (1) : 23-46. doi: 10.3934/mcrf.2020025
[11]

Jingrui Sun, Hanxiao Wang. Mean-field stochastic linear-quadratic optimal control problems: Weak closed-loop solvability. Mathematical Control & Related Fields, 2021, 11 (1) : 47-71. doi: 10.3934/mcrf.2020026
[12]

Dan Zhu, Rosemary A. Renaut, Hongwei Li, Tianyou Liu. Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory. Inverse Problems & Imaging, 2021, 15 (1) : 159-183. doi: 10.3934/ipi.2020076
[13]

Madhurima Mukhopadhyay, Palash Sarkar, Shashank Singh, Emmanuel Thomé. New discrete logarithm computation for the medium prime case using the function field sieve. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020119
[14]

P. K. Jha, R. Lipton. Finite element approximation of nonlocal dynamic fracture models. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1675-1710. doi: 10.3934/dcdsb.2020178
[15]

Ying Liu, Yanping Chen, Yunqing Huang, Yang Wang. Two-grid method for semiconductor device problem by mixed finite element method and characteristics finite element method. Electronic Research Archive, 2021, 29 (1) : 1859-1880. doi: 10.3934/era.2020095
[16]

Xuefei He, Kun Wang, Liwei Xu. Efficient finite difference methods for the nonlinear Helmholtz equation in Kerr medium. Electronic Research Archive, 2020, 28 (4) : 1503-1528. doi: 10.3934/era.2020079
[17]

Yue Feng, Yujie Liu, Ruishu Wang, Shangyou Zhang. A conforming discontinuous Galerkin finite element method on rectangular partitions. Electronic Research Archive, , () : -. doi: 10.3934/era.2020120
[18]

Bin Wang, Lin Mu. Viscosity robust weak Galerkin finite element methods for Stokes problems. Electronic Research Archive, 2021, 29 (1) : 1881-1895. doi: 10.3934/era.2020096
[19]

Xiu Ye, Shangyou Zhang, Peng Zhu. A weak Galerkin finite element method for nonlinear conservation laws. Electronic Research Archive, 2021, 29 (1) : 1897-1923. doi: 10.3934/era.2020097
[20]

Jiwei Jia, Young-Ju Lee, Yue Feng, Zichan Wang, Zhongshu Zhao. Hybridized weak Galerkin finite element methods for Brinkman equations. Electronic Research Archive, , () : -. doi: 10.3934/era.2020126

2019 Impact Factor: 1.233

Tools

Metrics

  • PDF downloads (84)
  • HTML views (485)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences