[PDF] [PDF] Factorisation des polynômes

View - Download [PDF] Factorisation des polynômes

Previous PDF

Next PDF

Factorisation des polynômes

Préparation à l"agrégation - option Calcul formel

Antoine Chambert-Loir

Résumé. -On expose dans ce petit cours la factorisation des polynômes (surtout en une indéterminée) à coefficients dans un corps fini ou dansZ.1. Cas des corps finis

1.1. Rappels sur les corps finis. -SoitFun corps fini; notonsqson cardinal.

La caractéristique deF, générateur de l"idéal de l"homomorphisme canonique deZdansF, est un nombre premierp. Cet homomorphisme se factorise en un homomorphisme injectif deZ/pZdansFqui permet de considérerFcomme un (Z/pZ)-espace vectoriel, de dimension nécessairement finie, disonseet l"on aq=pe. Le groupe multiplicatif deFest un groupe d"ordreq-1. Les éléments non nuls deFvérifient doncxq-1= 1; les éléments deFvérifient ainsixq=x.Le groupe multiplicatifF?est un groupe cyclique.Il faut démontrer queF?contient un élément d"ordre multiplicatifq-1. Il y a quarante démonstrations possibles, en voilà quelques unes : - le groupeF?est un groupe abélien fini, donc de la formeZ/d1Z×···×Z/drZ, où d

1,...,drsont des entiers strictement positifs tels qued1|d2|···|dr. En particulier,

d

1···dr=q-1. De plus, tout élémentxdeF?vérifiexdr= 1. Or, cette dernière

équation n"admet au plus quedrsolutions, car il s"agit d"une équation polynomiale dans un corps commutatif. Conclusion :q-1 =d1···dr?drce qui imposer= 1 etF??(Z/drZ). - soitq-1 =??niila factorisation deq-1. Soit?iun facteur premier deq-1; l"équationx(q-1)/?i= 1a au plus(q-1)/?solutions dansF?, car c"est une équation polynomiale. Il existe donc un élémentxi?F?tel quex(q-1)/?ii?= 1. Posons alors y i=x(q-1)/?niii; on ay?niii=xq-1 i= 1maisy?ni-1 ii?= 1; autrement dit,yiest un élément d"ordre?niideF?. Comme les entiers?niisont premiers entre eux deux à deux, il est alors facile de vérifier que?yiest un élément d"ordre??nii=q-1; c"est un générateur deF?. - Étant donnés deux élémentsxetyd"ordreaetbd"un groupe abélien, on peut construire un élémentzdont l"ordre est le ppcm deaetb. Par récurrence, on en déduit l"existence d"un élément deF?dont l"ordre, disonsm, est le plus petit commun multiple des ordres des éléments deF?. Tout élémentxdeF?vérifiexq-1= 1donc l"ordre d"un élément diviseq-1etmdiviseq-1. Par définition dem, tout élémentx

2ANTOINE CHAMBERT-LOIR

deF?vérifie de plusxm= 1. Cette dernière équation n"ayant au plus quemsolutions, on a doncm=q-1. - On construit par récurrence surnles polynômes cyclotomiquesΦn?Z[X], reliés par la formuleXn-1 =? d|nΦd(X). Les racines deXn-1dans un corpsK de caractéristique ne divisant pasnsont simples, ce sont les racinesn-ièmes de l"unité. En particulier, les racines deΦndans un tel corps sont simples et sont les racinesn-ièmes de l"unité qui ne sont pas racines d"un polynômeΦd, pourd|net d?=n, donc les racines primitivesn-ièmes de l"unité. Ce sont les éléments d"ordren dansK. En prenant pour corpsKle corps des nombres complexes, on voit que deg(Φ n)est l"indicateur d"Euler?(n). Prenons maintenant pour corpsKle corps finiFet posonsn=q-1. Tout élément deF?est racine d"un desΦd, pourd divisantn, mais les racines des polynômesΦdpourd|netd?=nne fournissent qu"au plusn-?(n)racines. Autrement dit,Φnpossède des racines dansF; une telle racine est une racine primitiven-ième de l"unité, donc un générateur deF?. Cet argument montre qu"en fait, pour tout entierddivisantq-1, le polynômeΦd est scindé dansF. Les deux dernières méthodes fournissent des méthodes pratiques efficaces, pourvu qu"on connaisse une factorisation deq-1. SoitKun corps de caractéristiquep. L"applicationσdeKdans lui-même donnée parσ(x) =xpest un homomorphisme de corps. Seule l"additivité n"est pas évidente; elle résulte de la formule du binôme et de ce que les coefficients?p k?sont multiples deppour1?k?p-1. Il est injectif comme tout homomorphisme de corps. SiK est un corps fini, il est alors surjectif; on l"appelle l"automorphisme de Frobenius. Soit¯Fun corps algébriquement clos de caractéristiquep. Soitq=peune puissance

dep. L"ensembleFqdes éléments de¯Fvérifiantσe(x) =x(oùσe=σ···σest le

composé deefoisσ) est un sous-corps de¯F. Commeσe(x) =xpepour toutx,Fq est l"ensemble des solutions de l"équation polynomialexq-x= 0dans¯F. La dérivée de ce polynôme étant-1, ses racines sont simples; autrement dit,Fqest un corps de cardinalq. Inversement, les éléments d"un sous-corps de cardinalqvérifient cette équationxq=x, si bien que le corpsFqtrouvé est l"unique sous-corps de cardinalq de¯F. SiFest un corps de cardinalq, la théorie des extensions de corps apprend qu"on peut prolonger l"homomorphisme deZ/pZdans¯Fen un plongement deFdans¯F; son image est un corps de cardinalqdans¯F: c"est le corpsFq. En particulier, les corpsKetFsont isomorphes. On résume ces deux paragraphes en disant qu"il existe, pour toute puissanceqd"un nombre premier, un corps fini de cardinalqet que deux tels corps sont isomorphes (" existence et unicité des corps fini de cardinal donné »). SoitFun corps fini de cardinalq=pe. Le corpsFpossède des éléments primitifs, c"est-à-dire des élémentsxtels queF=Fp[x]. On peut par exemple prendre un générateur du groupe multiplicatifF?(tout élément non nul est alors une puissance dex, a fortiori un polynôme enxà coefficients dansZ/pZ). Le polynôme minimal dexest de degrée.

FACTORISATION DES POLYNÔMES3

En particulier, le polynôme minimal d"un générateur quelconque du groupe mul- tiplicatifF?est de degrée. Les facteurs irréductibles sur(Z/pZ)du polynôme cy- clotomiqueΦq-1sont donc tous de même degrée. (Cela implique au passage que ?(qe-1)est multiple dee.) Pour construire explicitement un corps fini de cardinalpe, on peut à l"inverse exhiber un polynôme irréductiblefde degréeà coefficients dansZ/pZ. L"algèbre F= (Z/pZ)[x]/(f(x))sera alors un corps, et de dimensionesur(Z/pZ), donc de cardinalpe.

1.2. Rappels sur le calcul de pgcd. -Le pgcd de deux polynômes à coefficients

dans un corps se calcule par l"algorithme d"Euclide. (L"algorithme d"Euclide étendu fournit en outre une relation de Bézout.) Il convient de faire quelques remarques sur la façon de mener ces algorithmes et leur complexité. Chaque étape de l"algorithme requiert de calculer le resterde la division eucli-

dienne d"un polynômeapar un polynômeb. La méthode naïve enseignée à l"école fait

successivement décroître le degré dead"une unité et requiert(deg(a)-deg(b))deg(b) multiplications dans le corpsF. On peut raisonner autrement et considérer qu"il s"agit de calculer l"image parade la classe dexdansF[x]/(b). Sia=xm, l"algorithme d"exponentiation rapide requiert 2log

2(m)multiplications dansF[x]/(b).In fine, et en multipliant naïvement dans

F[x]/(b), on a besoin d"en groslog(deg(a))w(a)deg(b)2multiplications dansF, où w(a)désigne le nombre de monômes non nuls dea. C"est comme cela qu"il faut procéder sian"a que peu de monômes, notamment siaest de la formexq-x: la comparaison delog(q)deg(b)2etqdeg(b)est sans appel!

1.3. Critères d"irréductibilité. -SoitFun corps fini de cardinalqet soitf?

F[x]un polynôme de degrén. Il s"agit pour l"instant de décider sifest irréductible ou non.

1.3.1. Élimination des facteurs multiples. -Le premier pas consiste à dé-

tecter les facteurs multiples en dérivant. Un polynômegtel queg?= 0est un polynôme enxp; comme tout élément deF est une puissancep-ième, chacun des monômes degest une puissance dep, donc gaussi. En particulier,gn"est pas irréductible. Dans l"autre sens, la dérivée d"un polynôme irréductible est non nulle.

Notonsf=?r

i=1feiila décomposition defen facteurs irréductibles. Supposons f ??= 0, de sorte qu"au moins un desein"est pas multiple dep. Dans la décomposition f ?=r? i=1e ifei-1 if?i? j?=ifej j, le polynômefiapparaît avec multiplicitéeidans chacun des termes d"indicej?=i; il apparaît avec multiplicitéei-1dans le terme d"indiceisiein"est pas multiple

4ANTOINE CHAMBERT-LOIR

dep. En comparant avecf, on voit donc que pgcd(f,f?) =r? i=1p?eif ei-1 ir i=1p|eif eii. Par suite,g1=f/pgcd(f,f?)est le produit des facteurs irréductiblesfipour lesquels e in"est pas multiple dep. On peut réitérer le procédé avecf/g1qui a la même décomposition en facteurs irréductibles quef, les exposants non multiples depayant diminué de1. On obtient alors le produitg2des facteurs irréductiblesfipour lesquelse1?2mais niei(ei-1) n"est pas multiple dep. Au bout dep-1opérations, l"exposant defidans la décomposition def/g1···gp-1 est le plus grand multiple depinférieur ou égal àei. Ce polynôme est donc la puissancep-ième d"un polynômehqu"on peut déterminer explicitement et avec lequel on continue. Proposition 1.3.2. -Pour quefsoit irréductible, il faut et il suffit que les poly- nômesxqe-xetf, pour1?e < n, soient premiers entre eux. Démonstration. - Soitξune racine defdans une clôture algébrique¯FdeF. Son polynôme minimalgest irréductible et divisef, donc est un facteur irréductible def. En outre, le corpsF[ξ]engendré parξest un corps fini de cardinalqe, où e= deg(g). Il en résulte queξqe=ξ, autrement dit les polynômesxqe-xetfont une racine commune dans¯F. Cela entraîne que leur pgcd n"est pas égal à1. Inversement, sifetxqe-xont un facteur irréductible commun, celui-ci sera de

degré au pluse, donc distinct defsie < n.On peut généraliser ce résultat pour obtenir une factorisation defen un produit

de polynômesfe, chaque facteur irréductible defeétant de degrée. Pour simplifier, on suppose quefest sans facteur multiple. Proposition 1.3.3. -Soitf?F[x]un polynôme sans facteur multiple. Posons g

0=f; poure?1, posonsfe= pgcd(xpe-x,ge-1)etge=ge-1/fe. On af=

f

1f2···et pour toute?1, chaque facteur irréductible defeest degrée.

Démonstration. - Fixons pour la démonstration une clôture algébrique deFet notonsFqel"unique sous-corps deFde cardinalFqe. Comme dans la démonstration précédente, les racines def1sont les racines def qui appartiennent àFq. Comme les racines defsont simples, il en est de même de celles def1et le polynômef1est le produit des facteurs linéaires qui divisentf. Les racines def2sont les racines deg1=f/f1qui appartiennent àFq2; ce sont donc les racines defqui appartiennent àFq2mais pas àFq(ces dernières sont racines def1et ne sont plus racines deg1car les racines defsont simples). Par récurrence, les racines defesont les racines defqui appartiennent àFqemais à aucun des corpsFqrpour1?r < e; l"extension deFqengendrée par une telle racine estFqe, si bien que son polynôme minimal est de degrée.

FACTORISATION DES POLYNÔMES5

Le dernier critère, dû àBerlekamp, fournit le nombre de facteurs irréductibles def. Proposition 1.3.4. -Notonsnle degré def; pour1?e < n, soitgele reste de la division euclidienne du polynômexqe-xeparf. Soitkle rang du sous-espace deF[x]engendré par les polynômesg1,...,gn-1. Le nombre de facteurs irréductibles distincts defest égal àn-k. Avant de démontrer cette proposition, insistons sur le fait que pour calculer en pratique lesge, il importe de calculerxqdansF[x]/(f)à l"aide de l"algorithme d"exponentiation rapide puis calculer ses puissances. Démonstration. - SoitAl"algèbreF[x]/(f)et munissons-la de la base(1,x,...,xn-1). Soitσl"application deAdans elle-même donnée parσ(a) =aq. C"est un homo- morphisme d"algèbres. On a par définition0 =σ(1)-1etge=σ(xe)-xepour

1?e < n. La proposition équivaut donc à l"énoncé :le noyau deσ-idest un

F-espace vectoriel de dimension égale au nombrerde facteurs irréductibles def. NotonsBle noyau deσ-id. C"est l"ensemble des élémentsa?Atels queσ(a) =a; c"est donc une sous-algèbre deAqu"on appellela sous-algèbre de Berlekamp deA.

Nous allons montrer qu"elle est isomorphe àFr.

Écrivons la décomposition defen produits de facteurs irréductibles,f=f1···fr. Ils sont premiers entre eux deux à deux; d"après le lemme chinois, l"algèbreAest donc isomorphe à?r i=1F[x]/(fi)etσs"identifie à l"endomorphisme(a1,...,ar)?→ (aq

1,...,aqr). Par suite, l"image deBpar l"isomorphisme chinois est l"ensemble des

(a1,...,ar)tels queaq i=aipour touti. Commefiest irréductible,F[x]/(fi)est un corps fini de cardinalqdeg(fi)et l"ensemble desai?F[x]/(fi)tels queaq i=aiest le sous-corps àqéléments, c"est-à-direF. Autrement dit, l"image deBest l"algèbre

F× ···F; elle est de dimensionrsurF.1.4. Algorithme de Cantor-Zassenhaus (1981). -Il s"agit maintenant, étant

donné un polynômefà coefficients dans un corps finiF, supposé sans racines multiples, de le factoriser. On suppose que tous ses facteurs irréductibles sont de même degré, ce qui est loisible compte tenu des résultats du paragraphe précédent. Notonsf=f1···frla factorisation defetele degré desfi, de sorte quen= deg(f) =er. L"algèbreA=F[x]/(f)est isomorphe à(Fqe)r.

Lemme 1.4.1. -SoitKun corps fini de cardinalq.

Supposonsqimpair. L"applicationu?→u(q-1)/2deKdans lui-même prend une fois la valeur0(pouru= 0),(q-1)/2fois la valeur1(lorsqueuest un carré non nul) et(q-1)/2fois la valeur-1(sinon). Supposons queq= 2nest une puissance de2. L"applicationu?→u+u2+u22+ ···+u2n-1deKdans lui-même prend2n-1fois la valeur0et2n-1fois la valeur1.

Démonstration. - Notons?cette application.

Dans le cas oùqest impair, on a?(u)2= 1siu?= 0et?(u) = 0sinon; par suite, ?(u)vaut±1ou0. Comme?est une application polynomiale de degré(q-1)/2,

6ANTOINE CHAMBERT-LOIR

elle prend au plus(q-1)/2fois les valeurs-1et1, donc exactement(q-1)/2fois. (En fait,?(u)est le symbole de Legendre deu, qui vaut1siuest un carré non nul,

0siu= 0et-1dans les autres cas.)

Lorsqueqest une puissance de2, on a

?(u)2=u2+u22+···+u2n=?(u) +u2n-u=?(u). Par conséquent,?(u)(?(u)-1) = 0et?(u)vaut0ou1. En outre,?prend au plus2n-1fois chaque valeur, donc exactement2n-1fois la valeur0et2n-1fois la valeur1.Proposition 1.4.2. -SoitFun corps fini de cardinalq, soitf?F[x]un poly- nôme sans facteur carré dont tous les facteurs irréductibles sont de degrée. (1)Supposons queqsoit impair. Soitgun polynôme non nul de degré< net soithle reste de la division parfdu polynômeg(qe-1)/2. Alors,fest le produit depgcd(f,h),pgcd(f,h-1)etpgcd(f,h+ 1). En outre, parmi lesqn-1polynômes possiblesg, seuls2((qe-1)/2)rfournissent une factorisation triviale. (2)Supposons queq= 2msoit une puissance de2. Soitgun polynôme de degré< net soithle reste de la division parfdu polynômeg+g2+···+g2em-1. Alors,f est le produit depgcd(f,h)et depgcd(f,h-1). En outre, parmi lesqnpolynômes possiblesg, seuls2(2em-1)rfournissent une factorisation triviale. Lorsqueqest impair, la probabilité d"obtenir une factorisation triviale est donc

égale à

2

1-r(qe-1)rq

er-1?21-r. Lorsqueqest une puissance de2, elle est encore21-r. Par conséquent, sir?2, on peut espérer, en tirant des polynômesgau hasard, factoriserftrès rapidement.(1)Il est cependant possible de n"avoir trouvé aucun facteur non trivial au bout de1000 essais, mais la probabilité est de l"ordre de21000(1-r), donc ridiculement faible. Démonstration. - NotonsAl"algèbreF[x]/(f); commefest produit derpoly-

nômes irréductibles de degrée, deux à deux distincts, le théorème chinois entraîne

queAest isomorphe àKr, oùKest un corps àqeéléments. Étant donné un polynômegde degré< n, identifié à un élément deA, donc à une famille(u1,...,ur)d"éléments deK, le calcul de l"énoncé revient à celui de (?(u1),...,?(ur))dansKr, où?est l"application du lemme précédent. Par suite, ?(ui)? {0,1,-1}dans le cas oùqest impair, et?(ui)? {0,1}quandqest une puissance de2. Cela revient à dire queh≡?(ui) (modf)i, donc quehest multiple des polynômesfitels que?(ui) = 0,h-1est multiple des polynômesfitels que ?(ui) = 1, eth+1est multiple des polynômesfitels que?(ui) =-1. Comme lesfi(1) Sir= 1, cette probabilité est égale à1, comme il se doit.

FACTORISATION DES POLYNÔMES7

sont premiers entre eux deux à deux,h,h-1eth+ 1sont en fait multiples des produits correspondants. (Ce dernier polynôme n"intervient pas lorsqueqest une puissance de2.) La première partie de l"énoncé en découle immédiatement. Pour la seconde, il s"agit de dénombrer les familles(u1,...,ur)tels que (?(u1),...,?(ur))soit(0,...,0),(1,...,1)ou(-1,...,-1). On trouve exacte-

ment les valeurs indiquées.Le cas particulier d"un polynôme scindé dansFest très important. C"est en effet à

lui qu"on se ramène dans l"algorithme deBerlekampexposé ci-dessous, c"est aussi ce qui se passe pour un polynôme de petit degré. Proposition 1.4.3. -SoitFun corps fini de cardinalqet soitf?F[x]un polynôme de degrénsans facteur carré qui est scindé dansF. (1)Supposonsqimpair. Poura?F, posonsha= (x+a)(q-1)/2(modf). Alors fest le produit depgcd(ha,f),pgcd(ha-1,f)etpgcd(ha+1,f). En outre, au plus la moitié des valeurs deafournit une factorisation triviale. (2)Supposons queq= 2mest une puissance de2. Poura?F?, posonsha= (ax)+(ax)2+···+(ax)2m-1. Alors,fest le produit depgcd(ha,f)et depgcd(ha-quotesdbs_dbs33.pdfusesText_39

[PDF] polynome degré 2

[PDF] phyllotaxie spiralée

[PDF] définition société civile organisée

[PDF] comment expliquer l'abstention électorale

[PDF] mobilisation des civils première guerre mondiale

[PDF] implication des civils premiere guerre mondiale

[PDF] les civils victimes de la premiere guerre mondiale

[PDF] les conditions de vie des civils pendant la seconde guerre mondiale

[PDF] le fibroscope pour voir ? l'intérieur du corps correction

[PDF] exercice corrigé fibre optique ? saut d'indice

[PDF] composition géographie roissy

[PDF] l inégale intégration des territoires ? la mondialisation

[PDF] les mobilités humaines transnationales

[PDF] les mobilités humaines 4e évaluation

[PDF] un rayon lumineux penetre dans l une des fibres optiques d un fibroscope