[PDF] Chapitre III - Corps finis Les premiers exemples de corps

View - Download Chapitre III - Corps finis

Previous PDF

Next PDF

Universite Pierre et Marie Curie

Cours de cryptographie MM029 - 2009/10

Alain Kraus

Chapitre III - Corps nis

Nous admettrons que tout corps ni est commutatif. Ce resultat a ete etabli en 1905 par Wedderburn. Les premiers exemples de corps nis sont les quotients de l'anneauZ F p=Z=pZ; oupest un nombre premier. D'autres exemples sont fournis par les quotients F p[X]=(F); ouFest un polyn^ome irreductible deFp[X]. Un tel corps est de cardinalpd, oudest le degre deF. Nous reviendrons sur ce point, et demontrerons que l'on obtient de la sorte tous les corps nis. On etablira que pour tout nombre premierpet tout entiern1, il existe un corps apnelements et qu'il est unique a isomorphisme pres. On abordera par ailleurs le probleme du logarithme discret, qui est tres important en cryptographie.

Table des matieres

1. Rappels sur l'anneauK[X] et ses quotients 1

2. Caracteristique d'un anneau 5

3. Groupe multiplicatif d'un corps ni 6

4. Corps nis comme quotients deFp[X] 7

5. Polyn^omes irreductibles sur un corps ni 8

6. Theoreme d'existence et denombrement 12

7. Theoreme d'unicite 18

8. Probleme du logarithme discret 18

9. Algorithme de Silver, Pohlig et Hellman 20

10. Algorithme Baby step - Giant step 23

1. Rappels sur l'anneauK[X]et ses quotients

SoientKun corps commutatif etK[X] l'anneau des polyn^omes a coecients dansK. Pour toutF2K[X], notons deg(F) son degre. Rappelons que le degre du polyn^ome nul est hhmoins l'inniii, qui est par denition un element plus petit que tout entier naturel, 1 satisfaisant aux regles usuelles d'addition. Le groupe des elements inversible deK[X] est K (l'ensemble des polyn^omes de degre 0). L'anneauK[X] est euclidien, avec l'application degre comme stathme euclidien. Autrement dit,K[X] est un anneau integre et pour tous AetBdansK[X] avecB6= 0, il existe un unique couple de polyn^omes (Q;R), tels que

A=BQ+Ravec deg(R) On dit queQest le quotient et queRest le reste de la division euclidienne deAparB. Un polyn^ome est dit unitaire si son coecient de plus haut degre vaut 1. On deduit du lemme 0.9 queK[X] est un anneau principal. En particulier : Proposition 3.1.SoitIun ideal non nul deK[X]. Il existe un unique polyn^ome unitaire

PdeK[X]tel que l'on aitI= (P).

Le pgcd de deux polyn^omesAetB, non tous les deux nuls, est l'unique polyn^ome unitaireD2K[X] tel que (D) = (A) + (B): Il existe doncUetVdansK[X] tels queD=AU+BV(relation de Bezout). La determination deDet de relations de Bezout entreAetBs'eectue, comme dansZ, avec l'algorithme d'Euclide etendu, qui vaut dans ce cadre sans modications. On dit que AetBsont premiers entre eux si leur pgcd est 1. Tel est le cas si et seulement si il existe UetVdansK[X] tels queAU+BV= 1. Il en resulte que siF;G;Hsont des polyn^omes non nuls deK[X] tels queFdiviseGHet queFsoit premier avecG, alorsFdiviseH (theoreme de Gauss). Denition 3.1.Un polyn^ome deK[X]est dit irreductible (dansK[X], ou surK), si son degre est superieur ou egal a1et si l'ensemble de ses diviseurs est forme des elements non nuls deKet des polyn^omes qui lui sont associes(1). Un polyn^omeP2K[X] de degre1 est irreductible s'il ne possede pas de diviseur Q2K[X] tel que 1deg(Q)deg(P)1. Deux polyn^omes irreductibles deK[X] sont premiers entre eux ou associes. Un polyn^ome qui n'est pas irreductible est dit reductible. SoitPl'ensemble des polyn^omes irreductibles unitaires deK[X]. Comme dans le cas de l'anneauZ, on dispose du theoreme fondamental de l'arithmetique deK[X]. Theoreme 3.1.SoitPun polyn^ome non nul deK[X]. AlorsPs'ecrit de maniere unique sous la forme (1)P=Y F2PF nF;(1) Rappelons que deux polyn^omesFetGdeK[X] sont dits associes s'il existe2K tel queF=G. La denition 3.1 est un cas particulier de la notion generale d'element irreductible dans un anneau commutatif. 2 ou2K, et ou lesnFsont des entiers naturels nuls sauf un nombre ni d'entre eux. Demonstration : Prouvons l'assertion d'existence. L'enonce est vrai si le degre deP est nul, auquel cas on prend=Pet tous lesnFnuls. Considerons un entiern1. Supposons que l'on ait une decomposition de la forme (1) pour les polyn^omes non nuls de degren1 et que deg(P) =n. SoitEl'ensemble des diviseurs dePde degre1. Il n'est pas vide carPest dansE. Il existe donc un elementQ2Ede degre minimum. Ce polyn^ome est irreductible. Il existeR2K[X] tel queP=QRet deg(R)n1. D'apres l'hypothese de recurrence,Rpossede une decomposition de la forme (1). Il en est donc de m^eme deP, d'ou l'assertion d'existence. On admettra ici l'unicite. Rappelons que siPest un polyn^ome etaun element deK, on dit queaest racine de Psi l'on aP(a) = 0, autrement dit, si la fonction polyn^ome associee aPs'annule ena. Tel est le cas si et seulement siXadiviseP. De plus, siPest de degren, alorsPpossede au plusnracines dansK. En eet, on verie en utilisant le theoreme de Gauss, que siP possedait au moinsn+ 1 racines, il serait divisible par un polyn^ome de degren+ 1. Passons maintenant aux quotients deK[X]. Considerons un idealIdeK[X]. Pour toutP2K[X], posonsP=P+Ila classe dePmoduloI. C'est le sous-ensemble de K[X] forme des polyn^omesQtels quePQappartienne aI. On sait deja queK[X]=I est muni de la structure d'anneau denie par les egalitesP+Q=P+QetPQ=PQ: On munit de plusK[X]=Id'une structure deK-espace vectoriel, via la loi externe

KK[X]=I!K[X]=I

qui au couple (;P)2KK[X]=IassocieP. Par denition, on a donc l'egalite P=P: On verie que cette denition a bien un sens, autrement dit, qu'elle ne depend que de la classe dePet pas d'un de ses representants. Pour tous2KetP2K[X], on a (+I)(P+I) =P+I=(P+I): De plus, siIest distinct deK[X], le corpsKest isomorphe a un sous-anneau deK[X]=I, via l'application qui a2Kassocie+I. Proposition 3.2.SoitPun polyn^ome non nul deK[X]degren. Posons=X+ (P) dansK[X]=(P).

1) LeK-espace vectorielK[X]=(P)est de dimension nien, dont une base est le systeme1;;;n1.

3

2) PosonsP=a0+a1X++anXn(ai2K). On a l'egalite

(2) nX i=0a ii= 0:

Demonstration : Verions que

1;;;n1est un systeme libre. Soientides

elements deKtels que n1X i=0 ii= 0:

Cette egalite signie que l'on a

n1X i=0 iXi2(P): PuisquePest de degren, cela entra^ne que tous lesisont nuls. Demontrons que le systeme considere est generateur. Soitun element deK[X]=(P). Il existeF2K[X] tel que=F+(P). On aP6= 0. Il existe doncQetRdansK[X] tels que l'on aitF=PQ+R avec deg(R)< n, d'ou=Ret notre assertion.

Par ailleurs, on aP= 0, autrement dit, on a

n X i=0a iXi=nX i=0a iX i= 0; d'ou l'egalite (2). Le resultat qui suit concerne la structure d'anneau deK[X]=(P), qui n'est autre que l'analogue du lemme 1.8 sur la description des elements inversibles des quotients deZ. Proposition 3.3.SoitPun polyn^ome deK[X]. Le groupe des elements inversibles de l'anneauK[X]=(P)est forme des classes de polyn^omes qui sont premiers avecP. Demonstration : SoitFun polyn^ome deK[X] premier avecP. Il existeUetVdans K[X] tels queUP+V F= 1. On aVF= 1, doncFest inversible. Inversement, soitFun element inversible deK[X]=(P). Il existeQ2K[X] tel queFQ= 1. Cette egalite signie queFQ1 appartient a (P), autrement dit qu'il existeU2K[X] tel queFQ+UP= 1, doncFetPsont premiers entre eux. Corollaire 3.1.SoitPun polyn^ome non nul deK[X]. Les conditions suivantes sont equivalentes :

1) l'anneauK[X]=(P)est integre.

2) Le polyn^omePest irreductible dansK[X].

4

3) L'anneauK[X]=(P)est un corps.

Demonstration : Supposons queK[X]=(P) soit integre. Tout d'abord,Pn'est pas inversible, sinon on a (P) =K[X] etK[X]=(P) est l'anneau nul, ce qui est exclu par denition. On a donc deg(P)1. SoitFun diviseur deP. Il s'agit de montrer queF

est inversible ou bien queFetPsont associes. Il existeQ2K[X] tel queP=FQ, d'ouFQ= 0. Par hypothese, cela entra^ne queF= 0 ouQ= 0. SiF= 0, alorsFest dans (P)

i.e.PdiviseF. Par suite,PetFsont associes. SiQ= 0, alorsQetPsont associes, d'ou deg(F) = 0 i.e.Fest inversible. Cela prouve quePest irreductible dansK[X]. Supposons alorsPirreductible dansK[X] et prouvons que tout element non nulFdeK[X]=(P) est inversible. PuisquePest irreductible et quePne divise pasF, les polyn^omesFetPsont premiers entre eux. D'apres la proposition 3.3,Fest donc inversible, doncK[X]=(P) est un corps. La derniere implication est immediate.

2. Caracteristique d'un anneau

SoitAun anneau. Notons 1Al'element neutre multiplicatif deA. Soitf:Z!A l'application deZdansAdenie par (3)f(m) =m1Apour toutm2Z: C'est un morphisme d'anneaux (et d'ailleurs le seul). Son noyau est un ideal deZ. Il existe donc un unique entier naturelntel que l'on ait

Ker(f) =nZ:

Denition 3.2.L'entiernest la caracteristique deA.

Lemme 3.1.SiAest integre, sa caracteristique est nulle ou est un nombre premier. Tel est en particulier le cas siAest un corps commutatif. Demonstration : L'anneauZ=nZest isomorphe a un sous-anneau deA, a savoir l'image def. PuisqueAest integre, il en est de m^eme deZ=nZ. Sinn'est pas nul,Z=nZest un corps, etnest premier. Theoreme 3.2.SoitKun corps commutatif d'element neutre multiplicatif1K. Soitm un entier relatif.

1) SupposonsKde caracteristique zero. On am1K= 0si et seulement sim= 0. Dans ce

cas,Kcontient un unique sous-corps isomorphe aQ.

2) SupposonsKde caracteristique un nombre premierp. On am1K= 0si et seulement

sipdivisem. Dans ce cas,Kcontient un unique sous-corps isomorphe aFp. Demonstration : SupposonsKde caracteristique 0. Le morphismef:Z!Kdeni par (3) est alors injectif, d'ou la premiere equivalence. L'application deQdansKqui a 5 a=b2Qassociea1K(b1K)1, prolongefdeZaQ, et est un morphisme de corps (notons quebetant non nul, on ab1K6= 0, et l'on verie que cette application est bien denie). Son image est donc un sous-corps deKisomorphe aQ. Par ailleurs, soientQ1etQ2deux sous-corps deKisomorphes aQ. L'intersectionQ1\Q2est un sous-corps deQ1et deQ2. PuisqueQne contient pas de sous-corps autres que lui-m^eme, tel est aussi le cas deQ1 etQ2, d'ouQ1\Q2=Q1=Q2, et l'unicite annoncee. SiKest de caracteristiquep, le noyau defest l'idealpZ. Par suite, on am1K= 0 i.e.mappartient au noyau defsi et seulement sipdivisem. L'image defest un sous-corps deKisomorphe aFp. L'unicite d'un tel sous-corps resulte du fait queFpn'a pas d'autres sous-corps que lui-m^eme. Les corpsQ,R,Csont de caracteristique 0. Pour toutppremier,Fpest de ca- racteristiquep. Corollaire 3.2.SoitKun corps ni. La caracteristique deKest un nombre premierp etKcontient un unique sous-corps isomorphe aFp. De plus, il existe un entiern1tel que le cardinal deKsoitpn. Demonstration : PuisqueKest ni,Kne contient pas de sous-corps isomorphe aQ. La caracteristique deKest donc un nombre premierpetKcontient un unique sous-corps isomorphe aFp. Par suite,Kest naturellement muni d'une structure d'espace vectoriel surFp. Le corpsKetant ni, la dimension deKsurFpest nie. Sinest cette dimension, Kest isomorphe (comme espace vectoriel) aFnp, etKest de cardinalpn. Corollaire 3.3.SoitKun corps ni de cardinalp. AlorsKest isomorphe aFp. Demonstration : C'est immediat vu queKcontient un sous-corps isomorphe aFp. Corollaire 3.4.SoientKun corps ni etFun polyn^ome irreductible de degrendans K[X]. L'anneauK[X]=(F)est un corps ni, de m^eme caracteristique queK, et son cardinal estjKjn. Demonstration : L'anneauK[X]=(F) est un corps (cor. 3.1). Il contient un sous-corps isomorphe aK, donc sa caracteristique est la m^eme que celle deK. LeK-espace vectoriel K[X]=(F) etant de dimensionn(prop. 3.2), il est isomorphe aKn, d'ou l'assertion.

3. Groupe multiplicatif d'un corps ni

Theoreme 3.3.SoientKun corps commutatif etHun sous-groupe ni deK. Alors,

Hest un groupe cyclique.

Demonstration : C'est une consequence directe du lemme 1.12, car pour tout entier d1, le polyn^omeXd12K[X] possede au plusdracines dansK. Parce que tout corps ni est commutatif, on obtient : 6 Corollaire 3.5.SiKest un corps ni, le groupe multiplicatifKest cyclique. Compte tenu du theoreme 1.10, on obtient l'enonce suivant : Corollaire 3.6.SoitKun corps ni de cardinalq. Le groupeKpossede exactement '(q1)generateurs, ou'est la fonction indicatrice d'Euler. De plus, siest un generateur deK, alors l'ensemble des generateurs deKest n k1kq1etpgcd(k;q1) = 1o Exemple 3.1.Considerons le polyn^omeF=X3+X+ 12F5[X]. Posons

K=F5[X]=(F):

Le polyn^omeFest irreductible surF5, car il est de degre 3 et n'a pas de racines dansF5, doncKest un corps. Sa caracteristique est 5 et son cardinal est 53= 125. Le groupeK est cyclique d'ordre 124. Les ordres possibles de ses elements sont 1;2;4;31;62 et 124. Il possede soixante generateurs. Soitla classe deXmodulo (F). Le systeme (1;;2) est une base deKsurF5.

Verions que 2est un generateur deK. On a

3=1et5= 1 +2:

PuisqueKest de caracteristique 5, il en resulte que l'on a

15=(1 +)5=15=22;

d'ou les egalites

30=2+ 1 et31=1:

Ainsi,est d'ordre 62. Par ailleurs, on a 241 mod. 5 et 2313 mod. 5, d'ou (2)31= 2 et (2)62=1, ce qui entra^ne notre assertion.

4. Corps nis comme quotients deFp[X]

Theoreme 3.4.SoitKun corps ni de cardinalpn. Il existe un polyn^omeF2Fp[X]de degrenirreductible surFp, tel que les corpsKetFp[X]=(F)soient isomorphes. Demonstration : Soitun generateur deK. Considerons l'application :Fp[X]!K denie pour toutP=PaiXi2Fp[X] par l'egalite (P) =Xa ii; 7 ou l'on identie iciai2Fpavec n'importe quel entier relatif dont la classe modulopest a i. Cela est licite carKest de caracteristiquep. C'est un morphisme d'anneaux. Il est surjectif carest un generateur deK. Le noyau de est un ideal non nulIdeFp[X] et F p[X]=Iest un anneau isomorphe aK. Il existeF2Fp[X] non nul tel queI= (F) (prop.

3.1). PuisqueFp[X]=(F) est un corps,Fest irreductible surFp. Simest le degre deF, le

cardinal deFp[X]=(F) estpm. C'est le cardinal deK, d'oum=net le resultat. Les corps nis de cardinalpns'obtiennent donc exclusivement a partir des polyn^omes irreductibles de degrendansFp[X]. Autrement dit : Proposition 3.4.Soientpun nombre premier etnun entier1. Les deux assertions suivantes sont equivalentes :

1) il existe un corps apnelements.

2) Il existe un polyn^ome irreductible de degrendansFp[X].

Il s'agit maintenant de demontrer l'existence de polyn^omes irreductibles de tout degre n1 dansFp[X], et ensuite de prouver que siUetVsont des polyn^omes irreductibles de degrendansFp[X], alors les corpsFp[X]=(U) etFp[X]=(V) sont isomorphes (unicite a isomorphisme pres des corps apnelements).

5. Polyn^omes irreductibles sur un corps ni

On va etablir le resultat suivant :

Theoreme 3.5.SoientKun corps ni de cardinalqetnun entier naturel non nul. L'ensemble des diviseurs irreductibles du polyn^omeXqnX2K[X]est forme des polyn^omes irreductibles deK[X]de degre divisantn. Plus precisement, on a l'egalite (4)XqnX=YF; ouFparcourt l'ensemble des polyn^omes irreductibles unitaires deK[X]de degre di- visantn. La demonstration repose sur plusieurs lemmes intermediaires, qui sont par eux m^emes interessants d'un point de vue pratique. On suppose dans ce qui suit queKest un corps ni de caracteristiquepet de cardinalq(qui est donc une puissance dep). Lemme 3.2.Soitkun entier naturel. Pour tousxetydansKon a (x+y)pk=xpk+ypk: Demonstration : L'enonce est vrai sik= 0. Soitkun entier0 tel que l'egalite annoncee soit veriee. Pour tousx;y2K, on a (x+y)pk+1=(x+y)pkp=xpk+ypkp: 8 Pour tout entierj= 1;;p1, le coecient bin^omialCjpest divisible parp. La formule du bin^ome de Newton entra^ne alors l'egalite (x+y)pk+1=xpk+1+ypk+1.

Lemme 3.3.SoitLun corps ni contenantK.

1) Pour toutx2L,xappartient aKsi et seulement si on axq=x.

2) Pour toutF2L[X],Fappartient aK[X]si et seulement si on aF(Xq) =F(X)q.

Demonstration : 1) Soitxun element deL. Sixest dansK, vu queKest un groupe d'ordreq1, on axq1= 1, d'ouxq=x. Par ailleurs, le polyn^omeXqX2L[X] possede au plusqracines, doncKest l'ensemble de ses racines, d'ou l'assertion 1.

2) SoitF=PakXkun polyn^ome deL[X]. On a

F(X)q=Xa

kXkq=Xaq kXkq: Cette derniere egalite se demontre comme le lemme 3.2 en procedant par recurrence sur le nombre de mon^omes deF. D'apres la premiere assertion,Fappartient aK[X] si et seulement siaq k=akpour toutk, d'ou le resultat. Lemme 3.4.SoientFun polyn^ome unitaire irreductible deK[X]etLun corps ni contenantKdans lequelFa une racine. Il existe un plus petit entierr1tel que l'on aitqr=. On ar= deg(F)et l'egalite F=r1Y i=0 Xqi Demonstration : Il existe un entierm1 tel que le cardinal deLsoitqm. On a qm=, donc il existe un plus petit entierr1 tel que l'on aitqr=. Par ailleurs, etant racine deF, on deduit du lemme 3.3 que les elementsqipouri= 1;;r1 sont aussi des racines deF. Posons G=r1Y i=0 Xqi Puisque lesqipouri= 0;;r1 sont distincts deux a deux(2), il en resulte queG diviseFdansL[X]. De plus, on a les egalites(2) On peut justier cette assertion comme suit. Supposons qu'il existe deux entiersi etjcompris entre 0 etr1 tels quei < jetqi=qj. On a alors l'egalite qji qi = 1: Il s'agit d'en deduire queqji=, ce qui conduira a une contradiction vu le caractere 9

G(X)q=r1Y

i=0

Xqiq=r1Y

i=0

Xqqi+1

=G(Xq): Par suite,Gappartient aK[X] (lemme 3.3). Le quotient et le reste de la division euclidienne deFparGetant independants du corps de base, vu leur caractere d'unicite, on en deduit queGdiviseFdansK[X]. Le polyn^omeFetant irreductible,Getant de degre au moins

1, etFetGetant unitaires, on a doncF=G, d'ou le resultat.

Remarque 3.1.Le lemme 3.4 montre qu'un polyn^ome irreductibleFdeK[X] qui a une racine dans un surcorps niLdeK, a toutes ses racines dansL. De plus, sirest le degre deF, et si2Lest une racine deF, alors les racines deFsont lesqipour i= 0;;r1.

Fin de la demonstration du theoreme 3.5.

SoitF2K[X] un polyn^ome irreductible unitaire de degrer. Il s'agit de demontrer l'equivalence suivante : (5)FdiviseXqnX()rdivisen: Considerons un corps niLcontenantKdans lequelFa une racine: un tel corpsL existe (3). D'apres le lemme 3.4,rest le plus petit entier1 tel queqr=et on a (6)F=r1Y i=0 Xqi

Par ailleurs, on a

(7)qir=pour touti2N: En eet, cette egalite est vraie sii= 0, et si elle est veriee pour un entieri0, on a

q(i+1)r=qirqr=qr=:minimal der. Tout revient ainsi a demontrer que pour touty2L, l'egaliteyq= 1 entra^ne

y= 1. Les entiersqetqm1 etant premiers entre eux, il existeuetvdansZtels que l'on aituq+v(qm1) = 1. Pour touty2L, on ayqm1= 1. Par suite, siyq= 1, on obtient y=yuq+v(qm1)= 1, et notre assertion. (3)L'anneauK[X]=(F) est un corps ni qui contient un sous-corps isomorphe aK. En identiantKet ce sous-corps, on peut alors prendreL=K[X]=(F). Siest la classe

deXmodulo (F), on aF() = 0 (prop. 3.2). Cette identication n'a pas d'importancepour obtenir le theoreme 3.5. Cela etant, si l'on souhaite un corpsLcontenantKau sens

strict du terme, on peut prendre pourLla reunion deKet du complementaire de l'image

deKdansK[X]=(F). Cet ensemble est canoniquement en bijection avecK[X]=(F). Partransport de structure on munit alorsLd'une structure de corps, contenantKcomme

sous-corps, etFa une racine dansL. 10 Supposons alors queFdiviseXqnX. PuisqueF() = 0, on aqn=. Il existe deux entiers naturelstetstels que l'on aitn=rt+savec 0s < r. On a donc qn=qtrqs: D'apres (7), on aqtr=. Par suite, on a=qs;ce qui d'apres le caractere minimal de r, entra^nes= 0, ainsirdivisen. Inversement, supposons querdivisen. On deduit de (7) que l'on aqn=, autrement dit, queest racine du polyn^omeXqnX. Les elements q;;qr1; sont donc des racines deux a deux distinctes deXqnX. Il resulte de (6) queFdivise Xquotesdbs_dbs30.pdfusesText_36

[PDF] commentaire composé les espaces du sommeil

[PDF] rrose sélavy

[PDF] l aumonyme desnos analyse

[PDF] henri michaux

[PDF] langage cuit desnos

[PDF] non l'amour n'est pas mort analyse

[PDF] melange et corps pur 4eme pdf

[PDF] melange et corps pur 4eme

[PDF] corps santé bien etre

[PDF] carnet entrainement demi fond

[PDF] rapport au corps psychologie

[PDF] qu'est ce que le rapport au corps

[PDF] représentation sociale du corps définition

[PDF] corps et société david le breton

[PDF] le culte du corps dans notre société