Division dans Z[X]

Discussions générales concernant les mathématiques.
[participation réservée aux membres inscrits]
Règles du forum
Merci de soigner la rédaction de vos messages et de consulter ce sujet avant de poster. Pensez également à utiliser la fonction recherche du forum.
jobherzt
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 433
Inscription : vendredi 13 janvier 2006, 13:13

Division dans Z[X]

Message non lu par jobherzt »

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
François D.
Utilisateur chevronné
Utilisateur chevronné
Messages : 1367
Inscription : dimanche 30 juillet 2006, 10:04
Localisation : Alsace

Message non lu par François D. »

Un langage comme C++ n'a pas parmi les types de variables qu'il sait manipuler le type « entier », ainsi que les opérations spécifiques associées ?

Ce serait étrange : même le bon vieux Pascal a ça ...
jobherzt
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 433
Inscription : vendredi 13 janvier 2006, 13:13

Message non lu par jobherzt »

si, mais il s'agit de division euclidienne de polynome, donc la c'est de maths que je parle, comment diviser un polynome par un autre dans $\Z[X]$ ??
François D.
Utilisateur chevronné
Utilisateur chevronné
Messages : 1367
Inscription : dimanche 30 juillet 2006, 10:04
Localisation : Alsace

Message non lu par François D. »

Ah, OK.

Euh ... mes souvenirs d'algèbre sont franchement flous, mais n'y a-t-il pas une condition minimale sur un anneau $A$ (condition que $\mathbb{Z}$ ne remplirait justment pas) pour que $A[X]$ soit euclidien et qu'une telle division devienne possible :? ?
jobherzt
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 433
Inscription : vendredi 13 janvier 2006, 13:13

Message non lu par jobherzt »

ben en theorie si, mais il parait qu'on peut quand meme se debrouiller dans $\Z[X]$.. c'st la tout le mystere de la chose !
guiguiche
Modérateur général
Modérateur général
Messages : 8128
Inscription : vendredi 06 janvier 2006, 15:32
Statut actuel : Enseignant
Localisation : Le Mans

Message non lu par guiguiche »

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)
jobherzt
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 433
Inscription : vendredi 13 janvier 2006, 13:13

Message non lu par jobherzt »

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....
guiguiche
Modérateur général
Modérateur général
Messages : 8128
Inscription : vendredi 06 janvier 2006, 15:32
Statut actuel : Enseignant
Localisation : Le Mans

Message non lu par guiguiche »

C'est vraiment euclidien $\Z[X]$ ?
Ouh là là que c'est loin tout çà.
jobherzt
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 433
Inscription : vendredi 13 janvier 2006, 13:13

Message non lu par jobherzt »

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"...
jobherzt
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 433
Inscription : vendredi 13 janvier 2006, 13:13

Message non lu par jobherzt »

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.
guiguiche
Modérateur général
Modérateur général
Messages : 8128
Inscription : vendredi 06 janvier 2006, 15:32
Statut actuel : Enseignant
Localisation : Le Mans

Message non lu par guiguiche »

Une fois $f$ factorisé, le $PGCD(f,f')$ n'est pas difficile à obtenir : il est constitué des facteurs de $f$ avec un exposant diminué de 1 (il ne reste donc que les facteurs d'ordre au moins deux au départ). Mais c'est quand même la division (et le pgcd) dans $\Q[X]$.
jobherzt
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 433
Inscription : vendredi 13 janvier 2006, 13:13

Message non lu par jobherzt »

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...
guiguiche
Modérateur général
Modérateur général
Messages : 8128
Inscription : vendredi 06 janvier 2006, 15:32
Statut actuel : Enseignant
Localisation : Le Mans

Message non lu par guiguiche »

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...
Je me doutais bien qu'il ne s'agissait pas de factoriser le polynôme !
Cela dit, le pgcd est à coefficients dans $\Q$ a priori.
jobherzt
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 433
Inscription : vendredi 13 janvier 2006, 13:13

Message non lu par jobherzt »

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.
guiguiche
Modérateur général
Modérateur général
Messages : 8128
Inscription : vendredi 06 janvier 2006, 15:32
Statut actuel : Enseignant
Localisation : Le Mans

Message non lu par guiguiche »

Je crois qu'il sera difficile de ne pas passer par le $\Q$ :lol: :lol: :lol:
François D.
Utilisateur chevronné
Utilisateur chevronné
Messages : 1367
Inscription : dimanche 30 juillet 2006, 10:04
Localisation : Alsace

Message non lu par François D. »

Voilà une remarque empreinte de finesse :D !
guiguiche
Modérateur général
Modérateur général
Messages : 8128
Inscription : vendredi 06 janvier 2006, 15:32
Statut actuel : Enseignant
Localisation : Le Mans

Message non lu par guiguiche »

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.
la main gauche

Message non lu par la main gauche »

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".