**The Eleventh Power Residue Symbol**

*Marc Joye and Oleksandra Lapiha and 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.

**Category / Keywords: **implementation / Power residue symbol, cyclotomic field, reciprocity law, cryptography.

**Date: **received 29 Jul 2019, last revised 4 Nov 2019

**Contact author: **marc joye at onespan com

**Available format(s): **PDF | BibTeX Citation

**Note: **Fixed typo in the proof of proposition 3

**Version: **20191105:063823 (All versions of this report)

**Short URL: **ia.cr/2019/870

[ Cryptology ePrint archive ]