Séance de cours

Algorithme de Berlekamp : Facturation polynomiale

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Dans cours

MATH-489: Number theory II.d - Cryptography

. ...

Description

Cette séance de cours couvre l'application de l'algorithme de Berlekamp pour factoriser efficacement les polynômes en composants irréductibles, en mettant l'accent sur les polynômes sans carré et le calcul de gcd. L'instructeur explique le processus étape par étape, illustrant avec des exemples et des preuves.

Enseignant·e

Dimitar Petkov Jetchev

Source officielle

Concepts associés (29)

Polynôme sans carré

En mathématiques, un polynôme sans carré est un polynôme défini sur un corps (commutatif), ou plus généralement sur un anneau factoriel, qui n'a pour facteur aucun carré d'un facteur non unitaire. Dans le cas des polynômes invariables sur un corps k, cela signifie que est sans carré si et seulement si pour chaque polynôme de degré positif. Dans les applications en physique et en génie, un polynôme sans carré est communément appelé un polynôme sans racines répétées.

Factorisation des polynômes

En mathématiques, la factorisation d'un polynôme consiste à écrire celui-ci comme produit de polynômes. Les factorisations intéressantes sont celles permettant d'écrire le polynôme initial en produit de plusieurs polynômes non inversibles. Un polynôme non inversible pour lequel aucune factorisation de ce type n'existe s'appelle un polynôme irréductible. La décomposition d'un polynôme en produits de polynômes irréductibles existe, et a une propriété d'unicité (à un facteur inversible près), pour tout polynôme à coefficients réels ou complexes.

Factorization of polynomials over finite fields

In mathematics and computer algebra the factorization of a polynomial consists of decomposing it into a product of irreducible factors. This decomposition is theoretically possible and is unique for polynomials with coefficients in any 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.

Polynôme irréductible

In mathematics, an irreducible polynomial is, roughly speaking, a polynomial that cannot be factored into the product of two non-constant polynomials. The property of irreducibility depends on the nature of the coefficients that are accepted for the possible factors, that is, the field to which the coefficients of the polynomial and its possible factors are supposed to belong. For example, the polynomial x2 − 2 is a polynomial with integer coefficients, but, as every integer is also a real number, it is also a polynomial with real coefficients.

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.

Afficher plus

Séances de cours associées (43)

Polynômes : Racines et factorisation

Couvre les racines polynomiales, la factorisation et la représentation unique à travers des exemples de division polynomiale avec des restes.

Factorisation polynomiale : approche par champ

Couvre la factorisation des polynômes sur un champ, y compris la division avec le reste et les diviseurs communs.

Recherche de racines polynomiales

Explore les méthodes de recherche des racines polynômes basées sur l'évaluation des racines potentielles à partir des diviseurs du terme constant.

Factorisation polynomiale sur un champ : valeurs propres

Explore la factorisation polynomiale sur un champ, en mettant l'accent sur les valeurs propres et les composantes irréductibles.

Polynômes sur un terrain

Couvre la construction de polynômes sur un champ et le concept de polynômes minimaux.

Afficher plus

Concepts associés (29)

Polynôme sans carré

Factorisation des polynômes

Factorization of polynomials over finite fields

Polynôme irréductible

Polynomial greatest common divisor

Afficher plus