[PDF] [PDF] Rappel darithmétique : Anneaux modulo N - CNU 27 Marseille





Previous PDF Next PDF



Inverser un nombre modulo n

Soit n un entier > 1. On cherche à trouver l'inverse de a modulo n s'il existe. On sait que a est inversible modulo n (c'est-à-dire dans l'anneau Z/nZ) si 



Rappel darithmétique : Anneaux modulo N

U?1 · U ? 1 (mod N)) l'entier U est l'inverse de a. On peut utiliser l'algorithme étendu d'Euclide pour calculer l'inverse multiplicatif de a tel que pgcd(a



INVERSE MODULAIRE DUN ENTIER RELATIF

a?1 b [n]. Mais peut-on toujours inverser ainsi un entier relatif ? ... Si n est un nombre premier combien de nombres admettent un inverse modulo n ?



Sans titre

Définition du résidu : Modulo p pour tout nombre n



Petit théorème de Fermat

12 oct. 2016 Inverse modulaire de a dans Zn : entier b = a-1 tel que a × b = 1 mod n. Z. * n = l'ensemble des éléments inversibles modulo n. Attention !



CHAPITRE 3 : CONGRUENCES ET ARITHMÉTIQUE MODULAIRE

Théorème 1.3. Soient n et a entiers avec n ? 1. Alors a est congru modulo n à exactement un des nombres 01



Propriétés de Z/nZ

Si x est un entier on appelle classe d'équivalence de x modulo n On dit que a ? Z/nZ est inversible s'il existe b ? Z/nZ





Cryptographie

Soit n ? 2 un entier fixé. Définition 1. On dit que a est congru à b modulo n si n divise b ? a. On note alors a ? b (mod n). Pour nous n = 26.



Congruences et théorème chinois des restes

On définit l'addition et la multiplication modulo n de la ma- nière suivante : Le nombre d'éléments ayant un inverse modulo n est noté. ?(n).



[PDF] Inverser un nombre modulo n

On cherche à trouver l'inverse de a modulo n s'il existe On sait que a est inversible modulo n (c'est-à-dire dans l'anneau Z/nZ) si et seulement si 



[PDF] Rappel darithmétique : Anneaux modulo N - CNU 27 Marseille

En appliquant le modulo N cette équation on obtient les entiers Ue ? 1 (mod N) Donc selon la definition de l'inverse modulo N l'entier U est l'inverse de e 



Inverse modulo n [PGCD et nombres premiers]

On dit qu'un entier relatif admet un inverse modulo n ( n ? N n ? 2 ) lorsqu'il existe un entier relatif b tel que a b ? 1 [ n ]



Déterminer un inverse modulo n [PGCD et nombres premiers]

Il y a plusieurs façons de procéder : on peut soit tester toutes les possibilités (16 au total) de nombres b pour que 5 b ? 1 [ 16 ] ce qui va assez vite 



[PDF] chapitre 3 : congruences et arithmétique modulaire

Par la division euclidienne on peut écrire a = qn + r avec q r entiers et 0 ? r ? n ? 1 Et a ? r (mod n) car leur différence est qn Donc a est congru à 



[PDF] Inverse modulo n – Fonction indicatrice dEuler

Inverse modulo n – Fonction indicatrice d'Euler Exercice 1 – Déterminer les éléments inversibles dans Z/14Z et calculer les inverses Exercice 2 –



[PDF] Petit théorème de Fermat - DI ENS

12 oct 2016 · Inverse modulaire de a dans Zn : entier b = a-1 tel que a × b = 1 mod n Z * n = l'ensemble des éléments inversibles modulo n Attention !



(PDF) Rappel d arithmétique : Anneaux modulo N - Academiaedu

Download Free PDF Nombres: éléments de mathématiques pour philosophes Calcul de l'inverse (mod N ) 2 2 1 Calcul de l'inverse modulaire avec Euclide 



[PDF] Cours dintroduction `a larithmétique - Igor Kortchemski

L'entier u est appelé inverse de a modulo p et on note û = â?1 Exemple 5 Pour p = 7 2 est inverse de 4 3 est inverse de 5 et 6 est son propre inverse



[PDF] Devoir à la maison - IREM Clermont-Ferrand

On a donc 125 × 91 ? 1 mod 242 L'inverse de 125 modulo 242 est 91 Exercice 2 (3 points) 1 Montrez que pour tout entier naturel n 12n + 1 et 30n + 2 

  • Comment trouver l'inverse d'un nombre modulo n ?

    Le nombre x poss? un inverse modulo n si et seulement si (x,n)=1. Or, par le théorème de Bézout, de tels y et k existent si et seulement si 1 est divisible par (x,n). Autrement dit, on doit avoir (x,n)=1 ce qui signifie que x poss? un inverse si et seulement si il est premier avec n.
  • Qu'est-ce qu'un inversé modulo n ?

    Définition : On dit qu'un entier relatif admet un inverse modulo ( n ? N , n ? 2 ) lorsqu'il existe un entier relatif tel que a b ? 1 [ n ] . On dit aussi que est inversible modulo .
  • Quel est l'inverse d'un modulo ?

    L'inverse modulaire de A mod C est la valeur de B qui fait que A * B mod C = 1 .
  • l'inverse de 15 modulo 26 est 7 (et l'inverse de 7 modulo 26 est 15 ).

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_dbs11.pdfusesText_17
[PDF] inverseur bain-douche - Anciens Et Réunions

[PDF] Inverseur hydraulique sous charge avec commande par levier sous

[PDF] Inverseurs de sources Compact, Interpact et - Composants Electroniques

[PDF] INVERSEURS miniatures, à leviers POUSSOIR DE SECURITE

[PDF] Inversibilité de 1 ? ba en fonction de celle de 1 ? ab.

[PDF] Inversion

[PDF] Inversion de l`ammoniac - France

[PDF] Inversion du sens de rotation

[PDF] Invert-A-Cap – CF - Des Gants

[PDF] invertaire cassette video

[PDF] INVERTÉBRÉS DU PARC NATUREL RÉGIONAL DE CORSE· DES

[PDF] Invertec 300TPX 400TPX - Conception

[PDF] Invertec V205-S - Le Style Et La Mode

[PDF] Invertec v350-pro - Lincoln Electric - Conception

[PDF] INVERTER 2500 I2