## Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations / Power residue symbol, cyclotomic field, reciprocity law