[PDF] Introduction `a la Cryptologie - Chapitre 11 : Classification et

View - Download Introduction `a la Cryptologie - Chapitre 11 : Classification et

Previous PDF

Next PDF

Introduction

`a la Cryptologie Chapitre 11 : Classification et construction des corps finis Michael Eisermann (Institut Fourier, UJF Grenoble) Ann

´ee 2008-2009

IF/IMAG, Master 1, S1-S2

document mis `a jour le 7 juillet 2009FOURIERINSTITUTfi 1/32

Objectifs de ce chapitre

Les corps finis sont une des plus belles structures alg

´ebriques.Ils sont

`a la base de nombreuses applications algorithmiques, notamment en cryptographie et en codage de l"information.Nous connaissons d ´ej`a le corpsFp=Z=pZo`upest un nombre premier.Ce chapitre

´etablit d"abord laclassificationde tous les corps finis :1Tout corps fini est de cardinalpno`upest premier etn1.2Pour tout tel couple(p;n)il existe un corps de cardinalpn.3Deux corps finis de mˆeme cardinal sont isomorphes.Ce superbe r

´esultat, dˆu`a Galois, est un bijou de l"alg`ebre du 19e si`ecle.Pour le rendre effectif sur ordinateur, il faut n

´eanmoinsˆetre plus explicite.Le d

´eveloppement choisi ici explicitera commentconstruireconcr`etement un corps de cardinalpndonn´e puis commentl"impl´ementersur ordinateur. Litt

´erature pour aller plus loin :Lidl & Niederreiter,Finite Fields, Cambridge 1997.Gathen & Gerhard,Modern Computer Algebra, Cambridge 1999.2/32

Sommaire

1Structure d"un corps finiSous-corps premier et cardinal d"un corps fini

Automorphismes d"un corps finis

Sous-corps d"un corps fini

2Unicit´e du corps de cardinalpnCaract

´erisation des polynˆomes irr´eductibles surFpCorps finis et polyn

ˆomes irr´eductibles surFpUnicit

´e du corps de cardinalpn3Construction des corps finisD ´ecomposition deXpnXdansFp[X]Comptage des polyn ˆomes irr´eductiblesConstruction du corps fini de cardinalpn4Exercices3/32

Outils indispensables

Ce chapitre est le couronnement de notre bref d

´eveloppement alg´ebrique.Il utilise d"une mani `ere essentielle toutes les techniques (math´ematiques et algorithmiques) mises en place par les chapitres pr

´ec´edents :Groupes (ab

´eliens) finis, morphismes, quotientsSous-groupes, th ´eor`eme de Lagrange, ordre d"un´el´ementAnneaux, morphismes, id ´eaux, quotients, th´eor`eme d"isomorphismeCaract ´eristique d"un anneau, le morphisme de FrobeniusL"arithm ´etique des polynˆomes, notamment la division euclidienneDivisibilit ´e des polynˆomes, calcul du pgcd, factorialit´e deK[X]Nombre et multiplicit

´e des racines, crit`ere de multiplicit´eSous-groupes multiplicatifs finis deKEn outre, on aura besoin d"un concept basique omnipr

´esent :La th

´eorie des espaces vectoriels sur un corpsKquelconque (iciFp)4/32

Le groupeFest cycliqueTh

´eor`eme (rappel)SoitAun anneau int`egre et soitGAun sous-groupe fini du groupeA.AlorsGest cyclique, c"est-`a-dire qu"il existeg2Gtel queG=hgi.Corollaire (rappel)

Pour tout corps finiFle groupe multiplicatifFest cyclique.Tout g ´en´erateur du groupeFest appel´eracine primitivedeF.Exemple (rappel) CommeZ=7est un corps, le groupeZ=7est cyclique d"ordre6.(Le th

´eor`eme

ne garantit que l"existence d"un g ´en´erateur, sans en expliciter aucun.)Par t ˆatonnement on trouveord(2) = 3puisord(3) = 6, doncZ=7=h3i.Remarque (rappel)

Pour tout corpsFqde cardinalq, le groupeFqest cyclique d"ordren=q1.Toute racine primitivedeFqd´efinit alors un isomorphisme de groupes

exp

: (Z=n;+)!(Fq;),k7!k, et son inverselog: (Fq;)!(Z=n;+).C"est une situation typique de la cryptographie (Diffie-Hellman, Elgamal).

x1.15/32

Sous-corps premier et cardinal d"un corps fini

Proposition

SoitFun corps fini.Le morphisme canonique':Z!F,k7!k1Fa pour image un sous-anneauK:= im'.Celui-ci est int

`egre carFKest int`egre.Le noyauker'est un id´eal deZ, donc de la forme(p)pour unp2N.CommeFest fini,'ne peutˆetre injectif, doncp >0.Par passage au

quotient on obtient un isomorphisme':Z=p!K.MaisZ=pest int`egre

si et seulement sipest premier.AinsiK=Z=pest mˆeme un corps.On appelleKlesous-corps premier, etplacaract´eristiquedu corpsF.

Via'on identifieFp=Z=p`aK, et on´ecrit simplementFpF.Proposition (rappel) SoitKun sous-corps d"un anneauF.Alors l"addition+:FF!Fet la multiplication:KF!Ffont deFunK-espace vectoriel.Corollaire

SiFest un corps fini, alors son cardinal estpdo`upest premier etd1.Icip= car(F)est le cardinal du sous-corps premierK, etd= dimK(F).Toute base(u1;:::;ud)deFd´efinit un isomorphismeKd!Fd"espaces

vectoriels surKpar(k1;:::;kd)7!k1u1++kdud, d"o`ujFj=jKdj=pd.x1.16/32

Premier exemple : un corps de cardinal4

Le polyn

ˆomeX2+X+ 1de degr´e2est irr´eductible surF2, car sans racine.(Nous avons vu que c"est le seul polyn

ˆome irr´eductible de degr´e2surF2.)Le quotientF4:=F2[X]=(X2+X+ 1)est donc un corps de cardinal4.CommeF2-base on peut choisir(1;x)o`ux=Xest l"image deXdansF4.Les tables d"addition et de multiplication sont (en abr

´egeant1 +xpary) :+01xy

001xy 110yx
xxy01 yyx1001xy 00000 101xy
x0xy1 y0y1x On voit quex2=x+ 1, et ainsi la multiplication peutˆetre reformul´ee comme (+x)(0+0x) = (0+0) + (0+0+0)x:Ceci permet d"impl ´ementerF4commeF22avec les op´erations ci-dessus.Par contre, il n"est pas ´evident de partir d"une telle formule"tomb´ee du ciel» pour ´etablir qu"il s"agit d"un corps. On pr´ef´erera la constructionFp[X]=(P).Exercice

De mani

`ere analogue, expliciter des corps de cardinal8,9,25,27.x1.17/32

Le polyn

ˆome minimal d"un´el´ement alg´ebriqueExercice

SoitKun corps etI(K[X]un id´eal. SiP2Iest irr´eductible, alorsI= (P).Solution.Nous savons queI= (Q)pour unQ2K[X].

AinsiP2(Q)veut dire queQjP, d"o`uQ1ouQP.

Le premier casI= (1)´etant exclu, nous concluons queI= (P).,Exercice

SoitKun corps et soitaun´el´ement d"un anneauAcontenantK.1On adimK(K[a])<1si et seulement s"il existeP2K[X]tel que

P(a) = 0. Dans ce cas on dit que l"´el´ementaestalg´ebriquesurK. On peut alors choisirPde degr´e minimal et unitaire, appel´epolynˆome

minimaldea. SiAest int`egre, le polynˆome minimal est irr´eductible.2Siaest annul´e par un polynˆome irr´eductibleP2K[X],P(a) = 0,

alors le morphisme d"anneaux:K[X]!Ad´efini par(X) =a

induit un isomorphisme de corps:K[X]=(P)!K[a].Solution.Les´el´ements1;a;a2;:::;andansAsont lin´eairement li´es surK,

c"est- `a-direc01 +c1a+c2a2++cnan= 0, si et seulement si le polynˆome P(X) =c0+c1X+c2X2++cnXns"annule ena. Les cons´equences enonc´ees d´ecoulent de l"arithm´etique des polynˆomes surK(`a d´etailler).,x1.18/32

Illustration : corps de cardinal125

Comme un exemple un peu plus complexe et plus int

´eressant, on se propose

d"analyser puis de comparer deux quotients deF5[X]de cardinal125:

P=X3+X+ 1; E=F5[X]=(P);

Q=Y3+ 2Y2Y+ 2; F=F5[Y]=(Q):Exercice

1Quel est le cardinal deEet deF? Ces anneaux sont-ils des corps?2Notonsxl"image deXdansE. Expliciter les lois d"addition et de

multiplication par rapport `a laF5-base(1;x;x2):Comment additionnera=a0+a1x+a2x2etb=b0+b1x+b2x2 pour obtenir un r ´esultat de la formec=c0+c1x+c2x2?Comment multipliera=a0+a1x+a2x2etb=b0+b1x+b2x2 pour obtenir un r

´esultat de la formec=c0+c1x+c2x2?3Poury=x2xcalculerQ(y)dansE.4En d´eduire le noyau du morphisme:F5[Y]!E,Y7!y.5Construire un isomorphismeF5[Y]=(Q)!F5[X]=(P).x1.19/32

L"automorphisme de Frobenius d"un corps fini

Proposition

SoitFun corps fini de caract´eristiquep. Alors l"applicationf:F!F d ´efinie parx7!xpest un automorphisme du corpsF.On appellefl"automorphisme de FrobeniusdeF.D ´emonstration.Tout d"abord, l"applicationf:x7!xpest multiplicative : elle satisfaitf(1) = 1etf(xy) = (xy)p=xpyp=f(x)f(y). Puisfest aussi additive, d"apr`es le d´eveloppement binomial : f(x+y) = (x+y)p=pX k=0 p k! x kypk

DansZnous avons vu quepdivisep

ksi0< k < p. CommeFest de caract ´eristiquep, tous ces termes sont nuls dansF, et on obtient f(x+y) = (x+y)p=xp+yp=f(x) +f(y):

Ceci prouve quef:F!Fest un morphisme d"anneaux.

Or,Fest un corps et tout morphisme de corps est injectif. Comme le cardinal deFest fini,fest une bijection.Exemple

Le groupe d"automorphismes d"un corps fini

Proposition

SoitFun corps de cardinalpn.Le groupeAut(F)des automorphismes deFest cyclique d"ordren, engendr

´e par l"automorphisme de Frobeniusf:F!F,x7!xp.AinsiAut(F) =hfi=Z=net pour toutdjnil existe un unique

sous-groupeHAut(F)d"indiced,`a savoirH= fd.D ´emonstration.On afk(x) = ((xp)p))p=xpkpour toutx2F. Sifk= idFpour0< k < n, alorsXpkXauraitpnracines dansF.

Finalement on afn= idFcarxpn=xpour toutx2F.

Choisissonsa2Ftel queF=Fp[a], par exemple une racine primitive deF. SoitP2Fp[X]son polynˆome minimal; ainsiFp[X]=(P)=Fetdeg(P) =n. Les automorphismesidF=f0;f1;:::;fn1permutent les racines deP, carP(x) = 0entraˆıneP(fk(x)) =fk(P(x)) =fk(0) = 0. Sifkfixea, alorsfkfixeFp[a] =F, doncfk= idFetk2nZ. Ceci fait quea;f1(a);:::;fn1(a)sont lesnracines distinctes deP. Tout automorphismeg2Aut(F)permute lesnracines deP. Il existe donc unk2 f0;1;:::;n1gtel queg(a) =fk(a). Ainsifkg1fixeaet doncF=Fp[a]. Ceci veut dire queg=fk.x1.211/32

Sous-corps fix

´e par des automorphismesLemme

SoitFun corps et soith:F!Fun automorphisme.

AlorsK=fx2Fjh(x) =xgest un sous-corps deF.D

´emonstration.On a02K, eta;b2Kimpliquea+b2K, car h(a+b) =h(a) +h(b) =a+b: On ah(a) =h(a) =a, donc l"oppos´e dea2Kaussi est dansK.

On a12K, eta;b2Kimpliqueab2K, car

h(ab) =h(a)h(b) =ab: Poura2Kon ah(a1) =h(a)1=a1, donca1aussi est dansK.Corollaire SoitFun corps et soitHAut(F)un groupe d"automorphismes. AlorsFH=fx2Fjh(x) =xpour touth2Hgest un sous-corps deF.Exemple Pour tout corps finiFnous avonsFhfi=fx2Fjxp=xg=Fp.x1.212/32 Polyn

ˆomes remarquables sur un corps finiLemme

SoitFun corps fini de cardinalq. AlorsXqX=Q

a2F(Xa).D ´emonstration.D"apr`es le th´eor`eme de Lagrange, touta2Fv´erifie a q1= 1, doncaq=a. Cette derni`ere´egalit´e est aussi v´erifi´ee poura= 0. On trouve ainsiqracines distinctes du polynˆomeXqX, qui est de degr´eq, ce qui ´equivaut`a la factorisation compl`ete´enonc´ee.Lemme Dans l"anneau euclidienFp[X]des polynˆomes surFpnous avons pgcd(XpmX; XpnX) =XpdXo`ud= pgcd(m;n): En particulier,XpmXdiviseXpnXsi et seulement simdivisen.D ´emonstration.Supposons quem=sn+ro`u0r < n. Alors X pm=Xpsn+r= (((Xpn)pn)pn)prXprmoduloXpnX:

Ainsi le calcul revient

`a calculerpgcd(m;n)dans les exposants.x1.313/32

Sous-corps d"un corps fini

Proposition

SoitFun corps fini de cardinalpn.SiKest un sous-corps deF, alorsjKj=pdo`udjn.Pour toutdjnil existe un unique sous-corpsKFde cardinalpd.D

´emonstration.Le corpsFcontient le sous-corps premier estFp. D"une part tout sous-corpsKcontientFp, doncjKj=pdavecd= dimFpK. D"autre partFest unK-espace vectoriel, doncjFj=jKjmo`um= dimKF.

On conclut quepn=pdm, doncdjncomme souhait´e.

R ´eciproquement, pour tout diviseurdjn, nous avons un sous-corps

K=fa2Fjapd=ag=Fhfdi:

Comme le polyn

ˆomeXpdXdiviseXpnX=Q

a2F(Xa), on obtientXpdX=Q a2K(Xa). Ceci prouve quejKj=pd. Finalement, siLest un sous-corps de cardinalpd, alors tous ses´el´ements sont racines deXpdX, ce qui impliqueL=K, d"o`u l"unicit´e´enonc´ee.x1.314/32

Correspondance de Galois pour un corps fini

Th ´eor`emePour tout corps finiFnous avons une correspondance naturelle entre les sous-corps deFet les sous-groupes deAut(F):`

A tout sous-corpsKFon associe le sous-groupe

Gal(FjK) :=fh2Aut(F)jh(x) =xpour toutx2Kg:`

A tout sous-groupeHAut(F)on associe le sous-corps

F H:=fx2Fjh(x) =xpour touth2Hg:Ce sont des bijections mutuellement inverses :

Pour tout sous-corpsKFnous avonsFGal(FjK)=K.Pour tout sous-groupeHAut(F)nous avonsGal(FjFH) =H.Explicitement, siKest de cardinalpd, alorsGal(FjK) =

fd.SiHAut(F)est d"indiced, alorsFHest le sous-corps de cardinalpd.SoitKFun sous-corps. Tout automorphismeh:F!Fse restreint`a un

automorphisme deKcarh(K) =K. On obtient ainsi un´epimorphisme de groupesAut(F)!Aut(K),h7!hjK, qui a pour noyau le groupeGal(FjK).x1.315/32 D

´emonstration de la correspondance de Galois

SoitFun corps fini. Il est de cardinalpno`upest premier etn1. Le groupeAut(F)est cyclique d"ordrenengendr´e parf:F!F,x7!xp. Tout sous-corpsKFest de cardinaljKj=pdo`udjnet ainsi

K=fx2Fjxpd=xg=Fhfdi:

Montrons queGal(FjK) =

fd, l"inclusionGal(FjK) fd´etant claire. Nous savons que le sous-groupeGal(FjK)est de la formehfeio`uejn.

Commehfei

fdnous avons alorsejd. Observons ensuite que

KFGal(FjK)=fx2Fjxpe=xg:

PuisquejKj=pd, ceci exclute < d. On a donce=detGal(FjK) = fd.Ceci prouve queFGal(FjK)=Kainsi queGal(FjFH) =H.L"unicit ´e du sous-corpsKde cardinalpddansFassure queh(K) =K pour tout automorphismeh2Aut(F). Ainsi nous obtenons une morphismeAut(F)!Aut(K)par restriction. Il est surjectif carAut(K), commeAut(F), est engendr´e parf. Le noyau est le sous-groupeGal(FjK)par d´efinition.x1.316/32 Polyn

ˆomes irr´eductibles surFpLemme

SiP2Fp[X]est un polynˆome irr´eductible de degr´en, alorsPdiviseXpnXmais ne divise pasXpdXpourd < nD ´emonstration.SiP2Fp[X]est irr´eductible de degr´en, alors le quotient F=Fp[X]=(P)est un corps de cardinalq=pn. L"´el´ementx=X2Fest une racine commune dePet deXqX, donc deP1= pgcd(P;XqX). Ceci implique en particulier quedegP11. Or,Pest irr´eductible, donc P

1jPimpliqueP1P. Par cons´equentPjXqX.

Supposons par l"absurde quePdiviseXpdXpour und < n. AlorsPdivise aussipgcd(XpnX;XpdX), nous pouvons donc supposerdjn. Dans ce casx=Xserait contenu dans le sous-corps strictK=fa2Fjapd=agde cardinalpd< pn. Mais les puissances1;x;:::;xn1forment une base deF, donc le plus petit sous-corps contenantxestF.x2.117/32 Crit `ere d"irr´eductibilit´e dansFp[X]Proposition

Un polyn

ˆomeP2Fp[X]de degr´enest irr´eductible si et seulement siP diviseXpnXetpgcd(P;Xpn=tX) = 1pour tout diviseur premiertden.D ´emonstration.SiPest irr´eductible de degr´enalorsPdiviseXpnX mais aucun des polyn

ˆomesXpn=tX, doncpgcd(P;Xpn=tX) = 1.

R ´eciproquement supposons quePdiviseXpnX, et que pgcd(P;Xpn=tX) = 1pour tout diviseur premiertden. SoitQun diviseur irr ´eductible deP, de degr´em. On sait queQdiviseXpmXo`umjn. Si m < nalorsQdiviserait unpgcd(P;Xpn=tX), ce qui est exclus.

Par cons

´equentm=n, et ainsiPQ.!Souvent le degr

´en= deg(P)est raisonnablement petit,

mais le degr ´epndeXpnXest d´eraisonnablement grand!L"algorithme suivant r ´eduit tous les calculs au degr´e< n.x2.118/32

Algorithme pour tester l"irr

´eductibilit´e dansFp[X]Algorithme 11.1Tester l"irr´eductibilit´e deP2Fp[X]Entr ´ee:un polynˆomeP2Fp[X]de degr´enainsi que la d

´ecompositionn=ne11nekken facteurs premiers.

Sortie:"irr´eductible»siPest irr´eductible,"compos´e»sinon.Q XpnremP// puissance dichotomique modulaire

siQ6=Xalors retourner"compos´e»// carP-XpnX pouride1`akfaire m n=ni

Q XpmremP// puissance dichotomique modulaire

R pgcd(P;QX)// algorithme d"Euclide

siR6= 1alors retourner"compos´e»// carpgcd(P;XpmX)6= 1 fin pour retourner"irr´eductible»// d"apr`es la proposition pr´ec´edenteExercice Prouver que l"algorithme ci-dessus est correct. Estimer sa complexit

´e.x2.119/32

Corps finis et polyn

ˆomes irr´eductiblesProposition

SoitFun corps fini de cardinalpn. Alors il existe un polynˆomeP2Fp[X] unitaire irr

´eductible de degr´entel queF=Fp[X]=(P).D

´emonstration.Nous avonsFpFcomme sous-corps premier. Il existex2Ftel queFp[x] =F, par exemple une racine primitive deF. Le morphisme d"anneaux':Fp[X]!F,X7!x, est donc surjectif. Son noyau est de la formeker'= (P)o`uP2Fp[X]est unitaire.

Ainsi'induit un isomorphisme':Fp[X]=(P)!F.

En particulierPdoitˆetre irr´eductible de degr´en.Corollaire Il existe un corps de cardinalpdsi et seulement s"il existe un polyn ˆome irr´eductibleP2Fp[X]de degr´ed.On montrera plus bas qu"il existe des polyn

ˆomes irr´eductiblesP2Fp[X]

de tout degr ´ed. On les comptera mˆeme assez explicitement.x2.220/32

Unicit

´e du corps de cardinalpn

A priori deux polyn

ˆomes diff´erentsP;Q2Fp[X], suppos´es irr´eductibles de degr ´en, m`enent`a deux corps diff´erentsFp[X]=(P)etFp[X]=(Q).Or, le r ´esultat est toujours le mˆeme`a isomorphisme pr`es :Proposition SoitFun corps de cardinalpn. Alors pour tout polynˆome irr´eductible P2Fp[X]de degr´enl"anneau quotientFp[X]=(P)est isomorphe`aF.D ´emonstration.Nous avons la d´ecompositionXpnX=Q a2F(Xa).

Le polyn

ˆomePdiviseXpnX, donc il existex2Ftel queP(x) = 0. Le morphisme':Fp[X]!F,X7!x, a pour noyau l"id´eal(P), puisqueP est irr ´eductible. Par passage au quotient on obtient un morphisme injectif ':Fp[X]=(P),!F. CommeFp[X]=(P)etFont mˆeme cardinal, il s"agit bien d"une bijection. On obtient ainsi l"isomorphisme':Fp[X]=(P)!F.x2.321/32

Unicit

´e du corps de cardinalpnCorollaire

Deux corps finis de m

ˆeme cardinal sont isomorphes.D

´emonstration.SiEetFsont deux corps finis de cardinalpn, alors il existe un polyn ˆome unitaire irr´eductibleP2Fp[X]de degr´en. Ainsi':Fp[X]=(P)!Fet :Fp[X]=(P)!E, puis' 1:E!F.Remarque

Il n"y a pas d"identification canonique entre les

´el´ements deEetF!´

Etant deux corpsEetFde cardinalpnil existe un isomorphismeE!F.

Ceci entra

ˆıne qu"il existe exactementnisomorphismes entreEetF, car le groupe d"automorphismes est de cardinaljAut(E)j=n.

Le seul cas o

`u tout est canonique estn= 1, c"est-`a-dire queE=F=Z=p.Notation Il est souvent commode de noter parFquncorps de cardinalq.

Par un l

´eger abus de langage on appelleFqlecorps de cardinalq.x2.322/32 D

´ecomposition deXpnXdansFp[X]Lemme

Le polyn

ˆomeQ=XpnXdansFp[X]n"a pas de facteurs multiples. Autrement dit : siQ=U2Vo`uU;V2Fp[X], alorsdegU= 0.D ´emonstration.D"un cot´e la d´eriv´ee deQdansFp[X]est Q

0=pnXpn11 =1:

De l"autre cot

´e, la d´eriv´e deU2Vest

2UU0V+U2V0=U(2U0V+UV0):

DoncUest inversible, c"est-`a-diredegU= 0.Remarque

Si nous savions d

´ej`a qu"il existait un corpsFde cardinalpn, alors la d

´ecompositionQ=Q

a2F(Xa)montrerait l"absence de facteurs multiples. Or, nous sommes en train de prouver justement cette existence. La d ´emonstration ci-dessus´evite tout raisonnement circulaire.x3.123/32 D

´ecomposition deXpnXdansFp[X]Th

´eor`emeSoitIdpFp[X]l"ensemble des polynˆomes unitaires irr´eductibles de degr´ed.

Alors dansFp[X]on a la d´ecompositionXpnX=Q

djnQ

P2IdpP.D

´emonstration.PourdjntoutP2IdpdiviseXpdXet doncXpnX.

Ainsi leur ppcmM:= ppcmfPjP2Idp;djngdiviseQ.

quotesdbs_dbs29.pdfusesText_35

[PDF] exercices corps finis

[PDF] morphisme de frobenius

[PDF] caractéristique d'un dipole actif

[PDF] dipole actif generateur

[PDF] dipole passif

[PDF] exercice dipole actif

[PDF] dipole actif exemple

[PDF] dipole actif pdf

[PDF] caractéristiques de quelques dipoles passifs exercices corrigés

[PDF] caractéristique de quelques dipoles passifs tronc commun

[PDF] source de courant source de tension

[PDF] source idéale de tension continue

[PDF] source de courant exemple

[PDF] source de courant idéale definition

[PDF] source de courant réelle