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

Date: received 9 Oct 2019

Contact author: david naccache at ens fr

Available format(s): PDF | BibTeX Citation

Version: 20191010:125441 (All versions of this report)

Short URL: ia.cr/2019/1176


[ Cryptology ePrint archive ]