# American Institute of Mathematical Sciences

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] Cheng Peng, Zhaohui Tang, Weihua Gui, Qing Chen, Jing He. A bidirectional weighted boundary distance algorithm for time series similarity computation based on optimized sliding window size. Journal of Industrial & Management Optimization, 2021, 17 (1) : 205-220. doi: 10.3934/jimo.2019107 [2] Hoang The Tuan. On the asymptotic behavior of solutions to time-fractional elliptic equations driven by a multiplicative white noise. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020318 [3] Peng Luo. Comparison theorem for diagonally quadratic BSDEs. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020374 [4] Zhiyan Ding, Qin Li, Jianfeng Lu. Ensemble Kalman Inversion for nonlinear problems: Weights, consistency, and variance bounds. Foundations of Data Science, 2020  doi: 10.3934/fods.2020018 [5] Javier Fernández, Cora Tori, Marcela Zuccalli. Lagrangian reduction of nonholonomic discrete mechanical systems by stages. Journal of Geometric Mechanics, 2020, 12 (4) : 607-639. doi: 10.3934/jgm.2020029 [6] Shuang Chen, Jinqiao Duan, Ji Li. Effective reduction of a three-dimensional circadian oscillator model. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020349 [7] Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056 [8] Chao Wang, Qihuai Liu, Zhiguo Wang. Periodic bouncing solutions for Hill's type sub-linear oscillators with obstacles. Communications on Pure & Applied Analysis, 2021, 20 (1) : 281-300. doi: 10.3934/cpaa.2020266 [9] Hua Chen, Yawei Wei. Multiple solutions for nonlinear cone degenerate elliptic equations. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020272 [10] 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 [11] 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 [12] Sören Bartels, Jakob Keck. Adaptive time stepping in elastoplasticity. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 71-88. doi: 10.3934/dcdss.2020323 [13] Annegret Glitzky, Matthias Liero, Grigor Nika. Dimension reduction of thermistor models for large-area organic light-emitting diodes. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020460 [14] Tien-Yu Lin, Bhaba R. Sarker, Chien-Jui Lin. An optimal setup cost reduction and lot size for economic production quantity model with imperfect quality and quantity discounts. Journal of Industrial & Management Optimization, 2021, 17 (1) : 467-484. doi: 10.3934/jimo.2020043 [15] João Marcos do Ó, Bruno Ribeiro, Bernhard Ruf. Hamiltonian elliptic systems in dimension two with arbitrary and double exponential growth conditions. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 277-296. doi: 10.3934/dcds.2020138 [16] 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 [17] 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, , () : -. doi: 10.3934/ipi.2020076 [18] Emre Esentürk, Juan Velazquez. Large time behavior of exchange-driven growth. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 747-775. doi: 10.3934/dcds.2020299 [19] Yichen Zhang, Meiqiang Feng. A coupled $p$-Laplacian elliptic system: Existence, uniqueness and asymptotic behavior. Electronic Research Archive, 2020, 28 (4) : 1419-1438. doi: 10.3934/era.2020075 [20] Zedong Yang, Guotao Wang, Ravi P. Agarwal, Haiyong Xu. Existence and nonexistence of entire positive radial solutions for a class of Schrödinger elliptic systems involving a nonlinear operator. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020436

2019 Impact Factor: 0.734