Roots of unity in orders

DOI10.1007/S10208-016-9304-1zbMATH Open1384.16012arXiv1509.02612OpenAlexW2159115428MaRDI QIDQ2362292FDOQ2362292

Authors: Alice Silverberg, H. W. jun. Lenstra 

Publication date: 7 July 2017

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Revisiting the Gentry-Szydlo Algorithm
• Title not available (Why is that?)
• Testing Isomorphism of Lattices over CM-Orders

Cited In (8)

• Fundamental units for orders of unit rank 1 and generated by a unit
• Realizing orders as group rings
• Title not available (Why is that?)
• Algorithms for commutative algebras over the rational numbers
• Full level structures revisited: pairs of roots of unity
• Lattices with symmetry
• Title not available (Why is that?)
• Testing Isomorphism of Lattices over CM-Orders

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)