The Thirteenth Power Residue Symbol

Eric Brier; David Naccache

Paper 2019/1176

The Thirteenth Power Residue Symbol

Eric Brier and David Naccache

Abstract

This paper presents an efficient deterministic algorithm for computing $13$\textsuperscript{th}-power residue symbols in the cyclotomic field $\mathbb{Q}(\zeta_{13})$, where $\zeta_{13}$ is a primitive $13$\textsuperscript{th} root of unity. The new algorithm finds applications in the implementation of certain cryptographic schemes and closes a gap in the \textsl{corpus} of algorithms for computing power residue symbols.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint. MINOR revision.
Keywords: Power residue symbol cyclotomic field reciprocity law
Contact author(s): david naccache @ ens fr
History: 2019-10-10: received
Short URL: https://ia.cr/2019/1176
License: CC BY

BibTeX

@misc{cryptoeprint:2019/1176,
      author = {Eric Brier and David Naccache},
      title = {The Thirteenth Power Residue Symbol},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1176},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/1176}},
      url = {https://eprint.iacr.org/2019/1176}
}