[PDF] 1 Construction des corps finis 2 Structure des corps finis

View - Download 1 Construction des corps finis 2 Structure des corps finis

Previous PDF

Next PDF

123. Corps finis. Applications.

Introduction: Les corps finis ayant la propri´et´e d"ˆetre constructibles de fa¸con effective, ils sont tr`es utilis´es en cryptographie et pour les codes correcteurs d"erreurs.

1 Construction des corps finis

1.1 Corps de cardinal premier

Th ´eor`eme 1.Soitn?N?.Z/nZest un corpsssinest premier. Application(Wilson).Soitp?N?.pest premierssi (p-1)!≡ -1[p]. Pourp?N?premier, on noteraFple corpsZ/pZ. Y en a-t-il d"autres? Exemple.F2/(X2+X+ 1)est un corps `a 4 ´el´ements.

1.2 Corps de cardinal primaire

SoitFun corps fini.

D ´efinition 1.On appelle sous-corps premier le plus petit sous-corps deF. Lemme 1.Soit?:Z→Fd´efini par?(n) =n·1F. C"est un morphisme d"anneaux, son noyau est donc un id´eal deZ, de la formepZavecppremier.pest le cardinal du sous-corps premier deF, et celui-ci est isomorphe `aFp. D ´efinition 2.pest appel´e caract´eristique deF. Contre-exemple.F2(X)est un corps infini de caract´eristique finie2. Proposition 1.Fposs`ede une structure deFp-espace vectoriel de dimension finie.

Ainsi, il existen?N?,|F|=pn.

Proposition 2.SoitFun corps fini de caract´eristiquep. L"application?:F→F d´efinie par?(x) =xpest un automorphisme deF(et l"identit´e siF=Fp). Application(Fermat).Soitppremier, alors pour touta?Z,ap≡a[p]. Th ´eor`eme 2.R´eciproquement, soitp?N?premier, soitq=pn. Il existe un corps de cardinalq, c"est un corps de d´ecomposition deXq-XsurFp. De plus, siF,F? sont deux corps de cardinalq, alors ils sontFp-isomorphes.2 Structure des corps finis 2.1

´El´ements inversibles

Proposition 3.Soitppremier, soitq=pr. AlorsF?qest un groupe cyclique. 2.2

´El´ements carr´es

D ´efinition 3.SoitFqcorps fini de caract´eristiquep. On noteF2q={x2,x?Fq}, on d´efinit de mˆeme (F?q)2. Proposition 4.Sip= 2, on aF2q=Fq. Sip >2, on a|F2q|=q+12 Proposition 5.On supposep >2, soitx?F?q. Alorsx?F2q?xq-12 = 1.

Corollaire 2.-1?F2q?q≡1[4].

Application.Il existe une infinit´e de nombres premiers de la norme4m+1,m?N. Lemme 2.Pour tousα,β?Fq, l"´equationαx2+βy2= 1 d"inconnuesx,y?Fq admet au moins une solution. Th ´eor`eme 3.SoitFqun corps fini de caract´eristique diff´erente de 2. Alors il y a

2n+1 orbites pour l"action de congruence surSn(Fq), repr´esent´ees par les matrices

A=?Ir 0 n-r? etB=( (I r-1 0 n-r) , o`uα?F?q\F2q. D

´efinition 4.Soitppremier.

On d´efinit poura?F?ple symbole de Legendre?ap

=?1 sia?F2p-1 sinon.

Proposition 6.On a, pour touta?F?p,?ap

=ap-12 Th ´eor`eme 4(Frobenius-Zolotarev).Soitp≥3 premier, soitu?GLn(Fp). Alors

ε(u) =?det(u)p

Th ´eor`eme 5(R´eciprocit´e quadratique).Soientp,qpremiers.

Alors?pq

qp = (-1)p-12 q-12

Exemple.65 est un carr´e dansF29.

2.3 Sous-corps

Proposition 7.SoitFqcorps de cardinalq=pr. SiKest un sous-corps deFq, alors il existeddiviseur dentel que|K|=pd. R´eciproquement, pour toutddiviseur den,Fqposs`ede un unique sous-corps de cardinalpd. Contre-exemple.F16n"a pas de sous-corps de cardinal 8.

3 Applications

3.1 Irr´eductibilit´e et factorisation de polynˆomes

Th ´eor`eme 6.Soitppremier,q=pn,n?N?. Alors, pour toutP?Fp[X] irr´eductible de degr´en,Fqest isomorphe `aFp/(P). Corollaire 3.Il existe des polynˆomes irr´eductibles de tout degr´e dansFp[X]. De plus, siP?Fp[X] irr´eductible, son corps de rupture est aussi son corps de d´ecomposition. Lemme 3.SoitP?Fq[X],deg(P) =n, soitE=Fq[X]/(P). On a dim(E) =net siφ:E→Eest d´efinie parφ(Q) =Qq,φest lin´eaire.

On noteSPla matrice deφ.

Algorithme 1(Berlekamp).SoitP?Fq[X] unitaire sans facteur carr´e.

1. On calculeSP-Inet sir:=n-rg(Sp-I) = 1, on retourneP.

2. Sinon, calculerV?ker(Sp-In) non constant moduloPet pour toutα?Fq,

calculerDα=P?(V-α). Appliquer l"algorithme `aDα. Th ´eor`eme 7.L"algorithme de Berlekamp termine et retourne la d´ecomposition de

Pen facteurs irr´eductibles.

Algorithme 2.SoitP?Fq[X].

1. CalculerD=P?P?.

2. SiD=P, calculerRtel queP=Rpet appliquer l"algorithme `aR. SiD= 1,

appliquer Berlekamp `aP. Sinon, appliquer Berlekamp `aP/Det retourner en

1 avecD.

Th ´eor`eme 8.Cet algorithme termine et retourne la d´ecomposition dePen facteurs irr´eductibles. Th ´eor`eme 9.SoitP?Z[X], soitppremier. On notePle polynˆome obtenu en r´eduisant moduloples coefficients deP. Alors, siPest irr´eductible dansFp[X] et

deg(P) = deg(P), alorsPest irr´eductible dansQ[X].Exemple.P= 3X2+ 17X-11est irr´eductible dansQ[X].

Contre-exemple.X4+ 1est irr´eductible dansZ[X]mais r´eductible dansFp[X] pour toutp?N?premier.

3.2 Codes correcteurs d"erreurs

La transmission d"informations peut parfois ˆetre entach´ee d"erreurs. Les codes cor- recteurs permettent, dans une certaine mesure, de d´etecter voire de corriger ces erreurs. D ´efinition 5.SoitEun ensemble, on appelle mot de longueurkd"alphabetEun k-uplet (b0,···,bk-1)?Ek. Exemple.Dans un ordinateur, les informations sont envoy´ees par mots de 7 ca- ract`eres `a valeurs dansF2(bits). On ajoute `a chaque mot(b0,···,b6)un huiti`eme bit, appel´e bit de parit´e, donn´e parb7=b0+···+b6(mod 2). Ce bit permet de d´etecter si un des bits a ´et´e mal transmis.

On adopteraFqcomme alphabet.

D ´efinition 6.On appelle code correcteur de longueurnune sous-partie deFnq. Si cette sous-partie est un sous-espace vectoriel de dimensionm, on parlera de code lin´eaire de dimensionm. Le code correcteur contient l"ensemble des mots que l"on peut produire par codage. Ainsi, un mot re¸cu contient une erreur s"il n"est pas dans le code. D ´efinition 7.Soientx,ydeux mots deFnq. On d´efinit leur distance de Hamming, not´eed(x,y), comme le nombre de coefficients non nuls dex-y. D ´efinition 8.Un code est ditt-correcteur, pourt?N, si les boules de centre un mot du code et de rayontsont disjointes. Ainsi, si un mot re¸cu se situe dans une des boules, on le corrige en le mot du centre de la boule. Proposition 8.SoitCun code correcteur, on poseδ= min{d(x,y),x,y? C,x?=y}.

Siδ≥2t+ 1, alorsCestt-correcteur.

Exemple(Un code de Hamming).SoitG=(

((1 1 0 1 0 0 0

0 1 1 0 1 0 0

0 0 1 1 0 1 0

0 0 0 1 1 0 1)

))T On consid`ere le code lin´eaire de taille 7, de dimension 4 surF2d´efini par

C={Gx,x?F42}. Ce code est 1-correcteur.

D´eveloppements

- Algorithme de Berlekamp. - Loi de r´eciprocit´e quadratique.

R´ef´erences

[1] V. Beck, J. Malick, G. Peyr´e,Objectif Agr´egation, H&K. [2] I. Gozard,Th´eorie de Galois, Ellipses. [3] D. Perrin,Cours d"alg`ebre, Ellipses. [4] A. Szpirglas et al.,Alg`ebre L3, Pearson.quotesdbs_dbs28.pdfusesText_34

[PDF] caracteristique d'un corps

[PDF] théorie des corps finis

[PDF] polynomes irreductibles corps finis

[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