Factorization of polynomials over finite fields: Difference between revisions

Revision as of 17:18, 13 May 2023

Latest revision as of 07:47, 21 July 2025

(9 intermediate revisions by 7 users not shown)

Line 19:

Irreducible polynomials allow us to construct the finite fields of non-prime order. In fact, for a prime power ''q'', let '''F'''_''q'' be the finite field with ''q'' elements, unique up to isomorphism. A polynomial ''f'' of degree ''n'' greater than one, which is irreducible over '''F'''_''q'', defines a field extension of degree ''n'' which is isomorphic to the field with ''q''^''n'' elements: the elements of this extension are the polynomials of degree lower than ''n''; addition, subtraction and multiplication by an element of '''F'''_''q'' are those of the polynomials; the product of two elements is the remainder of the division by ''f'' of their product as polynomials; the inverse of an element may be computed by the extended GCD algorithm (see [[Polynomial greatest common divisor|Arithmetic of algebraic extensions]]).

It follows that, to compute in a finite field of non prime order, one needs to generate an irreducible polynomial. For this, the common method is to take a polynomial at random and test it for irreducibility. For sake of efficiency of the multiplication in the field, it is usual to search for polynomials of the shape ''x''^''n'' + ''ax'' + ''b''.{{Citation needed|date=February 2014}}<ref>{{Cite web |title=Reducibility over $\mathbb{Z}_2$? |url=https://math.stackexchange.com/questions/28281/reducibility-over-mathbbz-2 |access-date=2023-09-10 |website=Mathematics Stack Exchange |language=en}}</ref>

Irreducible polynomials over finite fields are also useful for [[pseudorandom]] number generators using feedback shift registers and [[discrete logarithm]] over '''F'''_2^''n''.

Line 49:

{{main article|Berlekamp's algorithm}}

The Berlekamp's algorithm is historically important as being the first factorization algorithm, which works well in practice. However, it contains a loop on the elements of the ground field, which implies that it is practicable only over small finite fields. For a fixed ground field, its [[time complexity]] is polynomial, but, for general ground fields, the complexity is exponential in the size of the ground field.

=== Square-free factorization ===

{{main|Square-free factorization}}

The algorithm determines a [[square-free polynomial|square-free]] factorization for polynomials whose coefficients come from the finite field '''F'''_''q'' of order {{nowrap|1=''q'' = ''p''^''m''}} with ''p'' a prime. This algorithm firstly determines the [[derivative]] and then computes the gcd of the polynomial and its derivative. If it is not one then the gcd is again divided into the original polynomial, provided that the derivative is not zero (a case that exists for non-constant polynomials defined over finite fields).

This algorithm uses the fact that, if the derivative of a polynomial is zero, then it is a polynomial in ''x''^''p'', which is, if the coefficients belong to '''F'''_''p'', the ''p''th power of the polynomial obtained by substituting ''x'' by ''x''^1/''p''. If the coefficients do not belong to '''F'''_''p'', the ''p''th root of a polynomial with zero derivative is obtained by the same substitution on ''x'', completed by applying the inverse of the [[Frobenius endomorphism|Frobenius automorphism]] to the coefficients. {{Citation needed|date=December 2020}}

This algorithm works also over a field of [[characteristic (algebra)|characteristic]] zero, with the only difference that it never enters in the blocks of instructions where ''p''th roots are computed. However, in this case, [[Square-free polynomial#Yun's algorithm|Yun's algorithm]] is much more efficient because it computes the greatest common divisors of polynomials of lower degrees. A consequence is that, when factoring a polynomial over the integers, the algorithm which follows is not used: one first computes the square-free factorization over the integers, and to factor the resulting polynomials, one chooses a ''p'' such that they remain square-free modulo ''p''.

Line 123 ⟶ 124:

The correctness of the algorithm is based on the following:

<blockquote>{{Anchor|lemma}}'''Lemma.''' For ''i'' ≥ 1 the polynomial

: <math>x^{q^i}-x \in \mathbf{F}_q[x]</math>

is the product of all monic irreducible polynomials in '''F'''_''q''[''x''] whose degree divides ''i''.</blockquote>

Line 229 ⟶ 230:

== Rabin's test of irreducibility ==

Like distinct-degree factorization algorithm, Rabin's algorithm<ref>{{cite journal |last1=Rabin |first1=Michael |year=1980 |title=Probabilistic algorithms in finite fields |journal=SIAM Journal on Computing |volume=9 |issue=2 |pages=273–280 |doi=10.1137/0209024 |citeseerx=10.1.1.17.5653 }}</ref> is based on the Lemma[[#lemma|lemma]] stated above. Distinct-degree factorization algorithm tests every ''d'' not greater than half the degree of the input polynomial. Rabin's algorithm takes advantage that the factors are not needed for considering fewer ''d''. Otherwise, it is similar to distinct-degree factorization algorithm. It is based on the following fact.

Let ''p''₁, ..., ''p_k'', be all the prime divisors of ''n'', and denote <math>n/p_i=n_i</math>, for 1 ≤ ''i'' ≤ ''k'' polynomial ''f'' in '''F'''_''q''[''x''] of degree ''n'' is irreducible in '''F'''_''q''[''x''] if and only if <math> \gcd \left (f,x^{q^{n_i}}-x \right )=1</math>, for 1&nbsp;≤&nbsp;''i''&nbsp;≤&nbsp;''k'', and ''f'' divides <math>x^{q^n}-x</math>. In fact, if ''f'' has a factor of degree not dividing ''n'', then ''f'' does not divide <math>x^{q^n}-x</math>; if ''f'' has a factor of degree dividing ''n'', then this factor divides at least one of the <math>x^{q^{n_i}}-x.</math>

Line 260 ⟶ 261:

==References==

{{Refbegin}}

*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–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–1907, USA. and Department of computer science University of Toronto, Canada M5S-1A4

Line 274 ⟶ 275:

* Some irreducible polynomials http://www.math.umn.edu/~garrett/m/algebra/notes/07.pdf

* Field and Galois Theory :http://www.jmilne.org/math/CourseNotes/FT.pdf

* Galois Field:http://designtheory.org/library/encyc/topics/gf.pdf {{Webarchive|url=https://web.archive.org/web/20101215224628/http://designtheory.org/library/encyc/topics/gf.pdf |date=2010-12-15 }}

* Factoring polynomials over finite fields: http://www.science.unitn.it/~degraaf/compalg/polfact.pdf {{Webarchive|url=https://web.archive.org/web/20110721233946/http://www.science.unitn.it/~degraaf/compalg/polfact.pdf |date=2011-07-21 }}

[[Category:Polynomials]]

Line 283 ⟶ 284:

[[Category:Cryptography]]

[[Category:Computational number theory]]

[[Category:PolynomialsPolynomial factorization algorithms]]