# American Institute of Mathematical Sciences

doi: 10.3934/amc.2020113
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

## 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 Early access 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] Kwang Ho Kim, Junyop Choe, Song Yun Kim, Namsu Kim, Sekung Hong. Speeding up regular elliptic curve scalar multiplication without precomputation. Advances in Mathematics of Communications, 2020, 14 (4) : 703-726. doi: 10.3934/amc.2020090 [2] Michael J. Jacobson, Jr., Monireh Rezai Rad, Renate Scheidler. Comparison of scalar multiplication on real hyperelliptic curves. Advances in Mathematics of Communications, 2014, 8 (4) : 389-406. doi: 10.3934/amc.2014.8.389 [3] J.-M. Deshouillers, G. Effinger, H. te Riele and D. Zinoviev. A complete Vinogradov 3-primes theorem under the Riemann hypothesis. Electronic Research Announcements, 1997, 3: 99-104. [4] Diego F. Aranha, Ricardo Dahab, Julio López, Leonardo B. Oliveira. Efficient implementation of elliptic curve cryptography in wireless sensors. Advances in Mathematics of Communications, 2010, 4 (2) : 169-187. doi: 10.3934/amc.2010.4.169 [5] Ely Kerman. On primes and period growth for Hamiltonian diffeomorphisms. Journal of Modern Dynamics, 2012, 6 (1) : 41-58. doi: 10.3934/jmd.2012.6.41 [6] Gábor Székelyhidi, Ben Weinkove. On a constant rank theorem for nonlinear elliptic PDEs. Discrete & Continuous Dynamical Systems, 2016, 36 (11) : 6523-6532. doi: 10.3934/dcds.2016081 [7] Bertrand Lods. Variational characterizations of the effective multiplication factor of a nuclear reactor core. Kinetic & Related Models, 2009, 2 (2) : 307-331. doi: 10.3934/krm.2009.2.307 [8] Christopher C. Tisdell. Reimagining multiplication as diagrammatic and dynamic concepts via cutting, pasting and rescaling actions. STEM Education, 2021, 1 (3) : 170-185. doi: 10.3934/steme.2021013 [9] Ilwoo Cho, Palle Jorgense. Free probability on $C^{*}$-algebras induced by hecke algebras over primes. Discrete & Continuous Dynamical Systems - S, 2019, 12 (8) : 2221-2252. doi: 10.3934/dcdss.2019143 [10] Pengyan Wang, Pengcheng Niu. Liouville's theorem for a fractional elliptic system. Discrete & Continuous Dynamical Systems, 2019, 39 (3) : 1545-1558. doi: 10.3934/dcds.2019067 [11] David L. Finn. Noncompact manifolds with constant negative scalar curvature and singular solutions to semihnear elliptic equations. Conference Publications, 1998, 1998 (Special) : 262-275. doi: 10.3934/proc.1998.1998.262 [12] 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 [13] Ilwoo Cho. Certain $*$-homomorphisms acting on unital $C^{*}$-probability spaces and semicircular elements induced by $p$-adic number fields over primes $p$. Electronic Research Archive, 2020, 28 (2) : 739-776. doi: 10.3934/era.2020038 [14] Alexander Blokh, Eric Teoh. How little is little enough?. Discrete & Continuous Dynamical Systems, 2003, 9 (4) : 969-978. doi: 10.3934/dcds.2003.9.969 [15] Marc Deschamps, Olivier Poncelet. Complex ray in anisotropic solids: Extended Fermat's principle. Discrete & Continuous Dynamical Systems - S, 2019, 12 (6) : 1623-1633. doi: 10.3934/dcdss.2019110 [16] Yan Cui, Yanfei Wang. Velocity modeling based on Rayleigh wave dispersion curve and sparse optimization inversion. Inverse Problems & Imaging, 2021, 15 (5) : 1121-1134. doi: 10.3934/ipi.2021031 [17] Shi Jin, Christof Sparber, Zhennan Zhou. On the classical limit of a time-dependent self-consistent field system: Analysis and computation. Kinetic & Related Models, 2017, 10 (1) : 263-298. doi: 10.3934/krm.2017011 [18] Gastão S. F. Frederico, Delfim F. M. Torres. Noether's symmetry Theorem for variational and optimal control problems with time delay. Numerical Algebra, Control & Optimization, 2012, 2 (3) : 619-630. doi: 10.3934/naco.2012.2.619 [19] Piotr Fijałkowski. A global inversion theorem for functions with singular points. Discrete & Continuous Dynamical Systems - B, 2018, 23 (1) : 173-180. doi: 10.3934/dcdsb.2018011 [20] Huaiyu Jian, Hongjie Ju, Wei Sun. Traveling fronts of curve flow with external force field. Communications on Pure & Applied Analysis, 2010, 9 (4) : 975-986. doi: 10.3934/cpaa.2010.9.975

2020 Impact Factor: 0.935

## Metrics

• PDF downloads (249)
• HTML views (495)
• Cited by (0)

## Other articlesby authors

• on AIMS
• on Google Scholar

[Back to Top]