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.