Discussion :

[Batoche]

Je suis actuellement sur un projet d'informatique (factorisation de polynomes), et évidemment, je rencontre une multitude de problèmes dont celui-ci :

J'ai une fonction qui me calcule la division euclidienne de deux polynomes, et je souhaiterais adapter cette fonction pour qu'elle fasse des divisions entre polynomes "modulés".

La version actuelle de la division multiplie le dividende par un nombre donné () assurant que tous les coefficients durant l'opération restent entiers.

Mais, les résultats obtenus par cette fonction en appliquant un modulo ne correspondent pas avec ceux de GIAC (ou autre logiciel de calcul formel) :

Exemple :
En modulo 5 :


==> Je trouve (ce qui correspond à 5x^2 -11x -1 sans le modulo)

==> GIAC trouve : .

Je pense que j'ai faux car la méthode du multiplicateur du dividende ne fonctionne pas dans ce cas, mais je n'en suis pas sûr ...

Si quelqu'un ici connait la solution (sans employer des mots compliqués de type (...)anneaux(...)injectif(...)corps(...)) à ce problème, ça m'arrangeait ...

beaucoup.

Merci

PS : J'utilise les docs suivantes comme support :
http://batoche.free.fr/Polynomes/factorisation.pdf
http://batoche.free.fr/Polynomes/pgcd.pdf

[Zavonen]

Difficile de parler de polynômes, de divisibilité, de quotient, de reste, etc... sans parler d'anneaux et de corps.
Essayons de faire simple: Les coefficients d'un polynôme doivent se trouver dans un même ensemble ou les opérations usuelles (+,x) aient un sens, et obéissent à certaines règles usuelles du calcul algébrique ce sont précisémment les anneaux (Z, Q, R, , etc...).
Les corps sont les anneaux où tous les éléments non nuls sont inversibles (Q,R,C, mais pas Z...)
Les entiers modulés Z/nZ forment dans tous les cas un anneau. On peut donc parler de l'ensemble des polynômes à coefficients 'modulés'. Cependant, tous les Z/nZ n'ont pas été créés égaux.
Pour pouvoir parler de divisibilité etc.. il faut avoir la notion de degré. La notion de degré elle-même n'est manipulable que quand elle satisfait certaines relations simples du genre degré(pq)=degre(p)+degre(q). Pour qu'il en soit ainsi, il ne faut pas se trouver dans des cas d'anneaux où on peut avoir un produit ab nul avec les deux facteurs non nuls (anneaux dit 'intègres). C'est par exemple le cas avec 2 et 4 dans les entiers modulo 8. Pour en revenir à vos polynomes 'modulés' pour avoir un minimum de résultats il faut se placer dans le cas où Z/nZ est intègre.
Or on dispose d'un résultat très connu:
Z/nZ intègre équivaut à Z/nz corps équivaut à n nombre premier.
Il convient donc de perdre d'entrée tout espoir d'arriver à des algorithmes avec des entiers modulés n'offrant pas les garanties minimum, c'est à dire quand n est non premier.
Cela dit les algos de division pour les polynômes à coefficients modulés sont exactement les MEMES que pour les autres (les polynômes 'courants') à coefficients rationnels, réels ou complexes. Il n'y a rien à changer mais il faut faire les calculs avec les règles des entiers modulés:
Par exemple en modulo 5:
2+4 = 1
2*4=3
etc...
Ce qui pertube les gens c'est que dans le cas des polynômes modulés il n'y a pas équivalence entre les polynômes 'formels' et les 'fonctions polynômes'. Ainsi pour reprendre votre exemple du modulo 5, on peut montrer que le polynôme X^4-1 correspond à la fonction nulle. Tout entier x modulo 5 vérifie x^4=1, mais ce n' est évidemment pas le polynôme nul. Dans les cas usuels (Q, R) il y a identification entre polynômes et fonctions polynômes ce qui permet de bâtir des algos en utilisant les 'valeurs' des polynômes (interdit pour les entiers modulés).
Il est facile d'écrire des fonctions qui font les opérations dans Z/nZ pour n premier et de faire des divisions standard. Je le repète il n'y a rien à toucher par rapport aux algos standard.
Dans le cas que vous citez, vous ne pouvez avoir raison à cause du degré.
Je reste à votre dispo pour d'autres questions sur ce sujet et éventuellement des algos de calcul si vous en avez besoin.

[Nemerle]

Tu peux effectivement toujours effectuer ta décomposition de Bezout D'ABORD dans Z[x], puis tu la projettes dans Z/nZ[x] (que n soit premier ou pas, on s'en fou). Le problème vient de ton calcul:

==> Je trouve (ce qui correspond à 5x^2 -11x -1 sans le modulo)

5x^2 -11x -1 sans modulo me semble faux. Après recalcul + vérifications (sous Excel ), on a dans Z[x]

8(x^5-x) = (2x^3-x^2+x+1)(4x^2+2x-1) -7x^2-9x+1

En projectant dans Z/5Z[x], il vient

3^(x^5-x) = (2x^3-x^2+x+1)(-x^2+2x-1) - 2x^2+x+1
0 = (2x^3-x^2+x+1)(-x^2+2x-1) - 2x^2+x+1

car x^5=x dans Z/5Z[x] puisque 5 est premier.

Dans Z/nZ[x], que l'on soit dans un corps ou un anneau, la décomposition de Bezout (=ta division) se calcule toujours d'abord dans Z[x], puis en "modulant" les coefficients.

Que n soit premier ou pas, tu n'a bien sur pas unicité de tes coefficients (ex: x=-(n-1)x dans Z/nZ[x]), SAUF si n est est premier et que tu IMPOSES que tes coefficients soient dans 0,...,n-1.

Mathématiquement, la surjection naturelle de Z sur Z/nZ est multiplicative, donc passe aux polynomes.

[Batoche]

Merci pour vos participations, j'ai résolu mon problème aujourd'hui, et comme d'habitude, ce n'était pas une faute de compréhension mais bien d'inatention :

Effectivement, on ne trouve pas -x-1 pour mon exemple (j'ai du me gourrer en recopiant le post, en réalité, je trouvais -7x^2-9x+1.

Dans ma tête, dans Z/5Z, cela faisais -2x^2-2x+1, or, si on multiplie ce poly par -3 (tjs dans Z/5Z), on obtient bien 6x^2 + 6x - 3 soit x^2+x+2

[jobherzt]

Tu peux effectivement toujours effectuer ta décomposition de Bezout D'ABORD dans Z[x], puis tu la projettes dans Z/nZ[x] (que n soit premier ou pas, on s'en fou).

euh, je trouve ca bizzare de dire ca.. l'anneau Z[X] n'est pas euclidien, or pour pouvoir trouver des coefficients de bezout il faut une division effective. On peut se depatouiller, mais c'est pas forcement simple. En revanche, pour n premier, Z/nZ est un corps, donc les coefficients sont inversible et donc la division se fait tres facilement !

[Nemerle]

euh, je trouve ca bizzare de dire ca.. l'anneau Z[X] n'est pas euclidien, or pour pouvoir trouver des coefficients de bezout il faut une division effective. On peut se depatouiller, mais c'est pas forcement simple. En revanche, pour n premier, Z/nZ est un corps, donc les coefficients sont inversible et donc la division se fait tres facilement !

La surjection s:Z[X]->Z/nZ[X] est un homomorphisme d'anneau: s(ap+bq)=as(p)+bs(q), et s(pq)=s(p)s(q). Par contre, je suis d'accord avec toi, toute décomposition P/Q=AQ+B dans Z[X] ne "passe" pas dans Z/nZ[X], mais à un "multiple près".

Ce qui revient effectivement à dire que la "division" P/Q=AQ+B s'effectue en considérant un multiple de P: P/Q ne fournit pas toujours des polynomes A,B à coefficients dans Z, mais dans Q. Par contre si r est le ppcm des dénominateurs des coefficients des polynomes A et B, on a rP=(rA)Q+(rB), où rA et rB sont bien dans Z[X].

En résumé: on travaille la decomp P/Q en fait dans Q[X], en prend la surjection de Q[X] dans Z[X] par mutiplication du ppcm des dénominateurs, PUIS seulement on passe à Z/nZ[X]. Donc tu travailles avec rP/Q, pas P/Q, et si r admet un inverse mutiplicatif dans Z/nZ[X], alors tu peux repasser à P/Q au lieu de rP/Q...

J'aurais donc du dire "tu fais ta decomp P/Q à un multiple près dans Z[X]..."