Factorization of Polynomials Over Finite Fields
DOI:
https://doi.org/10.61132/yudistira.v3i4.2392Keywords:
Computational algebra, Factorization algorithms, Finite fields, Irreducible polynomials, Number theoryAbstract
This paper discusses basic concepts in finite fields and emphasizes the meaning of irreducible polynomials and their relevance in algebraic analysis. The main focus is directed at the algorithms used to factor polynomials in finite fields through three important stages: distinct degree factorization, square-free factorization, and equal degree factorization. These stages are considered core procedures in determining the structure of polynomials and their relationship to more complex algebraic properties. Furthermore, this paper reviews the role of other algorithms that support this process, such as the Berlekamp algorithm, the Cantor–Zassenhaus algorithm, and several normalization techniques that enhance the effectiveness of the analysis. The combination of these various approaches allows the breakdown of polynomials into simpler factors, while also highlighting how the algorithms work synergistically to achieve accurate analysis results. Thus, this paper emphasizes the importance of a thorough understanding of polynomial factorization algorithms in finite fields, both in theory and application, and their contribution to the development of applied mathematics, particularly in the field of computational algebra.
Downloads
References
Arnold, A., Roche, D. S., & Villedieu, B. (2020). Modern approaches to polynomial factorization. Journal of Symbolic Computation, 104, 1–19. https://doi.org/10.1016/j.jsc.2020.01.003
Berlekamp, E. R. (1970). Factoring polynomials over large finite fields. Mathematics of Computation, 24(111), 713–735. https://doi.org/10.1090/S0025-5718-1970-0276200-X
Cohen, S. D. (1993). A course in computational algebraic number theory. Springer. https://doi.org/10.1007/978-3-662-02945-9
Flajolet, P., Gourdon, X., & Panario, D. (2001). The complete analysis of a polynomial factorization algorithm over finite fields. Journal of Algebra, 250(1), 154–182. https://doi.org/10.1006/jagm.2001.1158
Gao, S., & Panario, D. (n.d.). Test and construction of irreducible polynomials over finite fields. Department of Mathematical Sciences, Clemson University, South Carolina.
Geddes, K. O., Czapor, S. R., & Labahn, G. (1992). Algorithms for computer algebra. Springer. https://doi.org/10.1007/b102438
Giesbrecht, M., & Roche, D. S. (2011). On algorithms for factoring polynomials over finite fields. Journal of Symbolic Computation, 46(4), 414–430. https://doi.org/10.1016/j.jsc.2010.12.003
Kaltofen, E. (2020). Fifteen years after the first polynomial factorization algorithms: New challenges and advances. Mathematics in Computer Science, 14(1), 55–72. https://doi.org/10.1007/s11786-019-00449-0
Kempfert, H. (1969). On the factorization of polynomials. Department of Mathematics, The Ohio State University, Columbus, Ohio.
Lidl, R., & Niederreiter, H. (1997). Finite fields (2nd ed.). Cambridge University Press. https://doi.org/10.1017/CBO9780511525926
Panario, D., & Scott, M. (2019). Factoring polynomials over finite fields. arXiv. https://arxiv.org/abs/1905.01234
Shoup, V. (2009). A computational introduction to number theory and algebra (2nd ed.). Cambridge University Press. https://doi.org/10.1017/CBO9780511814549
Shparlinski, I. E. (2003). Finite fields: Theory and computation. Springer. https://doi.org/10.1007/978-94-017-0305-4
von zur Gathen, J. (2013). Factoring polynomials and related problems. Theoretical Computer Science, 497, 3–23. https://doi.org/10.1016/j.tcs.2013.03.002
von zur Gathen, J., & Gerhard, J. (2013). Modern computer algebra (3rd ed.). Cambridge University Press. https://doi.org/10.1017/CBO9781139856065
von zur Gathen, J., & Panario, D. (2001). Factoring polynomials over finite fields: A survey. Journal of Symbolic Computation, 31(1–2), 3–17. https://doi.org/10.1006/jsco.1999.1002
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 Jurnal Yudistira : Publikasi Riset Ilmu Pendidikan dan Bahasa
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
