Factorization of polynomials over finite fields: Difference between revisions

Revision as of 19:42, 16 August 2018

Revision as of 15:35, 20 August 2018

Line 1:

In [[mathematics]] and [[computer algebra]] the [[factorization of polynomials|factorization of a polynomial]] consists of decomposing it into a [[product (mathematics)|product]] of [[irreducible polynomial|irreducible factors]]. This decomposition is theoretically possible and is unique for [[polynomial]]s with [[coefficient]]s in any [[field (mathematics)|field]], but rather strong restrictions on the field of the coefficients are needed to allow the computation of the factorization by means of an [[algorithm]]. In practice, algorithms have been designed only for polynomials with coefficients in a [[finite field]], in the [[field of rationals]] or in a [[finitely generated field extension]] of one of them.

TheAll case of the '''factorization of [[univariate]] polynomials over a finite field'''algorithms, which is the subject of this article, is especially important, because all the algorithms (including the case of multivariate polynomials over the rational numbers), which are sufficiently efficient to be implemented, reduce the problem to this case (see [[Polynomialpolynomial factorization]]). It is also interestingused for various applications of finite fields, such as [[coding theory]] ([[cyclic redundancy]] codes and [[BCH code]]s), [[cryptography]] ([[public key cryptography]] by the means of [[elliptic curve cryptography|elliptic curves]]), and [[computational number theory]].

As the reduction of the factorization of [[multivariate polynomial]]s to that of univariate polynomials does not have any specificity in the case of coefficients in a finite field, only polynomials with one variable are considered in this article.