Concept

Factorization of polynomials

In mathematics and computer algebra, factorization of polynomials or polynomial factorization expresses a polynomial with coefficients in a given field or in the integers as the product of irreducible factors with coefficients in the same domain. Polynomial factorization is one of the fundamental components of computer algebra systems. The first polynomial factorization algorithm was published by Theodor von Schubert in 1793. Leopold Kronecker rediscovered Schubert's algorithm in 1882 and extended it to multivariate polynomials and coefficients in an algebraic extension. But most of the knowledge on this topic is not older than circa 1965 and the first computer algebra systems: When the long-known finite step algorithms were first put on computers, they turned out to be highly inefficient. The fact that almost any uni- or multivariate polynomial of degree up to 100 and with coefficients of a moderate size (up to 100 bits) can be factored by modern algorithms in a few minutes of computer time indicates how successfully this problem has been attacked during the past fifteen years. (Erich Kaltofen, 1982) Nowadays, modern algorithms and computers can quickly factor univariate polynomials of degree more than 1000 having coefficients with thousands of digits. For this purpose, even for factoring over the rational numbers and number fields, a fundamental step is a factorization of a polynomial over a finite field. Polynomial rings over the integers or over a field are unique factorization domains. This means that every element of these rings is a product of a constant and a product of irreducible polynomials (those that are not the product of two non-constant polynomials). Moreover, this decomposition is unique up to multiplication of the factors by invertible constants. Factorization depends on the base field. For example, the fundamental theorem of algebra, which states that every polynomial with complex coefficients has complex roots, implies that a polynomial with integer coefficients can be factored (with root-finding algorithms) into linear factors over the complex field C.

Official source

https://en.wikipedia.org/wiki/Factorization_of_polynomials

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related courses (13)

MATH-489: Number theory II.c - Cryptography

The goal of the course is to introduce basic notions from public key cryptography (PKC) as well as basic number-theoretic methods and algorithms for cryptanalysis of protocols and schemes based on PKC

ME-324: Discrete-time control of dynamical systems

On introduit les bases de l'automatique linéaire discrète qui consiste à appliquer une commande sur des intervalles uniformément espacés. La cadence de l'échantillonnage qui est associée joue un rôle

MATH-502: Distribution and interpolation spaces

The goal of this course is to give an introduction to the theory of distributions and cover the fundamental results of Sobolev spaces including fractional spaces that appear in the interpolation theor

Related people (1)

Arjen Lenstra

Related concepts (16)

Gauss's lemma (polynomials)

In algebra, Gauss's lemma, named after Carl Friedrich Gauss, is a statement about polynomials over the integers, or, more generally, over a unique factorization domain (that is, a ring that has a unique factorization property similar to the fundamental theorem of arithmetic). Gauss's lemma underlies all the theory of factorization and greatest common divisors of such polynomials. Gauss's lemma asserts that the product of two primitive polynomials is primitive (a polynomial with integer coefficients is primitive if it has 1 as a greatest common divisor of its coefficients).

Rational root theorem

In algebra, the rational root theorem (or rational root test, rational zero theorem, rational zero test or p/q theorem) states a constraint on rational solutions of a polynomial equation with integer coefficients and . Solutions of the equation are also called roots or zeros of the polynomial on the left side. The theorem states that each rational solution x = p⁄q, written in lowest terms so that p and q are relatively prime, satisfies: p is an integer factor of the constant term a0, and q is an integer factor of the leading coefficient an.

Polynomial greatest common divisor

In algebra, the greatest common divisor (frequently abbreviated as GCD) of two polynomials is a polynomial, of the highest possible degree, that is a factor of both the two original polynomials. This concept is analogous to the greatest common divisor of two integers. In the important case of univariate polynomials over a field the polynomial GCD may be computed, like for the integer GCD, by the Euclidean algorithm using long division. The polynomial GCD is defined only up to the multiplication by an invertible constant.

Official source

https://en.wikipedia.org/wiki/Factorization_of_polynomials

About this result

Related courses (13)

MATH-489: Number theory II.c - Cryptography

ME-324: Discrete-time control of dynamical systems

MATH-502: Distribution and interpolation spaces

Related lectures (29)

Complex Roots and Polynomials

Explores complex roots, polynomials, and factorizations, including roots of unity and the fundamental theorem of algebra.

Polynomial Factorization over a Field: Eigenvalues

Explores polynomial factorization over a field, emphasizing eigenvalues and irreducible components.

Complex Plane and Polynomials

Covers the complex plane, operations, transformations, and complex polynomials.

Related publications (26)

K3 surfaces, cyclotomic polynomials and orthogonal groups

Eva Bayer Fluckiger

Let X be a complex projective K3 surface and let T-X be its transcendental lattice; the characteristic polynomials of isometries of T-X induced by automorphisms of X are powers of cyclotomic polynomials. Which powers of cyclotomic polynomials occur? The ai ...

Springer Int Publ Ag2024

The multivariate Serre conjecture ring

Luc Guyot

It is well-known that for any integral domain R, the Serre conjecture ring R(X), i.e., the localization of the univariate polynomial ring R[X] at monic polynomials, is a Bezout domain of Krull dimension

Academic Press Inc Elsevier Science2023

Certification of Bottleneck Task Assignment With Shortest Path Criteria

Maryam Kamgarpour, Tony Alan Wood

Minimising the longest travel distance for a group of mobile robots with interchangeable goals requires knowledge of the shortest length paths between all robots and goal destinations. Determining the exact length of the shortest paths in an environment wi ...

2023