Factorization of polynomials over finite fields: Difference between revisions

Revision as of 16:34, 13 December 2023

Latest revision as of 07:47, 21 July 2025

(5 intermediate revisions by 4 users not shown)

Line 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 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 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 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 284:

[[Category:Cryptography]]

[[Category:Computational number theory]]

[[Category:PolynomialsPolynomial factorization algorithms]]