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 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.

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]

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

Tools

Article outline

Figures and Tables

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy