[PDF] FACTORISATION DE POLYNÔMES SUR DES CORPS FINIS 1

View - Download FACTORISATION DE POLYNÔMES SUR DES CORPS FINIS 1

Previous PDF

Next PDF

FACTORISATION DE POLYNÔMES SUR DES CORPS

FINIS

1.Introduction

La factorisation est l"un des points où l"analogie entre nombres entiers et polynômes se rompt. Par exemple, en caractéristique nulle, on peut trou- ver la partie sans facteurs carrés d"un polynôme (c"est-à-dire le produit de ses facteurs irréductibles) en utilisant la notion de dérivée, et en caractéris- tique positive, on peut aménager ce procédé. De plus, la notion de degré, la structure d"algèbre dont est muni l"ensemble de polynômes sur un corps, fournissent des outils importants pour la résolution du problème. Nous allons voir deux algorithmes. Le premier utilise trois étapes : la factorisation en un produit de polynômes sans facteurs carrés, la factorisa- tion en degrés distints, puis la factorisation en degrés égaux (algorithme de Cantor-Zassenhaus). La seconde utilise d"abord une factorisation en produit de polynômes sans facteurs carrés, puis un algorithme de factorisation dû à Berlekamp, qui utilise de l"algèbre linéaire.

2.Factorisation en degrés distincts

Ce paragraphe décrit une factorisation de polynômes sans facteurs car- rés en un produit de polynômes de degrés distincts. On utilise le théorème suivant. Théorème 2.1.Pour toutd1,xqdx2Fq[x]est le produit de tous les polynômes unitaires irréductibles deFq[x]dont le degré divised. Définition 2.2.La décomposition en degrés distincts d"un polynôme non constantf2Fq[x]est la suite(g1;:::;gs)de polynômes, oùgiest le produit de tous les polynômes unitaires irréductibles de degréiqui divisentf, avec g s6= 1. Exemple.x2+x;x4+x3+x+ 2est la décomposition en degrés distincts def=x(x+ 1)(x2+ 1)(x2+x+ 2)2F3[x]. Pour effectuer la factorisation en degrés distincts d"un polynômefsans facteurs carrés, on peut définir les éléments deR=Fq[x]=(f), pouri0: h i=xqi,f0=f,gi= (hix;fi1),fi=fi1=gi, jusqu"à ce quefi= 1. On pose alorss=iet la décomposition cherchée est(g1;:::;gs). Théorème 2.3.Cet algorithme fonctionne, et se fait en au plusO(sn2log(q)) opérations dansFq. 1

2 FACTORISATION DE POLYNÔMES SUR DES CORPS FINIS

Remarquons qu"on peut arrêter l"algorithme dès que degfi<2(i+ 1), parce-que tous les facteurs irréductibles defiont un degré supérieur ou égal ài+ 1, et donc dans ce cas,fiest irréductible.

3.Factorisation en degrés égaux (algorithme de

Cantor-Zassenhaus)

Maintenant, voyons la factorisation en degrés égaux, pour factoriser les polynômes produits par la factorisation en degrés distincts. L"algorithme décrit ici ne fonctionne que siqest impair. Lemme 3.1.Soitqune puissance d"un nombre premier impair, et soitS= (Fq)2l"ensemble des carrés deFq. AlorsSest un sous-groupe deFqd"ordre (q1)=2, égal à Ker', où'est l"homomorphisme de groupes deFqdans f1gqui àaassociea(q1)=2. Soitfun polynôme unitaire deFq[x]de degrén, et soitdun diviseur de n, tels que tous les facteurs irréductibles defont degréd. On veut trouver ces facteurs irréductibles. Il y en ar=n=d. On écritf=f1:::fr, où pour touti,fiest un polynôme unitaire irréductible de degrérdeFq[x]. On peut supposer quer2, car sinonfest irréductible. Grâce au théorème chinois, on sait qu"il existe un isomorphisme d"algèbres :R!Fq[x]=(f1):::Fq[x]=(fr) =R1 Rr; chaqueRiétant une extension algébrique deFqde degréd, donc un corps fini de cardinalqd. Pour tout élémentadeFq, on notei(a)l"image dea dansRi. Si l"on trouve un polynômeatel que certainsi(a)sont nuls et d"autres non, alors(a;f)est un diviseur non trivial def. Soite= (qd1)=2. Pour tout élémentdeRi,e2 f1g, chacune des deux possibilités ayant la même probabilité d"arriver. Si on choisita2Fq[x], de façon aléatoire, avec une loi de probabilité uniforme, premier àfde degré strictement inférieur àn, alors lesi(a)sont des éléments aléatoires avec des lois de probabilité uniformes indépendantes deF qd, et"i=i(ae)2Riest égal à1ou1, chacun avec une probabilité de1=2. Ainsi, ([ae1]f) = ("11;:::"r1); etae1décomposef, sauf si"1=="r, ce qui arrive avec probabilité 2 r+11=2. On procède de la façon suivante. On choisita2Fq[x]de degré inférieur strictement ànau hasard. Sia2Fq, on retourne : "Erreur". Ensuite, on poseg1=pgcd(a;f). Sig16= 1, on retourneg1: c"est un facteur non trivial def.

On calculeb=a(qd1)=2modf.

On calculeg2=pgcd(b1;f). Sig26= 1etg26=f, alors on retourneg2.

Sinon, on retourne "Erreur".

FACTORISATION DE POLYNÔMES SUR DES CORPS FINIS 3 Théorème 3.2.Cet algorithme de Cantor-Zassenhaus répond "Erreur" avec une probabilité inférieure à21r1=2, oùr=n=d2, ou sinon donne un facteur non trivial def. Il se fait en au plusO(dn2log(q))opérations dans F q. Ainsi, si l"on fait tourner l"algorithmekfois, la probabilité de ne pas trouver de facteurs est inférieure à2(1r)k2k. Cet algorithme donne2facteurs. Si on veut juste un facteur irréductible, on peut appliquer l"algorithme récursivement sur le plus petit facteur. Ha- bituellement, on veut lesrfacteurs irréductibles, et donc on applique l"algo- rithme récursivement sur tous les facteurs. Théorème 3.3.Par cette méthode, on factorise un polynôme de degrén= rdavecrfacteurs irréductibles de degrédavec un nombre d"opérations de

O(dn2logqlogr)en moyenne.

Pour montrer cela, on peut illustrer la méthode par un arbre. Les noeuds de l"arbre sont des facteurs def. La racine estfet les facteurs irréductibles sont les feuilles. Si l"algorithme de Cantor-Zassenhaus répond "Erreur", alors le noeud correspondant a exactement un enfant avec le même polynôme. Sinon, il a deux enfants qui contiennent les deux facteurs trouvés. Le produit sur tous les noeuds à un niveau de l"arbre est égal àf, donc la somme des degrés correspondants estn. Le coût en un noeud de degrémestO(dm2logq). Donc, le coût total à un niveau donné est deO(dn2logq). Montrons maintenant que la profondeur moyenne de l"arbre est enO(logr). Soientgetg0deux facteurs irréductibles def. La probabilité que l"algorithme de Zassenhaus séparegetg0est supérieure à1=2(s"ils n"ont pas été séparés auparavant). Donc, la probabilité pour quegetg0ne soient pas encore séparés à la profondeurkde l"arbre est au plus2k. C"est valable pour tout couple de facteurs irréductibles def. Comme il y a(r2r)=2r2tels couples, la probabilitépkque tous les facteurs irréductibles ne sont pas séparés à la profondeurkde l"arbre est au plusr22k.pkest en fait la probabilité pour que l"arbre soit de profondeur supérieure ou égale àk, etpk1pk est la probabilité pour que l"arbre soit de profondeur exactementk. Donc la profondeur en moyenne de l"arbre est égale àP k1k(pk1pk) =P k0pk. Pourk < s=d2log2re, on utilise le fait quepk1et pourksle fait que p kr22kpour montrer que cette moyenne est inférieure ou égale às+ 2, qui est enO(logr).

4.Un algorithme complet de factorisation

Soitfun polynôme qui n"est pas nécessairement sans facteurs carrés. On peut déterminer sa partie sans facteurs carrés, par un algorithme décrit dans le paragraphe suivant. Mais on peut aussi directement appliquer directement les algorithmes dé- crits dans le paragraphe précédent. En effet, soitPle polynôme à factoriser. On peut d"abord calculer le produit des facteurs irréductibles deux à deux

4 FACTORISATION DE POLYNÔMES SUR DES CORPS FINIS

distincts de degré1qui divisentP. Ensuite, on factorise complètement ce produit. Il est alors facile de déterminer la valuation dansPde chacun des facteurs irréductibles obtenus. Ensuite, on applique la même méthode pour le degré2àPdivisé par le produit de tous ses facteurs irréductibles de degré

1(avec multiplicité), et on itère le procédé.

Voyons le coût en opérations dansFq. Il est dominé parn3logqpour la factorisation en degrés distincts. Ensuite, on applique l"algorithme de Cantor- Zassenhaus aux différents facteursg1;:::;gstrouvés, respectivement de de- grésm1;:::;ms. Chacune de ces applications coûte au plusO(im2ilogqlog(mi=i)) opérations dansFq. Comme ilog(mi=i) =milog(mi=i)m i=imi; on trouve que le coût total est enO(n3logq). Le pas final, qui trouve les valuations des facteurs irréductibles, a un coût inférieur, donc en tout, l"al- gorithme est enO(n3logq).

5.Factorisation sans facteurs carrés

SoitFun corps parfait. Nous nous intéressons dans ce paragraphe à la façon de réduire le problème de la factorisation d"un polynôme au problème de la factorisation d"un polynôme sans facteurs carrés. Cette réduction est souvent utilisée dans les logiciels de calcul. Écrivons la factorisation en facteurs irréductibles d"un polynômefde

F[x].f=Qr

i=1feii, où lesfisont deux à deux distincts et leseistrictement positifs. La partie sans facteurs carrés defest égale àQr i=1fi. De plus, f 0=rX i=1e iff if0i:

Alors on peut voir que pour touti,fei1

idivisef0, et que de plus,feiine divise f

0que sieif0i= 0. Ainsi, en caractéristique nulle, la partie sans facteur carré

defestf=u, oùu=pgcd(f;f0), alors qu"en caractéristiquep, ce quotient f=uest égal àv=Q p6jeifi. Alors,u=pgcd(u;vn) =Q pjeifeii. On est donc ramené à calculer la racinepèmede ce polynôme, puis à procéder de façon récursive.

6.Algorithme de Berlekamp

Cet algorithme de factorisation utilise l"algèbre linéaire. Soitf2Fq[x]un polynôme unitaire irréductible de degrén >0, et soitR=Fq[x]=(f). Alors Rest uneFq-algèbre de dimensionn, et l"applicationdeRdansRqui àa associeaqestFq-linéaire. Soit=id. Alorsest égalementFq-linéaire. On va encore utiliser l"isomorphisme d"algèbres :R!Fq[x]=(f1) Fq[x]=(fr) =R1 Rr: FACTORISATION DE POLYNÔMES SUR DES CORPS FINIS 5 SoitB=Ker.(B)est égal àFqFq=Frq(c"est un abus de notation : c"est en fait égal au produit des images deFqdansF[x]=(fi)). SoitQla matrice dedans la base deRformée par les images de

1;x;:::;xn1dansR. L"algorithme de Berlekamp détermine dans un pre-

mier temps une baseb1;:::;brdeB, en utilisant le pivot de Gauss. Notons quefest irréductible si et seulement si le rang deQIest égal àn1. On va supposer à partir de maintenant queqest impair. Soitb=Pr i=1cibiun élément deBchoisi au hasard, où lescisont des éléments deFq. On emploi la même idée que pour la factorisation en degrés égaux. Si aucunfine divise b, alors pour touti,b(q1)=2 1modfi, et chacune des deux possibili- tés apparaît avec probabilité1=2, et ce de façon indépendante pour touti. L"algorithme suivant donne un facteur non trivial def, ou bien retourne "Erreur". On calculeg1=pgcd(b;f). Sig16= 1, on termine l"algorithme :g1est un facteur def.

On calculea=b(q1)=2.

On calculeg2=pgcd(a1;f). Sig26= 1etg26=f, alors on retourneg2, sinon, on retourne "Erreur". Théorème 6.1.Cet algorithme répond "Erreur" avec une probabilité infé- rieure à1=2, ou sinon donne un facteur non trivial def. Il se fait en au plus

O(n3+n2logq)opérations dansFq.

Si l"on veut une factorisation complète def, on se contente de calculer une base deBune fois pour toute, puis on applique le reste de l"algorithme récursivement àgetf=g, oùgest le facteur trouvé. Une analyse semblable à celle correspondant à l"algorithme de factorisation en degrés égaux montre que le coût en moyenne est deO(n3+n2logq)opérations dansFq. Référence :Modern computer algebra (Von zur Gathen et Gerhard).quotesdbs_dbs47.pdfusesText_47

[PDF] methode de gauss (systeme lineaire)

[PDF] méthode de gauss jordan exercices corrigés

[PDF] méthode de gauss matrice

[PDF] méthode de gauss matrice pdf

[PDF] methode de gauss resolution systeme

[PDF] méthode de gestion du temps pdf

[PDF] methode de horner

[PDF] methode de l'anthropologie

[PDF] méthode de la sécante exercice corrigé

[PDF] méthode de la sécante python

[PDF] methode de la variation de la constant

[PDF] methode de lecture syllabique gratuite

[PDF] méthode de lecture syllabique pour apprendre ? lire pas ? pas pdf

[PDF] methode de maintenance pdf

[PDF] Méthode de Mémoire