Skip to main content
SpringerLink
Log in

Square-free algorithms in positive characteristic

  • Published:
Applicable Algebra in Engineering, Communication and Computing Aims and scope

Abstract

We study the problem of the computation of the square-free decomposition for polynomials over fields of positive characteristic. For fields which are explicitly finitely generated over perfect fields, we show how the classical algorithm for characteristic zero can be generalized using multiple derivations. For more general fields of positive characteristic one must make an additional constructive hypothesis in order for the problem to be decidable. We show that Seidenberg'sCondition P gives a necessary and sufficient condition on the fieldK for computing a complete square free decomposition of polynomials with coefficients in any finite algebraic extension ofK.

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

Access this article

Log in via an institution

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

References

  1. Fröhlich, A., Shepherdson, J. C.: Effective Procedures in Field Theory. Philos. Trans. R. Soc. London, Ser.A248, 407–432 (1956)

    Google Scholar 

  2. Lang, S.: Algebra. Reading, MA., Addison-Wesley 1965

    Google Scholar 

  3. Mines, R., Richman, F., Ruitenberg, W.: A course in Constructive Algebra. Berlin, Heidelberg, New York: Springer 1988

    Google Scholar 

  4. Musser, D. R.: Algorithms for Polynomial Factorization. Ph.D. Thesis, C.S. Department, Univ. of Wisconsin (1971)

  5. Richman, F.: Seidenberg's condition P. In: Richman, F. (ed.) Constructive Mathematics. Lecture Notes in Mathematics, Vol. 873. Berlin, Heidelberg, New York: Springer 1980

    Google Scholar 

  6. Seidenberg, A.: Construction of the integral closure of a finite integral domain. Rend. Sem. Mat. Fis. Milano.40, 100–120 (1970)

    Google Scholar 

  7. Seidenberg, A.: Construction in Algebra. Trans. Am. Math. Soc.197, 273–313 (1974)

    Google Scholar 

  8. Seidenberg, A.: Constructions in a polynomial ring over the ring of integers. Am. J. Math.100, 685–703 (1978)

    Google Scholar 

  9. Yun, D.: On Square-Free Decomposition Algorithms. In: Jenks, R. D. (ed.) Proceedings of 1976 ACM SYMSAC. New York: ACM 1976

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dipartimento di Matematica, Universitá, via Buonarroti 2, I-56127, Pisa

    P. Gianni

  2. IBM Research, 10598, Yorktown Heights, NY

    B. Trager

Authors
  1. P. Gianni
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. B. Trager
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

This research was partially supported by C.N.R., M.U.R.S.T, CEC contract ES PRIT B.R.A.n.6846 POSSO and EC Science Plan Project “Computational Methods in the Theory of Riemann Surfaces and Algebraic Curves”

Rights and permissions

Reprints and permissions

About this article

Cite this article

Gianni, P., Trager, B. Square-free algorithms in positive characteristic. AAECC 7, 1–14 (1996). https://doi.org/10.1007/BF01613611

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01613611

Keywords

Search

Navigation