[PDF] Factorisation des polynômes

indéterminée) à coefficients dans un corps fini ou dans Z 1 Cas des divisant n, mais les racines des polynômes Φd pour dn et d = n ne fournissent qu'au plus

Déterminer les racines réelles et complexes du polynôme : ( ) = 5 + 4 + 3 + 2 + + 1 En déduire sa factorisation dans ℂ[ ] et

[PDF] Polynômes - Exo7 - Cours de mathématiques

partie 3 Racine d'un polynôme, factorisation · Vidéo · partie 4 Un polynôme à coefficients dans K est une expression de la forme P(X) = an X n +an−1X

[PDF] Factorisation de polynômes de degré 3

On peut donc le factoriser par (x − 1), ainsi, on sait qu'il existe un polynôme Q de degré 2 tel que, pour tout réel x, P(x) = (x −1)×Q(x) Détermination du polynôme Q Q est un polynôme de degré 2, il s'écrit sous la forme Q(x) = ax2 +bx +c

[PDF] 6 Nombres complexes et polynômes - cpgedupuydelomefr

On considère la représentation suivante du cercle trigonométrique C de Théorème 6 1 11 — Racines complexes d'un polynôme complexe du second degré considèrer la factorisation dans C[X] du polynôme P On regroupe tous les

P n'a pas de racines multiples (par calcul de PGCD, c'est la factorisation “square- free”), on peut aussi décider d'appliquer un algorithme de factorisation exact

[PDF] Factorisation des polynômes - webusersimj-prgfr

indéterminée) à coefficients dans un corps fini ou dans Z 1 Cas des divisant n, mais les racines des polynômes Φd pour dn et d = n ne fournissent qu'au plus

[PDF] La factorisation de polynômes

`A l'aide de l'équation x2 +(a+b)x+ab = (x+a)(x+b) on peut facilement factoriser un grand nombre de fonctions quadratiques x2 +bx+c (La facilité vient avec un

[PDF] Polynômes - Normale Sup

7 fév 2014 · Objectifs du chapitre : • savoir factoriser ou effectuer une division euclidienne sur des polynômes à coefficients réels ou complexes • comprendre

[PDF] Polynômes - Math´ematiques - ECS1

78000 Versailles c 2017, Polycopié du cours de mathématiques de première année Exemples simples de factorisation dans C[X] et R[X] de polynômes de K est à support fini • L'élément ai s'appelle coefficient d'indice i du polynôme A =

pdf Racines de l’unité et factorisation de polynômes dans C

RACINES DE L’UNITÉ ET FACTORISATION DE POLYNÔMESDANSC Exemple 9 2 2 Soit P(z)=z3 ? 6z2 +13z ? 10 Il n’est pas di?cile de véri?er que 2 est une racine de PilexistedoncQ(z)=az2 +bz +c un polynôme de degré (au plus) 2 tel que P(z)=(z ?2)(az2 +bz +c) Pour déterminer les nombres complexes ab et c

[PDF] factorisation d'un polynome en ligne

[PDF] factorisation d'un polynome exercice corrigé

[PDF] factorisation exercices corrigés 4ème

[PDF] factorisation identité remarquable exercice

[PDF] factorisation identités remarquables 3ème exercices

[PDF] factoriser développer identités remarquables

[PDF] factoriser développer identités remarquables exercices seconde

[PDF] factors that affect brightness of a glow stick

[PDF] factors that affect glow stick reaction

[PDF] facts about disneyland paris rides

[PDF] facts about paris for kids

[PDF] faculté médecine paris 7

[PDF] faire des ricochets dans l'eau

[PDF] faire des ricochets les enfoirés

[PDF] faire imprimer son rapport de stage

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,

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=

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 à

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-

1,f). En outre, au plus la moitié des valeurs deafournit une factorisation triviale.

Dans les deux cas, la probabilité, tirantaau hasard, d"obtenir une factorisation triviale est donc inférieure ou égale à1/2. Démonstration. - Notonsx1,...,xnles racines defdansF. Étudions d"abord le cas oùqest impair. Dire queafournit une factorisation triviale, signifie quexi-aest identiquement nul, carré ou non carré lorsqueipar- court{1,...,n}. Autrement dit, les " mauvaises » valeurs deasont celles pour lesquellesxi-aest non nul, et toujours carré ou non carré. En particulier, l"élément (x2-a)/(x1-a)deF?{∞}doit toujours être non carré (∞étant considéré comme un carré). Commea?→(x2-a)/(x1-a)est une homographie, c"est une application bĳective deF? {∞}et au plus(q-1)/2qvaleurs deasont mauvaises. Le cas oùqest une puissnace de2est analogue. SoitSl"ensemble des2m-1 solutions (dansF) de l"équation?(u) =u+u2+·+u2m-1; c"est un sous-groupe deFcar?(u+v) =?(u) +?(v). En outre,ha(xi)vaut0siaxiappartient àSet vaut1sinon. En particulier, sia(x2-x1)??S,ax1etax2n"appartiennent pas tous deux àS,ha(x1)?=ha(x2), donc l"une des racines,x1etx2, est racine depgcd(ha,f) tandis que l"autre est racine depgcd(ha-1,f). Ainsi, la factorisation n"est triviale

que dans au plus(2m-1-1)cas, c"est-à-dire moins de la moitié.1.5. Algorithme de Berlekamp (1970). -Revenons au problème de la factori-

sation d"un polynômefde degrén, à coefficients dans un corps finiFde cardinalq, supposé sans racines multiples. Notons encoreAl"algèbreF[x]/(f)etBla sous- algèbre de Berlekamp, noyau de l"endomorphisme d"espaces vectoriela?→aq-a. Par l"algèbre linéaire (algorithme de Gauss, ou de Gauss-Jordan), on peut en trouver uneF-baseb1,...,brreprésentée par des polynômes deF[x]de degrés< n.

8ANTOINE CHAMBERT-LOIR

Sif=?r

i=1fi, le théorème chinois identifieAau produitK1···Krdes corps finis

F[x]/(fi)et identifieBà la sous-algèbreFr.

Soitbun élément deB. Par définition, il existe pour touti? {1,...,r}un unique élément?i(b)?Ftel queb≡?i(b) (modf)i. Alors,fiest un facteur deb-?i(b) si bien que la connaissance des?i(b)permet de factoriserf. De fait, on a la formule f=? u?Fpgcd(f,b-u). Pour que l"on obtienne une factorisation non triviale, il faut et il suffit que les i(b)ne soient pas tous égaux, c"est-à-dire quebn"appartienne pas à la sous-algèbre diagonaleFdeB. Toutefois, la formule donnée est totalement inutilisable dans les applications pratiques où le cardinalqdeFest très grand; en effet elle suppose de calculerqpgcd, ce qui est prendra bien trop de temps. Il se pose donc la question de déterminer efficacement les?i(b). On s"inspire pour cela de l"argument déjà utiliser dans l"algorithme de Cantor-Zassenhaus. Supposons d"abordqimpair. Commebq-best multiple def, on a l"égalité f= pgcd(f,b(q-1)/2-1)pgcd(f,b(q-1)/2+ 1)pgcd(f,b). Il s"agit de voir à quelle probabilité cette factorisation est non triviale. Observons que pour touti,?i(b)(q-1)/2vaut0,1ou-1. Il s"agit de trouverbde sorte que ces valeurs ne soient pas toutes égales. Sibest choisi au hasard dansB? F r, distinct d"un élément deF,?i(b)(q-1)/2vaut(1,...,1)si et seulement si tous les i(b)sont des carrés non nuls,(-1,...,-1)si et seulement aucun des?i(b)n"est un carré. Il y a donc2((q-1)/2)r-(q-1)tels choix. En dehors de ces choix, la factorisation n"est pas triviale, ce qui arrive avec une probabilité au moins égale

à21-r.

Pour résumer, la méthode est la suivante : calculer une base de l"espace vectoriel des polynômesQ?F[x]de degrés< ntels queQq≡Q(modf), espace identifié àBet dont on noterla dimension; choisir un élémentQau hasard dansBpuis calculer le pgcd deQ(q-1)/2-1avecfd"où, avec probablité au moins1-21-r, un facteur non trivial def.

1.6. Remarques. -1) Continuons l"analyse de l"algorithme deBerlekamp.

La multiplication parbdans laF-algèbreAagit comme la multiplication par?i(b) dans le facteurKi. Par suite, cet endomorphismeμbest diagonalisable et son poly- nôme minimalPbest celui dont les?i(b)sont les racines (chacune avec multiplicité1). On le détermine en cherchant une relation de dépendance linéaire entre1,b,...,br dansB. Autrement dit, si l"on sait déterminer les racines d"un polynôme scindé, on connaît les?i(b), donc on peut factoriser le polynôme initial. En faisant en outre l"analyse précise de la complexité du calcul dePb, cela montre que le problème de la factorisation dans un corps fini se ramèneen temps polynomial à celui de la détermination des racines d"un polynôme scindé.

FACTORISATION DES POLYNÔMES9

2) En général, on ne connaît pas d"algorithme non probabiliste pour factoriser

un polynôme de degrénà coefficients dans un corps fini de cardinalq, dont la complexité soit polynomiale ennlogq. Pour les équations de la formex2=a,SchoofpuisPilaont en revanche exhibé un tel algorithme. L"expliquer nous entraînerait largement au delà du niveau de l"agrégation. J"ai l"impression que cela s"étend aux équations de la formexn=a.

2. Coefficients entiers

2.1. Rappels sur les anneaux de polynômes. -Comme l"anneauZest fac-

toriel, l"anneauZ[X]est factoriel (théorème de Gauss). En outre, les polynômes irréductibles deZ[X]sont : - les polynômes constants,±p, oùpest un nombre premier; - les polynômesprimitifs(dont les coefficients sont premiers entre eux dans leur ensemble) qui sont irréductibles en tant que polynômes à coefficients dansQ. Une conséquence importante est que sifetgsont deux polynômesprimitifs deZ[X]tels quefdivisegdansQ[X], alorsfdivisegdansZ[X]. En particulier, soitfun polynôme primitif et soitgl"unique polynôme primi- tif (au signe près) de la formecpgcd(f,f?), avecc?Z\ {0}. Commegdivisef dansQ[X], il divisegdansZ[X]et le polynômef/g?Z[X]à les mêmes facteurs ir- réductibles quef, tous avec exposant1. Cela permet de se ramener à la factorisation de polynômes sans facteur carré.

2.2. Bornes. -Soitf=anxn+···+a0?C[X]un polynôme de degrén, de

racines complexesz1,...,zn. On définit un certain nombre de quantités, qui mesurent la taille def: ?f?2=? n? j=0|aj|2? 1/2 ?f?1=n? j=0|aj| ?f?∞= max(|a0|,...,|an|)

M(f) =|an|n?

j=1max(1,|zj|). Lemme 2.2.1. -Ces quantités sont reliées par les inégalités suivantes : ?f?∞??f?2??f?1?(n+ 1)?f?∞et2-n?f?1?M(f)??f2?.

10ANTOINE CHAMBERT-LOIR

Démonstration. - Les trois premières inégalités sont évidentes. Pour0?k?n-1, on a (relations coefficients-racines) a k= (-1)n-kan? i

1<··· i1···zik, d"où |ak|?|an|? i
1<··· et ?f?1=n? k=0|ak|?|an|n? j=1(1 +|zj|)?|an|n? j=12max(1,|zj|)?2nM(f).
Appliquons d"autre part la formule deJensen:

12π?
2π 0 log??eiθ-a??dθ= max(|a|,1), on a (1)logM(f) =12π? 2π 0 log??f(eiθ)??dθ. Compte tenu de l"inégalité du même (concavité du logarithme), on a donc logM(f)?12 log?12π? 2π 0? ?f(eiθ)??2dθ? =12 log? n? j=0|aj|2? (inégalité deParseval), d"où finalement
M(f)??f?2

(inégalité deLandau).Si les normes?f?∞,?f?2et?f?1sont d"une utilisation plus aisée, l"intérêt de
l"expressionM(f)vient de sa multiplicativité, claire sur la formule (1) :M(fg) = M(f)M(g). Compte tenu de l"inégalité deLandau, il vient ?f?∞?g?∞??f?1?g?1 ?2mM(f)2nM(g)?2m+nM(fg) ?2m+n?fg?2 ?2m+n⎷m+n+ 1?fg?∞. Corollaire 2.2.2(" Bornes de Mignotte »). -Soitf,gdes polynômes à co- efficients entiers de degrésmetntels quegdivisefdansZ[X]. On a les inégalités ?g?∞?2n?f?2?2n⎷n+ 1?f?∞. Démonstration. - Soith?Z[x]tel quef=gh. On a?g?∞?h?∞?2n?f?2. Commegethsont à coefficients entiers,?g?∞et?h?∞sont au moins égale à1et sont donc majorées par2n?f?2, laquelle est inférieure ou égale à2n⎷n+ 1?f?∞.
FACTORISATION DES POLYNÔMES11
Proposition 2.2.3. -Sif?C[x]est un polynôme de degrén, on adisc(f)? n nM(f)n-1. Démonstration. - Par définition, le discriminant defest égal à disc(f) =a2(n-1)n? i1 +|zj|2+···+|zj|2(n-1)?
?|an|2(n-1)n? j=1?quotesdbs_dbs17.pdfusesText_23

[PDF] [PDF] Factorisation des polynômes - webusersimj-prgfr