nach oben

Foundations of Computational Mathematics

Erschienen in:

12.02.2016

Roots of Unity in Orders

verfasst von: H. W. Lenstra Jr., A. Silverberg

Erschienen in: Foundations of Computational Mathematics | Ausgabe 3/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Vorheriger Artikel Toward Effective Detection of the Bifurcation Locus of Real Polynomial Maps

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

M. F. Atiyah and I. G. Macdonald, Introduction to commutative algebra, Addison-Wesley Publishing Co., Reading, MA, 1969.MATH

J. Hopcroft and R. Tarjan, Algorithm 447: efficient algorithms for graph manipulation, Communications of the ACM, 16, no. 6 (1973) 372–378.CrossRef

S. Lang, Algebra, Third edition, Graduate Texts in Mathematics 211, Springer-Verlag, New York, 2002.

A. K. Lenstra, Factoring polynomials over algebraic number fields, in Computer algebra (London, 1983), Lect. Notes in Comp. Sci. 162, Springer, Berlin, 1983, 245–254.

H. W. Lenstra, Jr., Lattices, in Algorithmic number theory: lattices, number fields, curves and cryptography, Math. Sci. Res. Inst. Publ. 44, Cambridge Univ. Press, Cambridge, 2008, 127–181, http://library.msri.org/books/Book44/files/06hwl.pdf.

H. W. Lenstra, Jr. and A. Silverberg, Revisiting the Gentry-Szydlo Algorithm, in Advances in Cryptology–CRYPTO 2014, Lect. Notes in Comp. Sci. 8616, Springer, Berlin, 2014, 280–296.

H. W. Lenstra, Jr. and A. Silverberg, Lattices with symmetry, to appear in Journal of Cryptology, https://eprint.iacr.org/2014/1026.

H. W. Lenstra, Jr. and A. Silverberg, Algorithms for commutative algebras over the rational numbers, arXiv:1509.08843.

Titel: Roots of Unity in Orders
verfasst von: H. W. Lenstra Jr.
A. Silverberg
Publikationsdatum: 12.02.2016
Verlag: Springer US
Erschienen in: Foundations of Computational Mathematics / Ausgabe 3/2017
Print ISSN: 1615-3375
Elektronische ISSN: 1615-3383
DOI: https://doi.org/10.1007/s10208-016-9304-1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 3/2017

Construction of Approximate Entropy Measure-Valued Solutions for Hyperbolic Systems of Conservation Laws

Toward Effective Detection of the Bifurcation Locus of Real Polynomial Maps

A Lower Bound for the Determinantal Complexity of a Hypersurface

Noether-Type Discrete Conserved Quantities Arising from a Finite Element Approximation of a Variational Problem

Word Series for Dynamical Systems and Their Numerical Integrators

Analysis of the Diffuse Domain Method for Second Order Elliptic Boundary Value Problems