Cryptology ePrint Archive: Report 2019/870

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 ]