[go: up one dir, main page]
Skip to main content
SpringerLink
Log in

Computing Explicit Isomorphisms with Full Matrix Algebras over \(\mathbb {F}_q(x)\)

  • Published:
Foundations of Computational Mathematics Aims and scope Submit manuscript

Abstract

We propose a polynomial time f-algorithm (a deterministic algorithm which uses an oracle for factoring univariate polynomials over \(\mathbb {F}_q\)) for computing an isomorphism (if there is any) of a finite-dimensional \(\mathbb {F}_q(x)\)-algebra \(\mathcal{A}\) given by structure constants with the algebra of n by n matrices with entries from \(\mathbb {F}_q(x)\). The method is based on computing a finite \(\mathbb {F}_q\)-subalgebra of \(\mathcal{A}\) which is the intersection of a maximal \(\mathbb {F}_q[x]\)-order and a maximal R-order, where R is the subring of \(\mathbb {F}_q(x)\) consisting of fractions of polynomials with denominator having degree not less than that of the numerator.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Notes

  1. A polynomial bound for the dimension of C follows also simply from the polynomiality of the algorithm described here.

References

  1. M. Ajtai: The shortest vector problem in \(L_2\) is NP-hard for randomized reductions, Proceedings of the 30th annual ACM symposium on Theory of computing (1998), Dallas, Texas, United States, ACM. pp. 10-19.

  2. E.R. Berlekamp: Factoring polynomials over finite fields, Bell System Technical Journal 46 (1967), pp. 1853-1859.

    Article  MathSciNet  MATH  Google Scholar 

  3. D.G. Cantor, H. Zassenhaus: A new algorithm for factoring polynomials over finite fields, Mathematics of Computation 36 (1981), pp. 587-592.

    Article  MathSciNet  MATH  Google Scholar 

  4. J.E. Cremona, T.A. Fisher, C. O’neil, D. Simon, M. Stoll: Explicit \(n\)-descent on elliptic curves I. Algebra, Journal für die reine und angewandte Mathematik, Vol. 615 (2008), pp. 121-155.

  5. J.E. Cremona, T.A. Fisher, C. O’neil, D. Simon, M. Stoll: Explicit \(n\)-descent on elliptic curves II. Geometry, Journal für die reine und angewandte Mathematik 632 (2009), pp. 63–84.

  6. J.E. Cremona, T.A. Fisher, C. O’neil, D. Simon, M. Stoll: Explicit \(n\)-descent on elliptic curves III. Algorithms, Mathematics of Computation 84 No.292 (2015), 895-922.

  7. W.A. de Graaf, G. Ivanyos, A. Küronya, L. Rónyai: Computing Levi decompositions, Applicable Algebra in Engineering, Communication and Computing 8 (1997), pp. 291-304.

    Article  MathSciNet  MATH  Google Scholar 

  8. Y. Drozd, V.V. Kirichenko: Finite dimensional algebras, Vyshcha Shkola, Kiev, 1980.

    MATH  Google Scholar 

  9. K. Friedl, L. Rónyai: Polynomial time solutions of some problems in computational algebra, Proceedings of the 17th annual ACM symposium on Theory of computing (1985), Providence, Rhode Island, United States, ACM. pp. 153-162.

  10. M. Giesbrecht, Y. Zhang: Factoring and decomposing Ore polynomials over \(\mathbb{F}_q(T)\), Proceedingss of the 2003 International Symposium on Symbolic and Algebraic Computation (ISSAC2003), New York, NY, United States, ACM. pp. 127-134.

  11. J. Gómez-Torrecillas, F. J. Lobillo, G. Navarro: Factoring Ore polynomials over \({\mathbb{F}}_q(t)\) is difficult, (2015) Preprint arXiv:1505.07252.

  12. G. Ivanyos: Algorithms for algebras over global field, Ph.D. thesis, Hungarian Academy of Sciences (1996), http://real-d.mtak.hu/261/1/Ivanyos_Gabor.

  13. G. Ivanyos, M. Karpinski, L. Rónyai, N. Saxena: Trading GRH for algebra: algorithms for factoring polynomials and related structures, Matematics of Computation 81 (2012), pp. 493-531.

    Article  MathSciNet  MATH  Google Scholar 

  14. G. Ivanyos, Á. Lelkes, L. Rónyai: Improved algorithms for splitting full matrix algebras, JP Journal of Algebra, Number Theory and Applications 28 (2013), pp. 141-156.

    MathSciNet  MATH  Google Scholar 

  15. G. Ivanyos, L. Rónyai: On the complexity of finding maximal orders in semisimple algebras over \({\mathbb{Q}}\), Comput. complexity 3 (1993), pp. 245-261.

    Article  MathSciNet  MATH  Google Scholar 

  16. G. Ivanyos, L. Rónyai, J. Schicho: Splitting full matrix algebras over algebraic number fields, Journal of Algebra 354 (2012), pp. 211-223.

    Article  MathSciNet  MATH  Google Scholar 

  17. G. Ivanyos, L. Rónyai, Á. Szántó: Decomposition of algebras over \({\mathbb{F}}_q(x_1,... ,x_m)\), Applicable Algebra in Engineering, Communication and Computing 5 (1994), pp. 71-90.

    Article  MathSciNet  MATH  Google Scholar 

  18. A.K. Lenstra: Factoring multivariate polynomials over finite fields, Journal of Computer and System Sciences 30 (2) (1985), pp. 235-248.

    Article  MathSciNet  MATH  Google Scholar 

  19. S. Paulus: Lattice basis reduction in function fields, J. Buhler (Ed.), Proceedings of the Third Symposium on Algorithmic Number Theory, Portland, Oregon, United States: ANTS-III, Springer LNCS 1423 (1998), pp. 567-575.

  20. I. Reiner: Maximal orders, Academic Press, London, 1975.

  21. L. Rónyai: Computing the structure of finite algebras, Journal of Symbolic Computation 9 (1990), pp. 355-373.

    Article  MathSciNet  MATH  Google Scholar 

  22. M-F. Vignéras: Arithmétique des Algèbres de Quaternions, Springer, LNM 800, 1980.

Download references

Acknowledgements

Research is supported by the Hungarian National Research, Development and Innovation Office—NKFIH—Grants NK105645 and K115288. The authors are grateful to an anonymous referee for helpful remarks and suggestions.

Author information

Authors and Affiliations

  1. Institute for Computer Science and Control, Hungarian Acad. Sci., Budapest, Hungary

    Gábor Ivanyos & Lajos Rónyai

  2. Department of Mathematics and Its Applications, Central European University, Budapest, Hungary

    Péter Kutas

  3. Department of Algebra, Budapest University of Technology and Economics, Budapest, Hungary

    Lajos Rónyai

Authors
  1. Gábor Ivanyos
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Péter Kutas
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Lajos Rónyai
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Péter Kutas.

Additional information

Communicated by John Cremona.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Ivanyos, G., Kutas, P. & Rónyai, L. Computing Explicit Isomorphisms with Full Matrix Algebras over \(\mathbb {F}_q(x)\) . Found Comput Math 18, 381–397 (2018). https://doi.org/10.1007/s10208-017-9343-2

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10208-017-9343-2

Keywords

Mathematics Subject Classification

Search

Navigation