Paper 2019/870

The Eleventh Power Residue Symbol

Marc Joye, Oleksandra Lapiha, Ky Nguyen, and David Naccache

Abstract

This paper presents an efficient algorithm for computing $11^{\mathrm{th}}$-power residue symbols in the cyclotomic field $\mathbb{Q}(\zeta_{11})$, where $\zeta_{11}$ is a primitive $11^{\mathrm{th}}$ root of unity. It extends an earlier algorithm due to Caranay and Scheidler (Int. J. Number Theory, 2010) for the $7^{\mathrm{th}}$-power residue symbol. The new algorithm finds applications in the implementation of certain cryptographic schemes.

Note: Fixed typo in the proof of proposition 3

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint.
Keywords
Power residue symbolcyclotomic fieldreciprocity lawcryptography.
Contact author(s)
marc joye @ onespan com
History
2019-11-05: last of 2 revisions
2019-07-30: received
See all versions
Short URL
https://ia.cr/2019/870
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/870,
      author = {Marc Joye and Oleksandra Lapiha and Ky Nguyen and David Naccache},
      title = {The Eleventh Power Residue Symbol},
      howpublished = {Cryptology ePrint Archive, Paper 2019/870},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/870}},
      url = {https://eprint.iacr.org/2019/870}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.