Skip to main content
Erschienen in: Foundations of Computational Mathematics 1/2018

24.10.2016

Algorithms for Commutative Algebras Over the Rational Numbers

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

Erschienen in: Foundations of Computational Mathematics | Ausgabe 1/2018

Einloggen

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

search-config
loading …

Abstract

The algebras considered in this paper are commutative rings of which the additive group is a finite-dimensional vector space over the field of rational numbers. We present deterministic polynomial-time algorithms that, given such an algebra, determine its nilradical, all of its prime ideals, as well as the corresponding localizations and residue class fields, its largest separable subalgebra, and its primitive idempotents. We also solve the discrete logarithm problem in the multiplicative group of the algebra. While deterministic polynomial-time algorithms were known earlier, our approach is different from previous ones. One of our tools is a primitive element algorithm; it decides whether the algebra has a primitive element and, if so, finds one, all in polynomial time. A methodological novelty is the use of derivations to replace a Hensel–Newton iteration. It leads to an explicit formula for lifting idempotents against nilpotents that is valid in any commutative ring.

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!

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!

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!

Literatur
1.
Zurück zum Zitat L. Babai, R. Beals, J-y. Cai, G. Ivanyos, and E. M. Luks, Multiplicative equations over commuting matrices, in Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Atlanta, GA, 1996), ACM, New York, 1996, 498–507. L. Babai, R. Beals, J-y. Cai, G. Ivanyos, and E. M. Luks, Multiplicative equations over commuting matrices, in Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Atlanta, GA, 1996), ACM, New York, 1996, 498–507.
2.
Zurück zum Zitat D. Eisenbud, Commutative algebra with a view toward algebraic geometry, Graduate Texts in Mathematics 150, Springer-Verlag, New York, 1995. D. Eisenbud, Commutative algebra with a view toward algebraic geometry, Graduate Texts in Mathematics 150, Springer-Verlag, New York, 1995.
3.
Zurück zum Zitat K. Friedl and L. Rónyai, Polynomial time solutions of some problems of computational algebra, in Proceedings of the seventeenth annual ACM symposium on Theory of computing, ACM, 1985, 153–162. K. Friedl and L. Rónyai, Polynomial time solutions of some problems of computational algebra, in Proceedings of the seventeenth annual ACM symposium on Theory of computing, ACM, 1985, 153–162.
4.
Zurück zum Zitat J. von zur Gathen and J. Gerhard, Modern computer algebra. Third edition. Cambridge University Press, Cambridge, 2013. J. von zur Gathen and J. Gerhard, Modern computer algebra. Third edition. Cambridge University Press, Cambridge, 2013.
5.
Zurück zum Zitat G. Ge, Algorithms related to multiplicative representations of algebraic numbers, PhD thesis, U.C. Berkeley, 1993. G. Ge, Algorithms related to multiplicative representations of algebraic numbers, PhD thesis, U.C. Berkeley, 1993.
6.
Zurück zum Zitat P. Gianni, V. Miller, and B. Trager, Decomposition of algebras, in Symbolic and algebraic computation (Rome, 1988), Lect. Notes in Comp. Sci. 358, Springer, Berlin, 1989, 300–308.MATH P. Gianni, V. Miller, and B. Trager, Decomposition of algebras, in Symbolic and algebraic computation (Rome, 1988), Lect. Notes in Comp. Sci. 358, Springer, Berlin, 1989, 300–308.MATH
7.
Zurück zum Zitat G. H. Hardy and E. M. Wright, An introduction to the theory of numbers. Fifth edition. The Clarendon Press, Oxford University Press, New York, 1979. G. H. Hardy and E. M. Wright, An introduction to the theory of numbers. Fifth edition. The Clarendon Press, Oxford University Press, New York, 1979.
8.
9.
Zurück zum Zitat G. Ivanyos, L. Rónyai, and A. Szántó, Decomposition of algebras over \({\mathbb{F}}_q(X_1,\ldots ,X_m)\), Appl. Algebra Engrg. Comm. Comput. 5, 1994, 71–90. G. Ivanyos, L. Rónyai, and A. Szántó, Decomposition of algebras over \({\mathbb{F}}_q(X_1,\ldots ,X_m)\), Appl. Algebra Engrg. Comm. Comput. 5, 1994, 71–90.
10.
Zurück zum Zitat A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), 515–534. A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), 515–534.
12.
Zurück zum Zitat 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, Revisiting the Gentry-Szydlo Algorithm, in Advances in Cryptology—CRYPTO 2014, Lect. Notes in Comp. Sci. 8616, Springer, Berlin, 2014, 280–296.
Metadaten
Titel
Algorithms for Commutative Algebras Over the Rational Numbers
verfasst von
H. W. Lenstra Jr.
A. Silverberg
Publikationsdatum
24.10.2016
Verlag
Springer US
Erschienen in
Foundations of Computational Mathematics / Ausgabe 1/2018
Print ISSN: 1615-3375
Elektronische ISSN: 1615-3383
DOI
https://doi.org/10.1007/s10208-016-9336-6

Weitere Artikel der Ausgabe 1/2018

Foundations of Computational Mathematics 1/2018 Zur Ausgabe