Factorization of polynomials over finite fields: Difference between revisions

Revision as of 15:43, 23 January 2021

Revision as of 19:04, 6 March 2021

Line 85:

'''Output'''(''R'')

The idea is to identify the product of all irreducible factors of ''f'' with the same multiplicity. This is done in two steps. The first step uses the formal derivative of ''f'' to find all the factors with multiplicity not divisible by ''p''. The second step identifies the remaining factors. As all of the remaining factors have multiplicity divisible by ''p'', meaning they are powers of ''p'', one can simply take the ''p''-th square root and apply recursion.

====Example of a square-free factorization====

Line 100:

:<math> f= (x+1)(x^2+1)^3(x+2)^4.</math>

===Distinct-degree factorization===

Line 290 ⟶ 289:

*KEMPFERT,H (1969) [https://www.sciencedirect.com/science/article/pii/0022314X69900304/pdf?md5=c31af090ceec6b08d71eedf57d709ab0&isDTMRedir=Y&pid=1-s2.0-0022314X69900304-main.pdf&_valck=1 On the ''Factorization of Polynomials''] Department of Mathematics, The Ohio State University,Columbus,Ohio 43210

*Shoup,Victor (1996) ''[https://www.shoup.net/papers/smooth.ps Smoothness and Factoring Polynomials over Finite Fields]'' Computer Science Department University of Toronto

* [[Joachim von zur Gathen|Von Zur Gathen, J.]]; Panario, D. (2001). [https://dx.doi.org/10.1006/jsco.1999.1002 Factoring Polynomials Over Finite Fields: A Survey]. [[Journal of Symbolic Computation]], Volume 31, Issues 1-21–2, January 2001, 3--17.

*Gao Shuhong, Panario Daniel,''Test and Construction of Irreducible Polynomials over Finite Fields'' Department of mathematical Sciences, Clemson University, South Carolina, 29634-190729634–1907, USA. and Department of computer science University of Toronto, Canada M5S-1A4

*Shoup, Victor (1989) [https://www.ams.org/journals/mcom/1990-54-189/S0025-5718-1990-0993933-0/S0025-5718-1990-0993933-0.pdf New Algorithms for Finding Irreducible Polynomials over Finite Fields] Computer Science Department University of Wisconsin&ndash;Madison

*[[Keith Geddes|Geddes, Keith O.]]; Czapor, Stephen R.; Labahn, George (1992). [https://dx.doi.org/10.1007/b102438 Algorithms for computer algebra]. Boston, MA: Kluwer Academic Publishers. pp. xxii+585. {{ISBN|0-7923-9259-0}}.