May  2022, 16(2): 303-348. 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  May 2022 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, 2022, 16 (2) : 303-348. 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.

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

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

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

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

[6]

D. J. BernsteinN. DuifT. LangeP. 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.

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

[8]

J. W. BosC. CostelloH. Hisil and and K. E. Lauter, Fast cryptography in genus 2, J. Cryptology, 29 (2016), 28-60.  doi: 10.1007/s00145-014-9188-7.

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

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

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

[12]

NIST Curves, Recommended elliptic curves for federal government use, http://csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf, 1999.

[13]

Michael DüllBjörn HaaseGesine HinterwälderMichael HutterChristof PaarAna 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.

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

[15]

D. Hankerson, A. J. Menezes and S. Vanstone, Guide to Elliptic Curve Cryptography, Springer, 2003. doi: 10.1016/s0012-365x(04)00102-5.

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

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

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

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

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

[21]

N. Koblitz, Elliptic curve cryptosystems, Math. Comp., 48 (1987), 203-209.  doi: 10.1090/S0025-5718-1987-0866109-5.

[22]

N. Koblitz, Hyperelliptic cryptosystems, J. Cryptology, 1 (1989), 139-150.  doi: 10.1007/BF02252872.

[23]

Optimized C library for EC operations on curve secp256k1, https://github.com/bitcoin-core/secp256k1.,

[24] A. J. MenezesP. C. van Oorschot and S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1996. 
[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.

[26]

S. Nakamoto, Bitcoin: A peer-to-peer electronic cash system, http://bitcoin.org/bitcoin.pdf, 2009.

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

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

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

[30]

Certicom Research, SEC2: Recommended elliptic curve domain parameters, http://www.secg.org/sec2-v2.pdf, 2010.

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.

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

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

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

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

[6]

D. J. BernsteinN. DuifT. LangeP. 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.

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

[8]

J. W. BosC. CostelloH. Hisil and and K. E. Lauter, Fast cryptography in genus 2, J. Cryptology, 29 (2016), 28-60.  doi: 10.1007/s00145-014-9188-7.

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

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

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

[12]

NIST Curves, Recommended elliptic curves for federal government use, http://csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf, 1999.

[13]

Michael DüllBjörn HaaseGesine HinterwälderMichael HutterChristof PaarAna 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.

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

[15]

D. Hankerson, A. J. Menezes and S. Vanstone, Guide to Elliptic Curve Cryptography, Springer, 2003. doi: 10.1016/s0012-365x(04)00102-5.

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

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

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

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

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

[21]

N. Koblitz, Elliptic curve cryptosystems, Math. Comp., 48 (1987), 203-209.  doi: 10.1090/S0025-5718-1987-0866109-5.

[22]

N. Koblitz, Hyperelliptic cryptosystems, J. Cryptology, 1 (1989), 139-150.  doi: 10.1007/BF02252872.

[23]

Optimized C library for EC operations on curve secp256k1, https://github.com/bitcoin-core/secp256k1.,

[24] A. J. MenezesP. C. van Oorschot and S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1996. 
[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.

[26]

S. Nakamoto, Bitcoin: A peer-to-peer electronic cash system, http://bitcoin.org/bitcoin.pdf, 2009.

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

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

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

[30]

Certicom Research, SEC2: Recommended elliptic curve domain parameters, http://www.secg.org/sec2-v2.pdf, 2010.

Figure 1.  Single carry chain for $\mathsf {mulSCC}$
Figure 2.  Two independent carry chains for $\mathsf {mulSLDCC}$
Table 1.  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
Table 2.  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 $ -
Table 3.  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
Table 4.  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
Table 5.  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}$ -
Table 6.  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}$ -
Table 7.  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}$ -
Table 8.  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 and 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 and 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 and 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 and Continuous Dynamical Systems, 2019, 39 (3) : 1545-1558. doi: 10.3934/dcds.2019067

[11]

Franziska Nestler, Martin Stoll, Theresa Wagner. Learning in high-dimensional feature spaces using ANOVA-based fast matrix-vector multiplication. Foundations of Data Science, 2022, 4 (3) : 423-440. doi: 10.3934/fods.2022012

[12]

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

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

Huy Dinh, Harbir Antil, Yanlai Chen, Elena Cherkaev, Akil Narayan. Model reduction for fractional elliptic problems using Kato's formula. Mathematical Control and Related Fields, 2022, 12 (1) : 115-146. doi: 10.3934/mcrf.2021004

[15]

Alexander Blokh, Eric Teoh. How little is little enough?. Discrete and Continuous Dynamical Systems, 2003, 9 (4) : 969-978. doi: 10.3934/dcds.2003.9.969

[16]

Marc Deschamps, Olivier Poncelet. Complex ray in anisotropic solids: Extended Fermat's principle. Discrete and Continuous Dynamical Systems - S, 2019, 12 (6) : 1623-1633. doi: 10.3934/dcdss.2019110

[17]

Yan Cui, Yanfei Wang. Velocity modeling based on Rayleigh wave dispersion curve and sparse optimization inversion. Inverse Problems and Imaging, 2021, 15 (5) : 1121-1134. doi: 10.3934/ipi.2021031

[18]

Shi Jin, Christof Sparber, Zhennan Zhou. On the classical limit of a time-dependent self-consistent field system: Analysis and computation. Kinetic and Related Models, 2017, 10 (1) : 263-298. doi: 10.3934/krm.2017011

[19]

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 and Optimization, 2012, 2 (3) : 619-630. doi: 10.3934/naco.2012.2.619

[20]

Piotr Fijałkowski. A global inversion theorem for functions with singular points. Discrete and Continuous Dynamical Systems - B, 2018, 23 (1) : 173-180. doi: 10.3934/dcdsb.2018011

2021 Impact Factor: 1.015

Metrics

  • PDF downloads (526)
  • HTML views (655)
  • Cited by (0)

Other articles
by authors

[Back to Top]