Roots of unity in orders

DOI10.1007/S10208-016-9304-1MaRDI QIDQ2362292zbMATHOpenAlexFDO

Authors Alice Silverberg, H. W. jun. Lenstra

Publication date 7 July 2017

Published in Foundations of Computational Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1509.02612

zbMATH Keywords

algorithmsordersdiscrete logarithm problemidempotentsroots of unity

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) General commutative ring theory (13A99) Other algebras and orders, and their zeta and (L)-functions (11R54) Commutative orders (16H15)

Abstract: We give deterministic polynomial-time algorithms that, given an order, compute the primitive idempotents and determine a set of generators for the group of roots of unity in the order. Also, we show that the discrete logarithm problem in the group of roots of unity can be solved in polynomial time. As an auxiliary result, we solve the discrete logarithm problem for certain unit groups in finite rings. Our techniques, which are taken from commutative algebra, may have further potential in the context of cryptology and computer algebra.

Recommendations

• scientific article; zbMATH DE number 733559
• Publication:4945389
• Algorithms in Algebraic Number Theory
• Efficient polynomial time algorithms computing industrial-strength primitive roots
• On some computational problems in finite abelian groups

Cites work

• scientific article; zbMATH DE number 1703931 (Why is no real title available?)
• scientific article; zbMATH DE number 3858405 (Why is no real title available?)
• scientific article; zbMATH DE number 5486283 (Why is no real title available?)
• scientific article; zbMATH DE number 3279238 (Why is no real title available?)
• Revisiting the Gentry-Szydlo Algorithm
• Testing isomorphism of lattices over CM-orders

Cited in

(10)

• Realizing orders as group rings
• scientific article; zbMATH DE number 3966237 (Why is no real title available?)
• Universal gradings of orders
• Computing \(e\)-th roots in number fields
• Testing isomorphism of lattices over CM-orders
• Fundamental units for orders of unit rank 1 and generated by a unit
• scientific article; zbMATH DE number 599309 (Why is no real title available?)
• Full level structures revisited: pairs of roots of unity
• Lattices with symmetry
• Algorithms for commutative algebras over the rational numbers

Describes a project that uses

Uses Software

• Algorithm 447

This page was built for publication: Roots of unity in orders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2362292)