[PDF] Rappel darithmétique : Anneaux modulo N

View - Download Rappel darithmétique : Anneaux modulo N

Previous PDF

Next PDF

Rappel d'arithmetique : Anneaux moduloN

A. Dragut Univ. Aix-Marseille

Cours de cryptographieChapitre II

Denition.Deux entiersaetbsont dits congrus moduloN, ouN2est un entier si leur dierence est divisible parN, c.a-d. qu'il existe un entierktel queab=kN. On note ab(modN)et on dit queaest equivalent/congru abmoduloN. Souvent, par commodite,est remplace par = m^eme si cela reste faux dans l'absolu . Notation.ZNouZ=NZ=f0;1;2;:::;N1gl'ensemble des restes moduloN(c.a-d. a la division parN) On denie surZNdes operations d'addition et de multiplication analogues a celles denies sur les entiers : Addition :a deux restesaetb, on associe le reste de la sommea+ba la division parN et on note "(a+b) (modN)". Ainsi modulo 7, on ecrira 3 + 2 = 5 mais 4 + 4 = 1 car la somme de 4 et 4 a pour reste 1 modulo 7. Multiplication :a deux restesaetb, on associe le reste de produitaba la division parN et on note "(ab) (modN)". Ainsi modulo 7, on ecrira 22 = 4 mais 33 = 2 car le produit de 3 et 3 a pour reste 2 modulo 7. Pour ces operations dansZ=NZ, il est naturel de s'interesser a l'existence de l'oppose et de l'inverse moduloN, ainsi qu'aux puissances successives. Denition.Un anneau unitaire est un triplet(A;+;)tel que :

1. A est un ensemble

2. la loi+est une loi de composition interne telle que(A;+)soit un groupe commuta-

tif/abelien, c.a-d. { la loi + est associative :a+ (b+c) = (a+b) +c; {Aun element neutre pour la loi+, note0:a+ 0 = 0 +a=a; { tout elementadeAa un oppose, notea:a+ (a) = (a) +a= 0; { la loi+est commutative :(a+b=b+a);

3.est une loi de composition interne associative :(ab)c=a(bc) =abc;

4. la loiest une loi de composition interne distributive par rapport a+:

{a(b+c) = (ab) + (ac)(Distributivite a gauche); {(a+b)c= (ac) + (bc)(Distributivite a droite);

5.Aa un element neutre pour la loi, note1:a1 = 1a=a;

6.Aest un anneau commutatif si sa seconde loiest aussi commutative :(ab=ba);

7. un elementa2Aest inversible si existeb2Aetab=ba= 1. On noteb=a1= 1=a.

1 Proposition.(Z=NZ;+;)est un anneau unitaire commutatif. Notation.On note avec(Z=NZ)ouZNle sous-groupe multiplicatif du(Z=NZ;+;)forme par ses elements inversibles.

2.1 Algorithme d'Euclide etendu.

Lemme1.Soienta,b,qetr >0aveca=qb+r. Alorspgcd(a;b) = pgcd(r;b). On utilise ce lemme pour calculer le plus grand diviseur commun des entiersjetk. L'algorithme est recursif et reduit les entiers jusqu'a ce que le reste devienne nul. Il est convenable de supposer que les deux entiers sont positifs et queba.

Algorithme du pgcd etendu

On modie maintenant l'algorithme pour qu'il renvoie les entiersxetypour lesquels pgcd(a;b) =xa+yb. Pour cela, il sut d'eliminer successivement les restes des divisions et de remonter les calcules des divisions euclidiennes. Exemple.Trouver les coecients Bachet-Bezout pour255et141en utilisant l'algorithme d'Euclide etendu. (1) 255 = 1141 +114 (2) 141 = 1114 +27 (3) 114 = 427 +6 (4) 27 = 46 +3

6 = 23 + 0

Maintenant on elimine les restes :

4 = 2746

=274(114427) =4114 + 1727 =4114+ 17(1411114) = 1714121114) = 1714121(2551141) = 3814121255

Les coecients Bachet-Bezout sont 38 et21.

2

2.2 Le sous-groupe((Z=NZ);). Calcul de l'inverse(modN)

2.2.1 Calcul de l'inverse modulaire avec Euclide etendu

Denition.Deux entiersaetbsontpremiers entre eux(ou bienaest ditpremier avecb) s'il n'ont pas de diviseurs premiers communs, ou bien, de maniere equivalente, sipgcd(a;b) = 1. Theoreme. [Bachet-Bezout]Soient deux entiers non-nulsuetv. Sipgcd(u;v)est le PGCD deuet dev, alors il existe deux entiersxetytels quexu+yv= pgcd(u;v)En particulier, deux entiers sont relativement premiers entre eux si et seulement s'il existe deux entiersxetytels quexu+yv= 1 Corollaire.Soita2Z=NZtel queaetNsont premiers entre eux, alorsaa un inverse moduloN. Preuve.Donca2(ZNle sous ensemble deZ=NZcontenant les elements premiers avec N, c.a-d.fa2Z=NZjpgcd(a;N) = 1g. Parce quepgcd(a;N) = 1, l'algorithme etendu d'Euclide renvoie les entiersUetVtels queUa+V N= 1. En appliquant le moduloN a cette equation, on elimine le multiple deN. On obtient doncUa1 (modN). Selon la denition de l'inverse moduloN(c.a-d.U1U1 (modN)), l'entierUest l'inverse de a. On peut utiliser l'algorithme etendu d'Euclide pour calculer l'inverse multiplicatif dea tel quepgcd(a;N) = 1.

Exemple.91(mod 16)

16 = 19 + 7;

9 = 17 + 2;

7 = 32 + 1;

2 = 21 + 0 donc pgcd(16;9) = 1.

En ecrivant les restes nous avons 7 = 1619;2 = 917. En commencant du dernier reste non-nul nous avons

1 = 732 = 73(917) =39 + 47 =39 + 4(1619).

1 = 41679 et donc 91=7 = 9 (mod 16).

Une autre variante de calculer l'inverse multiplicatif moduloNavec unNpetit est d'utiliser directement le theoreme Bachet-Bezout pour deux nombres qui sont premiers entre eux. Six= 91, alors 9x1 (mod 16). Donc on ecrit : 9x= 16k+ 1 et on itere sur k= 1;2;:::;161 pour trouver un multiple de 9. Pourk= 1 on obtient 17, apres 33, apres

49, apres 65, apres 81 qui est un multiple de 9. Donc 9

1= 9 (mod 16).

2.2.2 Calcul de l'inverse modulaire avec Euler/Fermat

Corollaire.Sipest premier, alors chaque entier non-nula2Z=pZa un inverse. On note avecFp= (Z=pZ)= 1;2;:::;p1 3 Preuve.En supposantpgcd(e;N) = 1, l'algorithme etendu xPGCD renvoie les entiersUet Vtels queUe+V N= 1. En appliquant le moduloNcette equation, on obtient les entiers Ue1 (modN). Donc selon la denition de l'inverse moduloN, l'entierUest l'inverse de e. Corollaire.Sipest premierFp= (Z=pZ)= 1;2;:::;p1est le sous-groupe du corpsZ=pZ par rapport a la loi. Denition.Soit l'anneauZ=NZet soit(Z=NZ)=fa2Z=NZjpgcd(a;N) = 1gson sous-groupe contenant les entiers qui sont premiers avecN. On appelle fonction indicatrice d'Euler(N)la cardinalite de(Z=NZ), c'est-a-dire(N) =j(Z=NZ)j.

Les proprietes de(N) sont :

1. Sipest premier, alors(p) =p1

2. Plus generalement, sipest premier etk1, alors

(pk) =pkpk1= (p1)pk1

3. Si pgcd(p;q) = 1, alors(pq) =(p)(q).

4. SiN=pe11pekk, oup1;:::;pksont des nombres premiers tous distincts, ete1;:::;ek

sont des entiers positifs. Alors (N) = (p11)pe11

1(pk1)pek1

k Exemple.Calculer(126)en utilisant la factorisation deN= 2327. (126) =(2)(32)(7) = (21)(31)(321)(71) = 1236 = 36 Theoreme(Euler).x(N)1 (modN)pour toutx2(Z=NZ), c.a-d.pgcd(a;N) = 1. La preuve est immediate seulement pour ceux familiers avec la theorie de groupes. On ap- plique le Th. de Lagrange pour (Z=NZ)et pour le sous-groupe cyclique genere parx. Sinon on peut se contanter de prouver separement le cas special d'une version reduite Theoreme(petit theoreme du Fermat version reduite).xp11 (modp)pour toutx2 (Z=pZ),1xp1, oupest premier. 4

Preuve.

Ebauche :

On prend les nombresx;2x;:::;(p1)x. Nous avons queixjxsi et seulement si (ij)xest divisible parp. Maispgcd(x;p) = 1et0(ij)< p1et donc il ne peut pas ^etre un vrai multiple dep. Doncij= 0. Donc ils sontp1nombres distinctes modulop. Mais dans le groupe(Z=pZ)il n'y a quep1elements distincts au total. Donc x2x:::(p1)x= (p1)!. Alors,(p1)!x(p1) = (p1)!. En simpliant on prouve le resultat. Theoreme(petit theoreme du Fermat).Soitpun nombre premier etxun entier arbitraire.

Alorsxp11 (modp)ou equivalentxpx(modp)..

Preuve.L' hypothese du theoreme est verie pour x = 0 et x = 1. Supposons par induction que hypothese est vraie pour un nombre entierxet verions la pourx+ 1. Mais(x+ 1)p x p+ 1x+ 1 (modp)parce que (x+y)p=pX k=0p!k!(pk)!xpkyk:

Donc le pas d'induction est verie.

Pourp= 2hypothese est vraie aussi pour tout entier negatif. Sipest impaire etxpx (modp)nous avons(x)pxp x(modp).

Exemple.Calculer95(mod 19)(pour ElGamal)

L'entier 19 est premier. On sait que 9

181 (mod 19). Mais 1918= 91395(mod 19).

Donc selon la denition de l'inverse modulop= 19 nous avons que 959133 (mod 19)

2.3 Le theoreme chinois des restes

Theoreme.(Le theoreme chinois des restes)Sin1;;nksont deux a deux premiers entre eux alors, en notantnle produit desni, la fonction :Z=NZ!Z=p1Z Z=pkZ

7!((modp1);:::;(modpk))

est un isomorphisme d'anneaux. Dans le cas ou lespine sont pas premiers entre eux,Nest leur ppcm et le morphisme ci-dessus n'est qu'injectif. Theoreme.(Le theoreme chinois des restes version des congruences)Soient p

1;;pksont deux a deux premiers entre eux. On note avecNle produit despi. Soient les

entiers arbitrairement choisis1;;k. Alors il existe un entierz, unique moduloN, tel que z1(modp1) zk(modpk) 5

Preuve.Parce que pour chaquei, les entierspietNp

i=p1:::pi1pi+1:::pksont premiers entre eux, le theoreme de Bachet-Bezout s'applique et il existe les entiersui, etvi, tels que u ipi+viNp i= 1.

Pourei=viNp

inous avons pour chaquei e i1 (modpi) e i0 (modpj)pourj6=i

Une solutionzdu systeme de congruences estz=Pk

i=1iei, ouei=vinn ietvisont les entiers du le theoreme de Bachet-Bezout. Soitzune autre solution du systeme de congruences. Nous avonszz(modpi)pour chaquei. Donc il existe l'entierttel quezz=tp1. Parce que pour chaquei, les entiers p isont premiers entre euxtest divisible parpjpour chaquej6=i, donczzest divisible parN=p1:::pk.zz(modN) 6

2.4 Groupe cyclique ni. Resultats pour ElGamal

Denition.Un groupe cycliqueG, est un groupe dans lequel il existe un elementgtel que tout element du groupe puisse s'exprimer sous forme d'un multiple/puissance deg, cet elementgest appele generateur du groupe et on noteG=< g >.

En notation additive: (G;+) [n]g

En notation multiplicative: (G;)gn

Denition.SoitGun groupe etg2G, alors le groupe sous-groupeHgenere parg, note H=< g >, est le plus petit sous-groupe deGcontenantg. Denition.L'ordre d'un elementgd'un groupeGest noteordre(g)ouo(g). Si l'ordre est ni, il est le plus petit entierm >0tel que { En notation additive :mg= 0 { En notation multiplicative :gm= 1 On peut dire que si l'ordre degest niordre(g) =jHj=j< g >jla cardinalite sous-groupeH=< g >genere parg. Pour un groupeGni, la cardinalite sous-groupeH=< g >Ggenere pargest un nombre ni n'importe quel elementgmultiplie par lui-m^eme de maniere repetee doit ^etre dans le groupeG. Mais le groupeGa un nombre ni d'elements, alors les puissances deg nissent par se repeter.

Exemple.Pourx= 52(Z=26Z):5;25;21;1;5;25;21;1;:::

Exemple.Trouver l'ordre de l'element2dans

{F11= (Z=11Z)=f1;2;:::;10gle groupe multiplicatif de restes modulo11 {F17= (Z=17Z)=f1;2;:::;16gle groupe multiplicatif de restes modulo17 DansF11nous avons 20= 1, 21= 2, 22= 4, 23= 8, 245, 2510, 269, 277, 2

83, 296. Mais 2101 et on commence a repeter les elements.

Doncordre(2) = 10 et il genere tout le groupeG.

DansF17nous avons 20= 1, 21= 2, 22= 4, 23= 8,24= 16, 2515, 2613, 279.

Mais 2

81 et on commence a repeter les elements. Donc 2 n'est pas un generateur pour

F

17. Il genere que le sous-groupeH=<2>=f1;2;4;8;9;13;15;16get son ordre est la

cardinalite de ce sous-groupe, donc 8. Pourppremier la structure du groupe multiplicatif deZ=pZest celle d'un groupe abelien ni cyclique d'ordre(p) =p1. Theoreme. [racine primitive/generateur]Soitppremier. Alors il existeg2Fptel que (Fp;) =f1;g;:::;gp2g. L'ordre degestord(g) =jFpj=p1. Corollaire.(du Th. Lagrange) Soitpun entier premier. SoitH=< g >(Fp;)etord(g) = jHj=q. Alorsq=(p1). 7 Exemple.F11:20= 1,21= 2,22= 4,23= 8,245,2510,269,277,283, 2

96,2101, mais2n'est pas un generateur pourF17.

Exemple.Le groupe multiplicatifF11a la cardinalite10, donc les ordres des elements de Z

11sont :1;2;5;10.

Par exemple<3>= 1;3;9;5;4 est le sous-groupe d'ordre 5 du groupe multiplicatifF11. 8quotesdbs_dbs21.pdfusesText_27

[PDF] algorithme de dijkstra python

[PDF] algoritmo de dijkstra java

[PDF] aliexpress france avis

[PDF] alkyl and aryl halides notes pdf

[PDF] alkyl halides notes pdf

[PDF] all google sites list

[PDF] all html5 tags list with examples pdf

[PDF] all police codes mn

[PDF] all the methods in the interface are internally

[PDF] allan_and_barbara_pease_ _body_language_the_definitive_book.pdf

[PDF] allemand langage familier

[PDF] aller + infinitif exercices

[PDF] aller retour paris ajaccio air france

[PDF] aller retour paris nice avion

[PDF] alliance gradebook pinnacle