Welcome to the resource topic for 2021/1106
Title:
Primary Elements in Cyclotomic Fields with Applications to Power Residue Symbols, and More
Authors: Eric Brier, Rémi Géraud-Stewart, Marc Joye, David Naccache
Abstract:Higher-order power residues have enabled the construction of numerous public-key encryption schemes, authentication schemes, and digital signatures. Their explicit characterization is however challenging; an algorithm of Caranay and Scheidler computes p-th power residue symbols, with p \le 13 an odd prime, provided that primary elements in the corresponding cyclotomic field can be efficiently found. In this paper, we describe a new, generic algorithm to compute primary elements in cyclotomic fields; which we apply for p=3,5,7,11,13. A key insight is a careful selection of fundamental units as put forward by Dénes. This solves an essential step in the Caranay–Scheidler algorithm. We give a unified view of the problem. Finally, we provide the first efficient deterministic algorithm for the computation of the 9-th and 16-th power residue symbols.
ePrint: https://eprint.iacr.org/2021/1106
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .