Article

Free access

Polynomial time solutions of some problems of computational algebra

Authors:

K Friedl,

L RónyaiAuthors Info & Claims

STOC '85: Proceedings of the seventeenth annual ACM symposium on Theory of computing

Pages 153 - 162

https://doi.org/10.1145/22145.22162

Published: 01 December 1985 Publication History

PDF eReader

Abstract

The first structure theory in abstract algebra was that of finite dimensional Lie algebras (Cartan-Killing), followed by the structure theory of associative algebras (Wedderburn-Artin). These theories determine, in a non-constructive way, the basic building blocks of the respective algebras (the radical and the simple components of the factor by the radical). In view of the extensive computations done in such algebras, it seems important to design efficient algorithms to find these building blocks.

We find polynomial time solutions to a substantial part of these problems. We restrict our attention to algebras over finite fields and over algebraic number fields. We succeed in determining the radical (the “bad part” of the algebra) in polynomial time, using (in the case of prime characteristic) some new algebraic results developed in this paper. For associative algebras we are able to determine the simple components as well. This latter result generalizes factorization of polynomials over the given field. Correspondingly, our algorithm over finite fields is Las Vegas.

Some of the results generalize to fields given by oracles.

Some fundamental problems remain open. An example: decide whether or not a given rational algebra is a noncommutative field.

References

[1]

L. Bahai, W. M. Kaator, E. M. Luks, Computational eomplezittl lad the eldssificatiop o! }?nit~ simple groups, Proc. 24th IEEE Syrup. Found. Camp. $ci., Tuc.son, Arizona, 1983, 162-171.

Google Scholar

[2]

R.E. Beck, B. Kolman, I. N. Stewart, Computing the structure o! o Lie algebra, Computers in nonassociarve rings and algebras, Academic Press, New 'fork-San Francisco- London, 1077, 167-188.

Google Scholar

[3]

E. R, Bcrlekamp, Factoring polynomials over large finite/ields, Math. Camp. 24 (1070), 713-715.

Google Scholar

[4]

A. Borodin, $. Cook, N. Pippenger, Parallel computation,for well. emtowed rings and sptsee-bounded probabillstic machines, !nfoxmation and Control 58 (1983), 113-~3G.

Digital Library

Google Scholar

[5]

A.L. Chistov, D. Yu. Grigoryev, Pollmomid-time/he. taring o! the multlvgriable polgnomiale o~cr i global field, LOMI preprint, Leningrad 17~2. (to appeaz in J. of Symbolic Computation)

Google Scholar

[6]

L.E. Dickson, Algebras and their srlthmctics, University of Chicago, 1923.

Google Scholar

[7]

I.N. Hcrsteia, Nonco;nmutative rings, Math. Assoc. of America, 1968.

Google Scholar

[8]

N. Jacobson, Lie a/;ebras, John Wiley, New York- London, 1962.

Google Scholar

[9]

D. E',. Kauth, TAe art o! computer prograraming, Vol. t, Seminstmerical algorithms, Addison-Wesley, Reading, 1981.

Google Scholar

[10]

S. Landau, Factoring pollmornials o~er 41itebs'aie number fields is in polynomial time, SIAM J. Cor~p., 1085, to appear

Google Scholar

[11]

A.K. Lea~tra, Factoring pollfnomials over algebraic number fields, in: Proc. Eurocal'83, Springer Lect. Notes ia Camp. ScL vol. 162, 245-254.

Digital Library

Google Scholar

[12]

A.K. Leastra, H. W. Lenstra, L. I,ov~z, Factoring polynomials with rational cocfficicnts, Math. Ann. 261 (1982), 515-534.

Crossref

Google Scholar

[13]

M.O. Rabid, Probabilistic algorithms in .finitt ji~lda, SIAM J. Camp. 9 (1980), 273-280.

Crossref

Google Scholar

Cited By

View all

Qiao YSun X(2024)Canonical Forms for Matrix Tuples in Polynomial Time2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00054(780-789)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00054
Grochow JQiao Y(2023)On p-Group Isomorphism: Search-to-Decision, Counting-to-Decision, and Nilpotency Class Reductions via TensorsACM Transactions on Computation Theory10.1145/362530816:1(1-39)Online publication date: 24-Sep-2023
https://dl.acm.org/doi/10.1145/3625308
Couvreur AZappatore I(2023)An Extension of Overbeck’s Attack with an Application to Cryptanalysis of Twisted Gabidulin-Based SchemesPost-Quantum Cryptography10.1007/978-3-031-40003-2_1(3-37)Online publication date: 10-Aug-2023
https://doi.org/10.1007/978-3-031-40003-2_1
Show More Cited By

Index Terms

Polynomial time solutions of some problems of computational algebra
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Computations on polynomials
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features
        Abstract data types
      2. Language types

Recommendations

Combination problems for commutative/monoidal theories or how algebra can help in equational unification

We study the class of theories for which solving unification problems is equivalent to solving systems of linear equations over a semiring. It encompasses important examples like the theories of Abelian monoids, idempotent Abelian monoids, and Abelian ...
Polynomial-Time Solutions of Computational Problems in Noncommutative-Algebraic Cryptography

We introduce the linear centralizer method, and use it to devise a provable polynomial-time solution of the Commutator Key Exchange Problem, the computational problem on which, in the passive adversary model, the security of the Anshel---Anshel---...
Skew polynomial rings, Gröbner bases and the letterplace embedding of the free associative algebra

In this paper we introduce an algebra embedding @i:K ->S from the free associative algebra K generated by a finite or countable set X into the skew monoid ring S=P@__ __@S defined by the commutative polynomial ring P=K[XxN^@__ __] and by the monoid @S=<@...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '85: Proceedings of the seventeenth annual ACM symposium on Theory of computing

December 1985

484 pages

ISBN:0897911512

DOI:10.1145/22145

Chairman:
Robert Sedgewick

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 1985

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC85

Sponsor:

SIGACT

STOC85: Annual ACM Conference on Theory of Computing

May 6 - 8, 1985

Rhode Island, Providence, USA

Acceptance Rates

Overall Acceptance Rate 1,289 of 3,901 submissions, 33%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

43
Total Citations
View Citations
684
Total Downloads

Downloads (Last 12 months)105
Downloads (Last 6 weeks)29

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Qiao YSun X(2024)Canonical Forms for Matrix Tuples in Polynomial Time2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00054(780-789)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00054
Grochow JQiao Y(2023)On p-Group Isomorphism: Search-to-Decision, Counting-to-Decision, and Nilpotency Class Reductions via TensorsACM Transactions on Computation Theory10.1145/362530816:1(1-39)Online publication date: 24-Sep-2023
https://dl.acm.org/doi/10.1145/3625308
Couvreur AZappatore I(2023)An Extension of Overbeck’s Attack with an Application to Cryptanalysis of Twisted Gabidulin-Based SchemesPost-Quantum Cryptography10.1007/978-3-031-40003-2_1(3-37)Online publication date: 10-Aug-2023
https://doi.org/10.1007/978-3-031-40003-2_1
Arvind VJoglekar P(2022)On efficient noncommutative polynomial factorization via higman linearizationProceedings of the 37th Computational Complexity Conference10.4230/LIPIcs.CCC.2022.12(1-22)Online publication date: 20-Jul-2022
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2022.12
Bley WHofmann TJohnston H(2022)Computation of lattice isomorphisms and the integral matrix similarity problemForum of Mathematics, Sigma10.1017/fms.2022.7410Online publication date: 10-Oct-2022
https://doi.org/10.1017/fms.2022.74
Csahók TKutas PMontessinos MZábrádi G(2022)Explicit isomorphisms of quaternion algebras over quadratic global fieldsResearch in Number Theory10.1007/s40993-022-00380-38:4Online publication date: 1-Oct-2022
https://doi.org/10.1007/s40993-022-00380-3
Grochow JQiao Y(2021)On p-group isomorphismProceedings of the 36th Computational Complexity Conference10.4230/LIPIcs.CCC.2021.16Online publication date: 20-Jul-2021
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2021.16
Chen GPonomarenko I(2021)Tensor products of coherent configurationsFrontiers of Mathematics10.1007/s11464-021-0975-917:5(829-852)Online publication date: 27-Sep-2021
https://doi.org/10.1007/s11464-021-0975-9
Kiss SKutas P(2021)An identification system based on the explicit isomorphism problemApplicable Algebra in Engineering, Communication and Computing10.1007/s00200-021-00529-034:6(913-930)Online publication date: 19-Oct-2021
https://doi.org/10.1007/s00200-021-00529-0
Garg AKayal NSaha C(2020)Learning sums of powers of low-degree polynomials in the non-degenerate case2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS46700.2020.00087(889-899)Online publication date: Nov-2020
https://doi.org/10.1109/FOCS46700.2020.00087
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Combination problems for commutative/monoidal theories or how algebra can help in equational unification

Polynomial-Time Solutions of Computational Problems in Noncommutative-Algebraic Cryptography

Skew polynomial rings, Gröbner bases and the letterplace embedding of the free associative algebra