Paper 2016/138

A new algorithm for residue multiplication modulo $2^{521}-1$

Shoukat Ali and Murat Cenk

Abstract

We present a new algorithm for residue multiplication modulo the Mersenne prime $2^{521}-1$ based on the Toeplitz matrix-vector product. For this modulo, our algorithm yields better result in terms of the total number of operations than the previously known best algorithm of R. Granger and M. Scott presented in Public Key Cryptography - PKC 2015. Although our algorithm has nine more multiplications than Granger-Scott multiplication algorithm, the total number of additions is forty-two less than their algorithm. Even if one takes a ratio of $1:4$ between multiplication and addition our algorithm still has less total number of operations. We also present the test results of both the multiplication algorithms on an Intel Sandy Bridge Corei5-2410M machine, with and without optimization option in GCC.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint.
Keywords
residue multiplicationToeplitz matrix-vector productMersenne primeelliptic curve cryptography
Contact author(s)
shoukat 1983 @ gmail com
History
2016-02-16: received
Short URL
https://ia.cr/2016/138
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/138,
      author = {Shoukat Ali and Murat Cenk},
      title = {A new algorithm for residue multiplication modulo $2^{521}-1$},
      howpublished = {Cryptology ePrint Archive, Paper 2016/138},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/138}},
      url = {https://eprint.iacr.org/2016/138}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.