# American Institute of Mathematical Sciences

• Previous Article
Connection of $p$-ary $t$-weight linear codes to Ramanujan Cayley graphs with $t+1$ eigenvalues
• AMC Home
• This Issue
• Next Article
Locally repairable codes with high availability based on generalised quadrangles
doi: 10.3934/amc.2020113

## Efficient arithmetic in (pseudo-)Mersenne prime order fields

 Applied Statistics Unit, Indian Statistical Institute, 203, B. T. Road, Kolkata-700108, India

* Corresponding author.

Received  October 2019 Revised  May 2020 Published  October 2020

Elliptic curve cryptography is based upon elliptic curves defined over finite fields. Operations over such elliptic curves require arithmetic over the underlying field. In particular, fast implementations of multiplication and squaring over the finite field are required for performing efficient elliptic curve cryptography. The present work considers the problem of obtaining efficient algorithms for field multiplication and squaring. From a theoretical point of view, we present a number of algorithms for multiplication/squaring and reduction which are appropriate for different settings. Our algorithms collect together and generalize ideas which are scattered across various papers and codes. At the same time, we also introduce new ideas to improve upon existing works. A key theoretical feature of our work is that we provide formal statements and detailed proofs of correctness of the different reduction algorithms that we describe. On the implementation aspect, a total of fourteen primes are considered, covering all previously proposed cryptographically relevant (pseudo-)Mersenne prime order fields at various security levels. For each of these fields, we provide 64-bit assembly implementations of the relevant multiplication and squaring algorithms targeted towards two different modern Intel architectures. We were able to find previous 64-bit implementations for six of the fourteen primes considered in this work. On the Haswell and Skylake processors of Intel, for all the six primes where previous implementations are available, our implementations outperform such previous implementations.

Citation: Kaushik Nath, Palash Sarkar. Efficient arithmetic in (pseudo-)Mersenne prime order fields. Advances in Mathematics of Communications, doi: 10.3934/amc.2020113
##### References:
 [1] D. F. Aranha, S. Paulo, L. M. Barreto, C. Geovandro, C. F. Pereira, and J. E. Ricardini, A note on high-security general-purpose elliptic curves, Cryptology ePrint Archive, Report 2013/647, 2013. Google Scholar [2] D. Bernstein and B.-Y. Yang, Fast constant-time gcd computation and modular inversion, IACR Transactions on Cryptographic Hardware and Embedded Systems, 2019 (2019), 340-398.   Google Scholar [3] D. J. Bernstein, Curve25519: New Diffie-Hellman speed records, in Public Key Cryptography - PKC 2006, 9th International Conference on Theory and Practice of Public-Key Cryptography, New York, NY, USA, April 24-26, 2006, Proceedings, Lecture Notes in Computer Science, 3958, Springer, 2006,207–228. doi: 10.1007/11745853_14.  Google Scholar [4] D. J. Bernstein, C. Chuengsatiansup and T. Lange, Curve41417: Karatsuba revisited, in Cryptographic Hardware and Embedded Systems - CHES 2014 - 16th International Workshop, Busan, South Korea, September 23-26, 2014. Proceedings, Lecture Notes in Computer Science, 8731, Springer, 2014,316–334. doi: 10.1007/978-3-662-44709-3_18.  Google Scholar [5] D. J. Bernstein, C. Chuengsatiansup, T. Lange and P. Schwabe, Kummer strikes back: New DH speed records, in Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., December 7-11, 2014. Proceedings, Part I, Lecture Notes in Computer Science, 8873, Springer, 2014,317–337. doi: 10.1007/978-3-662-45611-8_17.  Google Scholar [6] D. J. Bernstein, N. Duif, T. Lange, P. Schwabe and B.-Y. Yang, High-speed high-security signatures, J. Cryptographic Engineering, 2 (2012), 77-89.  doi: 10.1007/978-3-642-23951-9_9.  Google Scholar [7] D. J. Bernstein and P. Schwabe, NEON crypto, in Cryptographic Hardware and Embedded Systems - CHES 2012 - 14th International Workshop, Leuven, Belgium, September 9-12, 2012. Proceedings, Lecture Notes in Computer Science, 7428, Springer, 2012,320–339. doi: 10.1007/978-3-642-33027-8_19.  Google Scholar [8] J. W. Bos, C. Costello, H. Hisil and and K. E. Lauter, Fast cryptography in genus 2, J. Cryptology, 29 (2016), 28-60.  doi: 10.1007/s00145-014-9188-7.  Google Scholar [9] T. Chou, Sandy2x: New Curve25519 speed records, in Selected Areas in Cryptography - SAC 2015 - 22nd International Conference, Sackville, NB, Canada, August 12-14, 2015, Revised Selected Papers, Lecture Notes in Computer Science, 9566, Springer, 2015,145–160. doi: 10.1007/978-3-319-31301-6_8.  Google Scholar [10] H. Cohen, G. Frey, R. Avanzi, C. Doche, T. Lange, K. Nguyen and F. Vercauteren, Handbook of Elliptic and Hyperelliptic Curve Cryptography, Chapman and Hall/CRC, 2005.  Google Scholar [11] C. Costello and P. Longa, Four$\mathbb{Q}$: Four-dimensional decompositions on a $\mathbb{Q}$-curve over the mersenne prime, in Advances in Cryptology - ASIACRYPT 2015 - 21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, November 29 - December 3, 2015, Proceedings, Part I, Lecture Notes in Computer Science, 9452, Springer, 2015,214–235. doi: 10.1007/978-3-662-48797-6_10.  Google Scholar [12] NIST Curves, Recommended elliptic curves for federal government use, http://csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf, 1999. Google Scholar [13] Michael Düll, Björn Haase, Gesine Hinterwälder, Michael Hutter, Christof Paar, Ana Helena Sánchez and Peter Schwabe, High-speed curve25519 on 8-bit, 16-bit, and 32-bit microcontrollers, Des. Codes Cryptogr., 77 (2015), 493-514.  doi: 10.1007/s10623-015-0087-1.  Google Scholar [14] A. Faz-Hernández and J. López, Fast implementation of Curve25519 using AVX2, in ATINCRYPT, Lecture Notes in Computer Science, 9230, Springer, 2015,329–345. doi: 10.1007/978-3-319-22174-8_18.  Google Scholar [15] D. Hankerson, A. J. Menezes and S. Vanstone, Guide to Elliptic Curve Cryptography, Springer, 2003. doi: 10.1016/s0012-365x(04)00102-5.  Google Scholar [16] National Institute for Standards and Technology, Digital signature standard, Federal Information Processing Standards Publication 186-2. 2000, https://csrc.nist.gov/csrc/media/publications/fips/186/2/archive/2000-01-27/documents/fips186-2.pdf. Google Scholar [17] P. Gaudry and É. Schost, Genus 2 point counting over prime fields, J. Symb. Comput., 47 (2012), 368-400.  doi: 10.1016/j.jsc.2011.09.003.  Google Scholar [18] R. Granger and M. Scott, Faster ECC over $\mathbb{F}_{2^521-1}$, in Public-Key Cryptography - PKC 2015 - 18th IACR International Conference on Practice and Theory in Public-Key Cryptography, Gaithersburg, MD, USA, March 30 - April 1, 2015, Proceedings, Lecture Notes in Computer Science, 9020, Springer, 2015,539–553. doi: 10.1007/978-3-662-46447-2_24.  Google Scholar [19] S. Gueron and V. Krasnov, Fast prime field elliptic-curve cryptography with 256-bit primes, J. Cryptographic Engineering, 5 (2015), 141-151.  doi: 10.1007/s13389-014-0090-x.  Google Scholar [20] S. Karati and P. Sarkar, Kummer for genus one over prime-order fields, J. Cryptology, 33 (2020), 92-129.  doi: 10.1007/s00145-019-09320-4.  Google Scholar [21] N. Koblitz, Elliptic curve cryptosystems, Math. Comp., 48 (1987), 203-209.  doi: 10.1090/S0025-5718-1987-0866109-5.  Google Scholar [22] N. Koblitz, Hyperelliptic cryptosystems, J. Cryptology, 1 (1989), 139-150.  doi: 10.1007/BF02252872.  Google Scholar [23] Optimized C library for EC operations on curve secp256k1, https://github.com/bitcoin-core/secp256k1., Google Scholar [24] A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1996.   Google Scholar [25] V. S. Miller, Use of elliptic curves in cryptography, in Advances in Cryptology - CRYPTO'85, Santa Barbara, California, USA, August 18-22, 1985, Proceedings, Springer Berlin Heidelberg, 1985,417–426. doi: 10.1007/3-540-39799-X_31.  Google Scholar [26] S. Nakamoto, Bitcoin: A peer-to-peer electronic cash system, http://bitcoin.org/bitcoin.pdf, 2009. Google Scholar [27] T. Oliveira, J. López, H. Hisil, A. Faz-Hernández and F. Rodríguez-Henríquez, How to (pre-)compute a ladder - improving the performance of X25519 and X448, in Selected Areas in Cryptography - SAC 2017 - 24th International Conference, Ottawa, ON, Canada, August 16-18, 2017, Revised Selected Papers, Lecture Notes in Computer Science, 10719, Springer, 2017,172–191. doi: 10.1007/978-3-319-72565-9_9.  Google Scholar [28] E. Ozturk, J. Guilford and V. Gopal, Large integer squaring on Intel architecture processors, $\mathsf {intel}$ white paper, https://www.intel.com/content/dam/www/public/us/en/documents/white-papers/large-integer-squaring-ia-paper.pdf, 2013. Google Scholar [29] E. Ozturk, J. Guilford, V. Gopal and W. Feghali, New instructions supporting large integer arithmetic on Intel architecture processors, $\mathsf {intel}$ white paper, https://www.intel.com/content/dam/www/public/us/en/documents/white-papers/ia-large-integer-arithmetic-paper.pdf, 2012. Google Scholar [30] Certicom Research, SEC2: Recommended elliptic curve domain parameters, http://www.secg.org/sec2-v2.pdf, 2010. Google Scholar

show all references

##### References:
 [1] D. F. Aranha, S. Paulo, L. M. Barreto, C. Geovandro, C. F. Pereira, and J. E. Ricardini, A note on high-security general-purpose elliptic curves, Cryptology ePrint Archive, Report 2013/647, 2013. Google Scholar [2] D. Bernstein and B.-Y. Yang, Fast constant-time gcd computation and modular inversion, IACR Transactions on Cryptographic Hardware and Embedded Systems, 2019 (2019), 340-398.   Google Scholar [3] D. J. Bernstein, Curve25519: New Diffie-Hellman speed records, in Public Key Cryptography - PKC 2006, 9th International Conference on Theory and Practice of Public-Key Cryptography, New York, NY, USA, April 24-26, 2006, Proceedings, Lecture Notes in Computer Science, 3958, Springer, 2006,207–228. doi: 10.1007/11745853_14.  Google Scholar [4] D. J. Bernstein, C. Chuengsatiansup and T. Lange, Curve41417: Karatsuba revisited, in Cryptographic Hardware and Embedded Systems - CHES 2014 - 16th International Workshop, Busan, South Korea, September 23-26, 2014. Proceedings, Lecture Notes in Computer Science, 8731, Springer, 2014,316–334. doi: 10.1007/978-3-662-44709-3_18.  Google Scholar [5] D. J. Bernstein, C. Chuengsatiansup, T. Lange and P. Schwabe, Kummer strikes back: New DH speed records, in Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., December 7-11, 2014. Proceedings, Part I, Lecture Notes in Computer Science, 8873, Springer, 2014,317–337. doi: 10.1007/978-3-662-45611-8_17.  Google Scholar [6] D. J. Bernstein, N. Duif, T. Lange, P. Schwabe and B.-Y. Yang, High-speed high-security signatures, J. Cryptographic Engineering, 2 (2012), 77-89.  doi: 10.1007/978-3-642-23951-9_9.  Google Scholar [7] D. J. Bernstein and P. Schwabe, NEON crypto, in Cryptographic Hardware and Embedded Systems - CHES 2012 - 14th International Workshop, Leuven, Belgium, September 9-12, 2012. Proceedings, Lecture Notes in Computer Science, 7428, Springer, 2012,320–339. doi: 10.1007/978-3-642-33027-8_19.  Google Scholar [8] J. W. Bos, C. Costello, H. Hisil and and K. E. Lauter, Fast cryptography in genus 2, J. Cryptology, 29 (2016), 28-60.  doi: 10.1007/s00145-014-9188-7.  Google Scholar [9] T. Chou, Sandy2x: New Curve25519 speed records, in Selected Areas in Cryptography - SAC 2015 - 22nd International Conference, Sackville, NB, Canada, August 12-14, 2015, Revised Selected Papers, Lecture Notes in Computer Science, 9566, Springer, 2015,145–160. doi: 10.1007/978-3-319-31301-6_8.  Google Scholar [10] H. Cohen, G. Frey, R. Avanzi, C. Doche, T. Lange, K. Nguyen and F. Vercauteren, Handbook of Elliptic and Hyperelliptic Curve Cryptography, Chapman and Hall/CRC, 2005.  Google Scholar [11] C. Costello and P. Longa, Four$\mathbb{Q}$: Four-dimensional decompositions on a $\mathbb{Q}$-curve over the mersenne prime, in Advances in Cryptology - ASIACRYPT 2015 - 21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, November 29 - December 3, 2015, Proceedings, Part I, Lecture Notes in Computer Science, 9452, Springer, 2015,214–235. doi: 10.1007/978-3-662-48797-6_10.  Google Scholar [12] NIST Curves, Recommended elliptic curves for federal government use, http://csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf, 1999. Google Scholar [13] Michael Düll, Björn Haase, Gesine Hinterwälder, Michael Hutter, Christof Paar, Ana Helena Sánchez and Peter Schwabe, High-speed curve25519 on 8-bit, 16-bit, and 32-bit microcontrollers, Des. Codes Cryptogr., 77 (2015), 493-514.  doi: 10.1007/s10623-015-0087-1.  Google Scholar [14] A. Faz-Hernández and J. López, Fast implementation of Curve25519 using AVX2, in ATINCRYPT, Lecture Notes in Computer Science, 9230, Springer, 2015,329–345. doi: 10.1007/978-3-319-22174-8_18.  Google Scholar [15] D. Hankerson, A. J. Menezes and S. Vanstone, Guide to Elliptic Curve Cryptography, Springer, 2003. doi: 10.1016/s0012-365x(04)00102-5.  Google Scholar [16] National Institute for Standards and Technology, Digital signature standard, Federal Information Processing Standards Publication 186-2. 2000, https://csrc.nist.gov/csrc/media/publications/fips/186/2/archive/2000-01-27/documents/fips186-2.pdf. Google Scholar [17] P. Gaudry and É. Schost, Genus 2 point counting over prime fields, J. Symb. Comput., 47 (2012), 368-400.  doi: 10.1016/j.jsc.2011.09.003.  Google Scholar [18] R. Granger and M. Scott, Faster ECC over $\mathbb{F}_{2^521-1}$, in Public-Key Cryptography - PKC 2015 - 18th IACR International Conference on Practice and Theory in Public-Key Cryptography, Gaithersburg, MD, USA, March 30 - April 1, 2015, Proceedings, Lecture Notes in Computer Science, 9020, Springer, 2015,539–553. doi: 10.1007/978-3-662-46447-2_24.  Google Scholar [19] S. Gueron and V. Krasnov, Fast prime field elliptic-curve cryptography with 256-bit primes, J. Cryptographic Engineering, 5 (2015), 141-151.  doi: 10.1007/s13389-014-0090-x.  Google Scholar [20] S. Karati and P. Sarkar, Kummer for genus one over prime-order fields, J. Cryptology, 33 (2020), 92-129.  doi: 10.1007/s00145-019-09320-4.  Google Scholar [21] N. Koblitz, Elliptic curve cryptosystems, Math. Comp., 48 (1987), 203-209.  doi: 10.1090/S0025-5718-1987-0866109-5.  Google Scholar [22] N. Koblitz, Hyperelliptic cryptosystems, J. Cryptology, 1 (1989), 139-150.  doi: 10.1007/BF02252872.  Google Scholar [23] Optimized C library for EC operations on curve secp256k1, https://github.com/bitcoin-core/secp256k1., Google Scholar [24] A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1996.   Google Scholar [25] V. S. Miller, Use of elliptic curves in cryptography, in Advances in Cryptology - CRYPTO'85, Santa Barbara, California, USA, August 18-22, 1985, Proceedings, Springer Berlin Heidelberg, 1985,417–426. doi: 10.1007/3-540-39799-X_31.  Google Scholar [26] S. Nakamoto, Bitcoin: A peer-to-peer electronic cash system, http://bitcoin.org/bitcoin.pdf, 2009. Google Scholar [27] T. Oliveira, J. López, H. Hisil, A. Faz-Hernández and F. Rodríguez-Henríquez, How to (pre-)compute a ladder - improving the performance of X25519 and X448, in Selected Areas in Cryptography - SAC 2017 - 24th International Conference, Ottawa, ON, Canada, August 16-18, 2017, Revised Selected Papers, Lecture Notes in Computer Science, 10719, Springer, 2017,172–191. doi: 10.1007/978-3-319-72565-9_9.  Google Scholar [28] E. Ozturk, J. Guilford and V. Gopal, Large integer squaring on Intel architecture processors, $\mathsf {intel}$ white paper, https://www.intel.com/content/dam/www/public/us/en/documents/white-papers/large-integer-squaring-ia-paper.pdf, 2013. Google Scholar [29] E. Ozturk, J. Guilford, V. Gopal and W. Feghali, New instructions supporting large integer arithmetic on Intel architecture processors, $\mathsf {intel}$ white paper, https://www.intel.com/content/dam/www/public/us/en/documents/white-papers/ia-large-integer-arithmetic-paper.pdf, 2012. Google Scholar [30] Certicom Research, SEC2: Recommended elliptic curve domain parameters, http://www.secg.org/sec2-v2.pdf, 2010. Google Scholar
Single carry chain for $\mathsf {mulSCC}$
Two independent carry chains for $\mathsf {mulSLDCC}$
The various algorithms for multiplication/squaring and reduction described in this paper
 $\mathsf {algorithm}$ $\mathsf {feature}$ $\mathsf {mulSLDCC}$/$\mathsf {sqrSLDCC}$ generalizes [28,29] $\mathsf {mulSLa}$/$\mathsf {sqrSLa}$ new $\mathsf {mulUSL}$/$\mathsf {sqrUSL}$ generalizes [6] $\mathsf {mulUSLa}$/$\mathsf {sqrUSLa}$ new $\mathsf {reduceSLMP}$ generalizes [5] $\mathsf {reduceSLPMP}$ new $\mathsf {reduceSLPMPa}$ generalizes [6,4-limb] $\mathsf {reduceSL}$ new $\mathsf {reduceUSL}$ generalizes [9,5-limb] $\mathsf {reduceUSLA}$ generalizes [6,5-limb] $\mathsf {reduceUSLB}$ new
 $\mathsf {algorithm}$ $\mathsf {feature}$ $\mathsf {mulSLDCC}$/$\mathsf {sqrSLDCC}$ generalizes [28,29] $\mathsf {mulSLa}$/$\mathsf {sqrSLa}$ new $\mathsf {mulUSL}$/$\mathsf {sqrUSL}$ generalizes [6] $\mathsf {mulUSLa}$/$\mathsf {sqrUSLa}$ new $\mathsf {reduceSLMP}$ generalizes [5] $\mathsf {reduceSLPMP}$ new $\mathsf {reduceSLPMPa}$ generalizes [6,4-limb] $\mathsf {reduceSL}$ new $\mathsf {reduceUSL}$ generalizes [9,5-limb] $\mathsf {reduceUSLA}$ generalizes [6,5-limb] $\mathsf {reduceUSLB}$ new
The primes considered in this work
 $\mathsf {prime}$ $\mathsf {curve(s)}$ $2^{127}-1$ $\mathsf {Kummer}_2$ [5], Four$\mathbb{Q}$ [11] $2^{221}-3$ M-221 [1] $2^{222}-117$ E-222 [1] $2^{251}-9$ Curve1174 [1], KL2519(81,20) [20] $2^{255}-19$ Curve25519 [3], KL25519(82,77) [20] $2^{256}-2^{32}-977$ secp256k1 [30] $2^{266}-3$ KL2663(260,139) [20] $2^{382}-105$ E-382 [1] $2^{383}-187$ M-383 [1] $2^{414}-17$ Curve41417 [4] $2^{511}-187$ M-511 [1] $2^{512}-569$ - $2^{521}-1$ P-521 [16], E-521 [1] $2^{607}-1$ -
 $\mathsf {prime}$ $\mathsf {curve(s)}$ $2^{127}-1$ $\mathsf {Kummer}_2$ [5], Four$\mathbb{Q}$ [11] $2^{221}-3$ M-221 [1] $2^{222}-117$ E-222 [1] $2^{251}-9$ Curve1174 [1], KL2519(81,20) [20] $2^{255}-19$ Curve25519 [3], KL25519(82,77) [20] $2^{256}-2^{32}-977$ secp256k1 [30] $2^{266}-3$ KL2663(260,139) [20] $2^{382}-105$ E-382 [1] $2^{383}-187$ M-383 [1] $2^{414}-17$ Curve41417 [4] $2^{511}-187$ M-511 [1] $2^{512}-569$ - $2^{521}-1$ P-521 [16], E-521 [1] $2^{607}-1$ -
The primes considered in this work and their saturated and unsaturated limb representations
 $\mathsf {prime}$ $m$ $\delta$ $\mathsf {unsaturated\;limb}$ $\mathsf {saturated\;limb}$ $\kappa$ $\eta$ $\nu$ $\kappa$ $\eta$ $\nu$ $2^{127}-1$ 127 1 3 43 41 2 64 63 $2^{221}-3$ 221 3 4 56 53 4 64 29 $2^{222}-117$ 222 117 4 56 54 4 64 30 $2^{251}-9$ 251 9 5 51 47 4 64 59 $2^{255}-19$ 255 19 5 51 51 4 64 63 $2^{256}-2^{32}-977$ 256 $2^{32}+977$ 5 52 48 4 64 64 $2^{266}-3$ 266 3 5 54 50 5 64 10 $2^{382}-105$ 382 105 7 55 52 6 64 62 $2^{383}-187$ 383 187 7 55 53 6 64 63 $2^{414}-17$ 414 17 8 52 50 7 64 30 $2^{511}-187$ 511 187 9 57 55 8 64 63 $2^{512}-569$ 512 569 9 57 56 8 64 64 $2^{521}-1$ 521 1 9 58 57 9 64 9 $2^{607}-1$ 607 1 10 61 58 10 64 31
 $\mathsf {prime}$ $m$ $\delta$ $\mathsf {unsaturated\;limb}$ $\mathsf {saturated\;limb}$ $\kappa$ $\eta$ $\nu$ $\kappa$ $\eta$ $\nu$ $2^{127}-1$ 127 1 3 43 41 2 64 63 $2^{221}-3$ 221 3 4 56 53 4 64 29 $2^{222}-117$ 222 117 4 56 54 4 64 30 $2^{251}-9$ 251 9 5 51 47 4 64 59 $2^{255}-19$ 255 19 5 51 51 4 64 63 $2^{256}-2^{32}-977$ 256 $2^{32}+977$ 5 52 48 4 64 64 $2^{266}-3$ 266 3 5 54 50 5 64 10 $2^{382}-105$ 382 105 7 55 52 6 64 62 $2^{383}-187$ 383 187 7 55 53 6 64 63 $2^{414}-17$ 414 17 8 52 50 7 64 30 $2^{511}-187$ 511 187 9 57 55 8 64 63 $2^{512}-569$ 512 569 9 57 56 8 64 64 $2^{521}-1$ 521 1 9 58 57 9 64 9 $2^{607}-1$ 607 1 10 61 58 10 64 31
Classification of primes for application of $\mathsf {reduceUSL}$, $\mathsf {reduceUSLA}$ or $\mathsf {reduceUSLB}$
 prime $2^{127}-1$ $2^{221}-3$ $2^{222}-117$ $2^{251}-9$ $2^{255}-19$ $2^{256}-2^{32}-977$ $2^{266}-3$ type A A A A A A A prime $2^{382}-105$ $2^{383}-187$ $2^{414}-17$ $2^{511}-187$ $2^{512}-569$ $2^{521}-1$ $2^{607}-1$ type B B A G G A G
 prime $2^{127}-1$ $2^{221}-3$ $2^{222}-117$ $2^{251}-9$ $2^{255}-19$ $2^{256}-2^{32}-977$ $2^{266}-3$ type A A A A A A A prime $2^{382}-105$ $2^{383}-187$ $2^{414}-17$ $2^{511}-187$ $2^{512}-569$ $2^{521}-1$ $2^{607}-1$ type B B A G G A G
Comparison of timings of various field arithmetic algorithms on Haswell
 $\mathsf {field}$ $\mathsf {implementation type - maa}$ $\mathsf {previous}$ $\mathsf {this\;work}$ $\mathsf {algorithm}$ $\mathsf {sup}$ $\mathbb{F}_{2^{127}-1}$ (32, 32, 2797) [5] (32, 30, 2503) $\mathsf {farith-SLMP}$ (0, 10.3, 10.5) $\mathbb{F}_{2^{221}-3}$ - (54, 45, 8082) $\mathsf {farith-USLA}$ - (57, 56, 9957) $\mathsf {farith-USL}$ $\mathbb{F}_{2^{222}-117}$ - (58, 46, 8385) $\mathsf {farith-USLA}$ - (64, 55, 10798) $\mathsf {farith-USL}$ $\mathbb{F}_{2^{251}-9}$ (72, 55, 12202) [20] (52, 46, 11245) $\mathsf {farith-SLa}$ (27.8, 16.35, 7.8) (78, 55, 11803) $\mathsf {farith-USLA}$ $\mathbb{F}_{2^{255}-19}$ (72, 51, 12359) [6,5-limb] (71, 50, 11854) $\mathsf {farith-USLA}$ (1.4, 2.0, 4.1) (77, 64, 15880) [6,4-limb] (62, 54, 12393) $\mathsf {farith-SLa}$ $\mathbb{F}_{2^{256}-2^{32}-977}$ (86, 62, 20209) [23] (55, 51, 12809) $\mathsf {farith-SLa}$ (36.0, 17.7, 36.6) (70, 63, 17202) $\mathsf {farith-USL}$ $\mathbb{F}_{2^{266}-3}$ (72, 52, 12705) [20] (71, 51, 12413) $\mathsf {farith-USLA}$ (1.4, 2.0, 2.3) (85, 50, 14892) $\mathsf {farith-USL}$ $\mathbb{F}_{2^{382}-105}$ - (119,100, 33437) $\mathsf {farith-USLB}$ - (127,102, 39722) $\mathsf {farith-USL}$ $\mathbb{F}_{2^{383}-187}$ - (119,101, 33699) $\mathsf {farith-USLB}$ - (127,102, 39825) $\mathsf {farith-USL}$ $\mathbb{F}_{2^{414}-17}$ - (161,117, 43218) $\mathsf {farith-USLA}$ - (130,109, 44239) $\mathsf {farith-USLa}$ $\mathbb{F}_{2^{511}-187}$ - (199,144, 72804) $\mathsf {farith-USL}$ - $\mathbb{F}_{2^{512}-569}$ - (199,144, 73771) $\mathsf {farith-USL}$ - $\mathbb{F}_{2^{521}-1}$ (210,166, 76298) [18] (177,129, 62244) $\mathsf {farith-USLA}$ (15.7, 22.3, 18.4) (178,132, 71546) $\mathsf {farith-USL}$ $\mathbb{F}_{2^{607}-1}$ - (230,156, 94149) $\mathsf {farith-USL}$ -
 $\mathsf {field}$ $\mathsf {implementation type - maa}$ $\mathsf {previous}$ $\mathsf {this\;work}$ $\mathsf {algorithm}$ $\mathsf {sup}$ $\mathbb{F}_{2^{127}-1}$ (32, 32, 2797) [5] (32, 30, 2503) $\mathsf {farith-SLMP}$ (0, 10.3, 10.5) $\mathbb{F}_{2^{221}-3}$ - (54, 45, 8082) $\mathsf {farith-USLA}$ - (57, 56, 9957) $\mathsf {farith-USL}$ $\mathbb{F}_{2^{222}-117}$ - (58, 46, 8385) $\mathsf {farith-USLA}$ - (64, 55, 10798) $\mathsf {farith-USL}$ $\mathbb{F}_{2^{251}-9}$ (72, 55, 12202) [20] (52, 46, 11245) $\mathsf {farith-SLa}$ (27.8, 16.35, 7.8) (78, 55, 11803) $\mathsf {farith-USLA}$ $\mathbb{F}_{2^{255}-19}$ (72, 51, 12359) [6,5-limb] (71, 50, 11854) $\mathsf {farith-USLA}$ (1.4, 2.0, 4.1) (77, 64, 15880) [6,4-limb] (62, 54, 12393) $\mathsf {farith-SLa}$ $\mathbb{F}_{2^{256}-2^{32}-977}$ (86, 62, 20209) [23] (55, 51, 12809) $\mathsf {farith-SLa}$ (36.0, 17.7, 36.6) (70, 63, 17202) $\mathsf {farith-USL}$ $\mathbb{F}_{2^{266}-3}$ (72, 52, 12705) [20] (71, 51, 12413) $\mathsf {farith-USLA}$ (1.4, 2.0, 2.3) (85, 50, 14892) $\mathsf {farith-USL}$ $\mathbb{F}_{2^{382}-105}$ - (119,100, 33437) $\mathsf {farith-USLB}$ - (127,102, 39722) $\mathsf {farith-USL}$ $\mathbb{F}_{2^{383}-187}$ - (119,101, 33699) $\mathsf {farith-USLB}$ - (127,102, 39825) $\mathsf {farith-USL}$ $\mathbb{F}_{2^{414}-17}$ - (161,117, 43218) $\mathsf {farith-USLA}$ - (130,109, 44239) $\mathsf {farith-USLa}$ $\mathbb{F}_{2^{511}-187}$ - (199,144, 72804) $\mathsf {farith-USL}$ - $\mathbb{F}_{2^{512}-569}$ - (199,144, 73771) $\mathsf {farith-USL}$ - $\mathbb{F}_{2^{521}-1}$ (210,166, 76298) [18] (177,129, 62244) $\mathsf {farith-USLA}$ (15.7, 22.3, 18.4) (178,132, 71546) $\mathsf {farith-USL}$ $\mathbb{F}_{2^{607}-1}$ - (230,156, 94149) $\mathsf {farith-USL}$ -
Comparison of $\mathsf {maa}$-timings of various field arithmetic algorithms on Skylake
 $\mathsf {field}$ $\mathsf {implementation type - maa}$ $\mathsf {previous}$ $\mathsf {this\;work}$ $\mathsf {algorithm}$ $\mathsf {sup}$ $\mathbb{F}_{2^{127}-1}$ (27, 26, 2505)k_ge [5] (26, 24, 2263) $\mathsf {farith-SLMP}$ (3.7, 7.7, 9.7) $\mathbb{F}_{2^{221}-3}$ - (58, 41, 7949) $\mathsf {farith-USLA}$ - (60, 43, 8936) $\mathsf {farith-USL}$ $\mathbb{F}_{2^{222}-117}$ - (55, 42, 8033) $\mathsf {farith-USLA}$ - (60, 44, 10067) $\mathsf {farith-USL}$ $\mathbb{F}_{2^{251}-9}$ (66, 65, 13632)k_ge [20] (50, 46, 11783) $\mathsf {farith-SLa}$ (24.2, 29.2, 13.6) (65, 52, 12415) $\mathsf {farith-USLA}$ $\mathbb{F}_{2^{255}-19}$ (67, 48, 13223)k_ge [6, 5-limb] (65, 47, 12671) $\mathsf {farith-USLA}$ (3.0, 2.1, 4.2) (67, 58, 13901)k_ge [6, 4-limb] (57, 52, 12906) $\mathsf {farith-SLa}$ $\mathbb{F}_{2^{256}-2^{32}-977}$ (74, 54, 18391)k_ge [23] (52, 49, 13242) $\mathsf {farith-SLa}$ (29.7, 9.3, 28.0) (74, 63, 15565) $\mathsf {farith-USLa}$ $\mathbb{F}_{2^{266}-3}$ (66, 50, 14472)k_ge [20] (65, 48, 13350) $\mathsf {farith-USLA}$ (1.51, 4.0, 7.8) (71, 48, 14651) $\mathsf {farith-USL}$ $\mathbb{F}_{2^{382}-105}$ - (107, 92, 30419) $\mathsf {farith-USLB}$ - (115, 93, 35465) $\mathsf {farith-USL}$ $\mathbb{F}_{2^{383}-187}$ - (107, 92, 30680) $\mathsf {farith-USLB}$ - (115, 93, 35552) $\mathsf {farith-USL}$ $\mathbb{F}_{2^{414}-17}$ - (127, 98, 38096) $\mathsf {farith-USLA}$ - (126, 97, 39371) $\mathsf {farith-USLa}$ $\mathbb{F}_{2^{511}-187}$ - (179, 131, 66039) $\mathsf {farith-USL}$ - $\mathbb{F}_{2^{512}-569}$ - (179, 131, 66808) $\mathsf {farith-USL}$ - $\mathbb{F}_{2^{521}-1}$ (184, 142, 64924)k_ge [18] (150, 116, 54790) $\mathsf {farith-USLA}$ (18.5, 18.3, 15.6) (162, 121, 63938) $\mathsf {farith-USL}$ $\mathbb{F}_{2^{607}-1}$ - (202, 137, 83587) $\mathsf {farith-USL}$ -
 $\mathsf {field}$ $\mathsf {implementation type - maa}$ $\mathsf {previous}$ $\mathsf {this\;work}$ $\mathsf {algorithm}$ $\mathsf {sup}$ $\mathbb{F}_{2^{127}-1}$ (27, 26, 2505)k_ge [5] (26, 24, 2263) $\mathsf {farith-SLMP}$ (3.7, 7.7, 9.7) $\mathbb{F}_{2^{221}-3}$ - (58, 41, 7949) $\mathsf {farith-USLA}$ - (60, 43, 8936) $\mathsf {farith-USL}$ $\mathbb{F}_{2^{222}-117}$ - (55, 42, 8033) $\mathsf {farith-USLA}$ - (60, 44, 10067) $\mathsf {farith-USL}$ $\mathbb{F}_{2^{251}-9}$ (66, 65, 13632)k_ge [20] (50, 46, 11783) $\mathsf {farith-SLa}$ (24.2, 29.2, 13.6) (65, 52, 12415) $\mathsf {farith-USLA}$ $\mathbb{F}_{2^{255}-19}$ (67, 48, 13223)k_ge [6, 5-limb] (65, 47, 12671) $\mathsf {farith-USLA}$ (3.0, 2.1, 4.2) (67, 58, 13901)k_ge [6, 4-limb] (57, 52, 12906) $\mathsf {farith-SLa}$ $\mathbb{F}_{2^{256}-2^{32}-977}$ (74, 54, 18391)k_ge [23] (52, 49, 13242) $\mathsf {farith-SLa}$ (29.7, 9.3, 28.0) (74, 63, 15565) $\mathsf {farith-USLa}$ $\mathbb{F}_{2^{266}-3}$ (66, 50, 14472)k_ge [20] (65, 48, 13350) $\mathsf {farith-USLA}$ (1.51, 4.0, 7.8) (71, 48, 14651) $\mathsf {farith-USL}$ $\mathbb{F}_{2^{382}-105}$ - (107, 92, 30419) $\mathsf {farith-USLB}$ - (115, 93, 35465) $\mathsf {farith-USL}$ $\mathbb{F}_{2^{383}-187}$ - (107, 92, 30680) $\mathsf {farith-USLB}$ - (115, 93, 35552) $\mathsf {farith-USL}$ $\mathbb{F}_{2^{414}-17}$ - (127, 98, 38096) $\mathsf {farith-USLA}$ - (126, 97, 39371) $\mathsf {farith-USLa}$ $\mathbb{F}_{2^{511}-187}$ - (179, 131, 66039) $\mathsf {farith-USL}$ - $\mathbb{F}_{2^{512}-569}$ - (179, 131, 66808) $\mathsf {farith-USL}$ - $\mathbb{F}_{2^{521}-1}$ (184, 142, 64924)k_ge [18] (150, 116, 54790) $\mathsf {farith-USLA}$ (18.5, 18.3, 15.6) (162, 121, 63938) $\mathsf {farith-USL}$ $\mathbb{F}_{2^{607}-1}$ - (202, 137, 83587) $\mathsf {farith-USL}$ -
Comparison of $\mathsf {maax}$-timings of various field arithmetic algorithms on Skylake
 $\mathsf {field}$ $\mathsf {implementation type - maax}$ $\mathsf {previous}$ $\mathsf {this\;work}$ $\mathsf {reduction}$ $\mathsf {sup}$ $\mathbb{F}_{2^{127}-1}$ - (26, 24, 2154) $\mathsf {farithx-SLMP}$ - $\mathbb{F}_{2^{221}-3}$ - (62, 43, 7728) $\mathsf {farithx-SLPMP}$ - $\mathbb{F}_{2^{222}-117}$ - (64, 40, 7967) $\mathsf {farithx-SLPMP}$ - $\mathbb{F}_{2^{251}-9}$ - (54, 47, 8784) $\mathsf {farithx-SLPMP}$ - $\mathbb{F}_{2^{255}-19}$ (62, 49, 12170) [27] (54, 42, 9301) $\mathsf {farithx-SLPMP}$ (12.9, 14.3, 23.6) $\mathbb{F}_{2^{256}-2^{32}-977}$ - (65, 53, 11501) $\mathsf {farithx-SLPMP}$ - $\mathbb{F}_{2^{266}-3}$ - (65, 53, 12938) $\mathsf {farithx-SLPMP}$ - $\mathbb{F}_{2^{382}-105}$ - (81, 69, 24549) $\mathsf {farithx-SLPMP}$ - $\mathbb{F}_{2^{383}-187}$ - (81, 69, 24628) $\mathsf {farithx-SLPMP}$ - $\mathbb{F}_{2^{414}-17}$ - (97, 80, 30972) $\mathsf {farithx-SLPMP}$ - $\mathbb{F}_{2^{511}-187}$ - (118,101, 47062) $\mathsf {farithx-SLPMP}$ - $\mathbb{F}_{2^{512}-569}$ - (125,106, 49713) $\mathsf {farithx-SLPMP}$ - $\mathbb{F}_{2^{521}-1}$ - (128,108, 53828) $\mathsf {farithx-SLMP}$ - $\mathbb{F}_{2^{607}-1}$ - (159,129, 74442) $\mathsf {farithx-SLMP}$ -
 $\mathsf {field}$ $\mathsf {implementation type - maax}$ $\mathsf {previous}$ $\mathsf {this\;work}$ $\mathsf {reduction}$ $\mathsf {sup}$ $\mathbb{F}_{2^{127}-1}$ - (26, 24, 2154) $\mathsf {farithx-SLMP}$ - $\mathbb{F}_{2^{221}-3}$ - (62, 43, 7728) $\mathsf {farithx-SLPMP}$ - $\mathbb{F}_{2^{222}-117}$ - (64, 40, 7967) $\mathsf {farithx-SLPMP}$ - $\mathbb{F}_{2^{251}-9}$ - (54, 47, 8784) $\mathsf {farithx-SLPMP}$ - $\mathbb{F}_{2^{255}-19}$ (62, 49, 12170) [27] (54, 42, 9301) $\mathsf {farithx-SLPMP}$ (12.9, 14.3, 23.6) $\mathbb{F}_{2^{256}-2^{32}-977}$ - (65, 53, 11501) $\mathsf {farithx-SLPMP}$ - $\mathbb{F}_{2^{266}-3}$ - (65, 53, 12938) $\mathsf {farithx-SLPMP}$ - $\mathbb{F}_{2^{382}-105}$ - (81, 69, 24549) $\mathsf {farithx-SLPMP}$ - $\mathbb{F}_{2^{383}-187}$ - (81, 69, 24628) $\mathsf {farithx-SLPMP}$ - $\mathbb{F}_{2^{414}-17}$ - (97, 80, 30972) $\mathsf {farithx-SLPMP}$ - $\mathbb{F}_{2^{511}-187}$ - (118,101, 47062) $\mathsf {farithx-SLPMP}$ - $\mathbb{F}_{2^{512}-569}$ - (125,106, 49713) $\mathsf {farithx-SLPMP}$ - $\mathbb{F}_{2^{521}-1}$ - (128,108, 53828) $\mathsf {farithx-SLMP}$ - $\mathbb{F}_{2^{607}-1}$ - (159,129, 74442) $\mathsf {farithx-SLMP}$ -
Timings for integer multiplication and squaring in the $\mathsf {maax}$ setting on Skylake
 field(s) (mult, sqr) $\mathbb{F}_{2^{127}-1}$ (14, 13) $\mathbb{F}_{2^{221}-3}$, $\mathbb{F}_{2^{222}-117}$ (27, 23) $\mathbb{F}_{2^{251}-9}$, $\mathbb{F}_{2^{255}-19}$, $\mathbb{F}_{2^{256}-2^{32}-977}$ (30, 25) $\mathbb{F}_{2^{266}-3}$ (42, 33) $\mathbb{F}_{2^{382}-105}$, $\mathbb{F}_{2^{383}-187}$ (59, 50) $\mathbb{F}_{2^{414}-17}$ (73, 65) $\mathbb{F}_{2^{511}-187}$, $\mathbb{F}_{2^{512}-569}$ (90, 82) $\mathbb{F}_{2^{521}-1}$ (109, 96) $\mathbb{F}_{2^{607}-1}$ (143,113)
 field(s) (mult, sqr) $\mathbb{F}_{2^{127}-1}$ (14, 13) $\mathbb{F}_{2^{221}-3}$, $\mathbb{F}_{2^{222}-117}$ (27, 23) $\mathbb{F}_{2^{251}-9}$, $\mathbb{F}_{2^{255}-19}$, $\mathbb{F}_{2^{256}-2^{32}-977}$ (30, 25) $\mathbb{F}_{2^{266}-3}$ (42, 33) $\mathbb{F}_{2^{382}-105}$, $\mathbb{F}_{2^{383}-187}$ (59, 50) $\mathbb{F}_{2^{414}-17}$ (73, 65) $\mathbb{F}_{2^{511}-187}$, $\mathbb{F}_{2^{512}-569}$ (90, 82) $\mathbb{F}_{2^{521}-1}$ (109, 96) $\mathbb{F}_{2^{607}-1}$ (143,113)
 [1] Huy Dinh, Harbir Antil, Yanlai Chen, Elena Cherkaev, Akil Narayan. Model reduction for fractional elliptic problems using Kato's formula. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021004 [2] Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069 [3] 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 [4] 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 [5] Jean-François Biasse. Improvements in the computation of ideal class groups of imaginary quadratic number fields. Advances in Mathematics of Communications, 2010, 4 (2) : 141-154. doi: 10.3934/amc.2010.4.141 [6] 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 [7] 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 [8] 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 [9] Hirofumi Notsu, Masato Kimura. Symmetry and positive definiteness of the tensor-valued spring constant derived from P1-FEM for the equations of linear elasticity. Networks & Heterogeneous Media, 2014, 9 (4) : 617-634. doi: 10.3934/nhm.2014.9.617 [10] José Raúl Quintero, Juan Carlos Muñoz Grajales. On the existence and computation of periodic travelling waves for a 2D water wave model. Communications on Pure & Applied Analysis, 2018, 17 (2) : 557-578. doi: 10.3934/cpaa.2018030 [11] Peter Benner, Jens Saak, M. Monir Uddin. Balancing based model reduction for structured index-2 unstable descriptor systems with application to flow control. Numerical Algebra, Control & Optimization, 2016, 6 (1) : 1-20. doi: 10.3934/naco.2016.6.1 [12] Christophe Zhang. Internal rapid stabilization of a 1-D linear transport equation with a scalar feedback. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021006 [13] Z. Reichstein and B. Youssin. Parusinski's "Key Lemma" via algebraic geometry. Electronic Research Announcements, 1999, 5: 136-145. [14] Ronald E. Mickens. Positivity preserving discrete model for the coupled ODE's modeling glycolysis. Conference Publications, 2003, 2003 (Special) : 623-629. doi: 10.3934/proc.2003.2003.623 [15] Elvise Berchio, Filippo Gazzola, Dario Pierotti. Nodal solutions to critical growth elliptic problems under Steklov boundary conditions. Communications on Pure & Applied Analysis, 2009, 8 (2) : 533-557. doi: 10.3934/cpaa.2009.8.533 [16] Bernold Fiedler, Carlos Rocha, Matthias Wolfrum. Sturm global attractors for $S^1$-equivariant parabolic equations. Networks & Heterogeneous Media, 2012, 7 (4) : 617-659. doi: 10.3934/nhm.2012.7.617 [17] Arunima Bhattacharya, Micah Warren. $C^{2, \alpha}$ estimates for solutions to almost Linear elliptic equations. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021024 [18] Enkhbat Rentsen, Battur Gompil. Generalized Nash equilibrium problem based on malfatti's problem. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 209-220. doi: 10.3934/naco.2020022 [19] Livia Betz, Irwin Yousept. Optimal control of elliptic variational inequalities with bounded and unbounded operators. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021009 [20] Jiangxing Wang. Convergence analysis of an accurate and efficient method for nonlinear Maxwell's equations. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2429-2440. doi: 10.3934/dcdsb.2020185

2019 Impact Factor: 0.734

## Tools

Article outline

Figures and Tables