Division dans Z[X]
Division dans Z[X]
bonjour a tous,
je suis un cours sur l'algorithme de factorisation de Berlekamp, et j'essaie en parallele de l'implementer en C++ (en prenant un peu d'avance sur le cours). A priori, cet algo necessite de calculer des PGCD, or on se situe dans $\Z[X]$, donc je ne vois pas trop comment y implementer la division euclidienne. dois je passer par $\Q[X]$ et ensuite revenir dans $\Z$ ? ca risque de me forcer a pas mal de contorsions...
si quelqu'un a une idée, je suis preneur. accessoirement, toute indication sur une "bonne" maniere de gerer des polynmes en C++ est la bienvenue !
Merci
je suis un cours sur l'algorithme de factorisation de Berlekamp, et j'essaie en parallele de l'implementer en C++ (en prenant un peu d'avance sur le cours). A priori, cet algo necessite de calculer des PGCD, or on se situe dans $\Z[X]$, donc je ne vois pas trop comment y implementer la division euclidienne. dois je passer par $\Q[X]$ et ensuite revenir dans $\Z$ ? ca risque de me forcer a pas mal de contorsions...
si quelqu'un a une idée, je suis preneur. accessoirement, toute indication sur une "bonne" maniere de gerer des polynmes en C++ est la bienvenue !
Merci
-
- Utilisateur chevronné
- Messages : 1367
- Inscription : dimanche 30 juillet 2006, 10:04
- Localisation : Alsace
-
- Utilisateur chevronné
- Messages : 1367
- Inscription : dimanche 30 juillet 2006, 10:04
- Localisation : Alsace
-
- Modérateur général
- Messages : 8191
- Inscription : vendredi 06 janvier 2006, 15:32
- Statut actuel : Enseignant
- Localisation : Le Mans
- Contact :
Imaginons que l'on effectue l'algorithme d'Euclide (recherche du PGCD) dans $\Q[X]$. Une fois le PGCD obtenu, on le multiplie par le PPCM des dénominateurs des coefficients (ils sont en nombre fini !). On doit encore avoir un PCGD qui est dans $\Z[X]$ cette fois.
(je ne sais pas pourquoi mais j'ai l'impression de dire une bétise en conclusion)
(je ne sais pas pourquoi mais j'ai l'impression de dire une bétise en conclusion)
c'est loin d'etre idiot.. je pensais a un truc comme ca, mais peut on encore dire que le PGCD "divise" chacun des membres ? le but etant de chercher des facteurs d'un polynome donné. On pourrait aussi considerer que si les coeeficients ne se divisent pas "exactement", la division ne marche pas.. dans ce cas ca marche, mais on perd le fait que le reste est de degre inferieur au diviseur....
a priori, non, c'est pas vraiment euclidien, c'est pour ca qu'il doit y avoir une astuce ! par contre, il est principal donc on peut decomposer un polynome en facteur irreductibles ! la premiere etape consiste a trouver la partie sans facteur carré de $f$, en calculant :
$$PGCD(f,f')$$
mais comme on est dans $Z[X]$, ca me semble curieux.. meme si dans ce cas particulier, il y a plus de chances que ca tombe "juste"...
$$PGCD(f,f')$$
mais comme on est dans $Z[X]$, ca me semble curieux.. meme si dans ce cas particulier, il y a plus de chances que ca tombe "juste"...
Ou alors, une idee : on considere assi le PGCD des coefficients !!
par exemple , soif $f=4x^2$, $g=6x$. dans $\Q[X]$, on voit bien que g divise f. dans $\Z[X]$, on peut dire que le PGCD de f et g est $2x$ ?? non ?? cad qu'on prend comme coeff qui va bien PGCD(6,4)... et on n'a bien un facteur qui divise f, qui divise g et qui est maximal ! mais comme je le disais, on perd un critere sur le reste.
par exemple , soif $f=4x^2$, $g=6x$. dans $\Q[X]$, on voit bien que g divise f. dans $\Z[X]$, on peut dire que le PGCD de f et g est $2x$ ?? non ?? cad qu'on prend comme coeff qui va bien PGCD(6,4)... et on n'a bien un facteur qui divise f, qui divise g et qui est maximal ! mais comme je le disais, on perd un critere sur le reste.
-
- Modérateur général
- Messages : 8191
- Inscription : vendredi 06 janvier 2006, 15:32
- Statut actuel : Enseignant
- Localisation : Le Mans
- Contact :
Je me doutais bien qu'il ne s'agissait pas de factoriser le polynôme !jobherzt a écrit :en fait, c'est dans l'autre sens que ca se passe : on commence par calculer le pgcd de f et de f' pour enlever des facteurs faciles a trouver, et ensuite on factorise ce qui reste...
Cela dit, le pgcd est à coefficients dans $\Q$ a priori.
oui, mais a priori, si $d$ est un facteur carré de $f$ dans $\Z[X]$, alors $d$ sera bien un diviseur commun de $f$ et $f'$ toujours dans $\Z[X]$, donc on doit bien pouvoir trouver le plus grand diviseur a coefficient entiers commun a $f$ et $f'$, puisqu'il existe ! par contre, il faut peut etre passer temporairement dans $\Q[X]$ pour le trouver ! c'est un peu le sens de ma question.
-
- Utilisateur chevronné
- Messages : 1367
- Inscription : dimanche 30 juillet 2006, 10:04
- Localisation : Alsace
-
- Modérateur général
- Messages : 8191
- Inscription : vendredi 06 janvier 2006, 15:32
- Statut actuel : Enseignant
- Localisation : Le Mans
- Contact :
Pour ceux qui ont été passionné par le problème posé par jobherzt, voici des compléments d'information fournis sur le forum les-mathematiques.net :
http://les-mathematiques.u-strasbg.fr/p ... 0&t=325030
Très intéressant.
http://les-mathematiques.u-strasbg.fr/p ... 0&t=325030
Très intéressant.
La division de deux polynômes a par b dans un anneau commutatif A est possible ssi le coeff dominant de b divise tous les coeffs de a, i.e. si a a ses coeffs dans l'idéal engendré par le coeff dominant de b (ce qui doit rappeler des choses aux amateurs de berlekamperies). Autrement dit la division est possible dès que rien ne coince dans la mise en pratique de l'opération.
Concernant le rapport entre le PGCD dans Z[X] et celui dans Q[X], il faut se souvenir de ce qu'est le contenu de Gauss d'un polynôme, c'est le pgcd de ses coeffs dans Z, on dit qu'un polynôme est primitif si son contenu est 1, i.e. si on ne peut pas l'écrire a.f avec a dans Z.
Les éléments irréductibles de Z[X] sont exactement: les éléments irréductibles de Z, auxquels il faut ajouter les polynômes primitifs qui sont irréductibles dans Q[X].
Ensuite Z[X] est factoriel, et le paragraphe précédant permet de relier le calcul de pgcd dans Q[X] avec celui dans Z[X]. Mais je crois me rappeler que dans cette situation on utilise plutôt le résultant de polynômes, il y a quelques pages bien claires sur le sujet dans le livre de Bernadette Perrin-Riou intitulé "algèbre et maple".
Concernant le rapport entre le PGCD dans Z[X] et celui dans Q[X], il faut se souvenir de ce qu'est le contenu de Gauss d'un polynôme, c'est le pgcd de ses coeffs dans Z, on dit qu'un polynôme est primitif si son contenu est 1, i.e. si on ne peut pas l'écrire a.f avec a dans Z.
Les éléments irréductibles de Z[X] sont exactement: les éléments irréductibles de Z, auxquels il faut ajouter les polynômes primitifs qui sont irréductibles dans Q[X].
Ensuite Z[X] est factoriel, et le paragraphe précédant permet de relier le calcul de pgcd dans Q[X] avec celui dans Z[X]. Mais je crois me rappeler que dans cette situation on utilise plutôt le résultant de polynômes, il y a quelques pages bien claires sur le sujet dans le livre de Bernadette Perrin-Riou intitulé "algèbre et maple".
-
- Sujets similaires
- Réponses
- Vues
- Dernier message
-
- 7 Réponses
- 721 Vues
-
Dernier message par projetmbc