Introduction a la Cryptologie Chapitre Le theoreme des restes chinois

Michael Eisermann

Description

Niveau: Supérieur, Master
Introduction a la Cryptologie Chapitre 5 : Le theoreme des restes chinois Michael Eisermann (Institut Fourier, UJF Grenoble) Annee 2008-2009 IF / IMAG, Master 1, S1-S2 document mis a jour le 7 juillet 2009FOURIERINSTITUTfi www-fourier.ujf-grenoble.fr/~eiserm/cours _ crypto

• theoreme des restes


• fourierinstitutfi www-fourier


• ?m des elements inversibles modulo


• developpement mathematique


• theoreme


• inverse dans z

Sujets

• Théorème

Informations

• Publié par: profil-infoe-2012
• Nombre de lectures: 93
• Langue: Français

Extrait

Introduction a` la Cryptologie
Chapitre 5 : Le theor´ eme` des restes chinois
Michael Eisermann (Institut Fourier, UJF Grenoble)
Annee´ 2008-2009
IF / IMAG, Master 1, S1-S2
document mis a` jour le 7 juillet 2009
INSTITUTi f FOURIER
www-fourier.ujf-grenoble.fr/~eiserm/cours#cryptoDev´ eloppement algorithmique :
Calculer efficacement l’inverse dansZ= .m
Appliquer efficacement les bijections dans le theor´ eme` chinois.
Objectifs de ce chapitre
Dev´ eloppement mathematique´ :
´Etudier les el´ ements´ inversibles dansZ= .m
´ Etablir le theor´ eme` chinois :Z= Z= Z= si pgcd(m;n) = 1.mn = m nObjectifs de ce chapitre
Dev´ eloppement mathematique´ :
´Etudier les el´ ements´ inversibles dansZ= .m
´ Etablir le theor´ eme` chinois :Z= Z= Z= si pgcd(m;n) = 1.mn = m n
Dev´ eloppement algorithmique :
Calculer efficacement l’inverse dansZ= .m
Appliquer les bijections dans le theor´ eme` chinois.Sommaire

1 Le groupeZ= des el´ ements´ inversibles modulomm
´ `2 Le theoreme chinois :Z= =Z= Z= si pgcd(m;n) = 1mn m nSommaire

1 Le groupeZ= des el´ ements´ inversibles modulomm
´Elements´ inversibles dansZ=m
Calcul de l’inverse dansZ=m
nLes cas particuliersZ= etZ=p p
2 Le theor´ eme` chinois :Z= =Z= Z= si pgcd(m;n) = 1mn m n1´Dans ce casy est unique et on l’appelle l’inverse dex, notex .
On definit´ Z= =Z= rf0g et Z= :=fx2Z= jx est inversibleg.m mm m
Remarque
L’el´ ement´ 1 est inversible dansZ= , car 1 1 = 1.m
De memeˆ 1 est inversible, car ( 1) ( 1) = 1.
Exemple
DansZ= l’el´ ement´ 3 est inversible car 3 7 = 1.10
L’el´ ement´ 2, par contre, n’est pas inversible. (Pourquoi ?)
Exercice
Expliciter les el´ ements´ inversibles dansZ= et leur inverse.8
´Elements´ inversibles dansZ=m
Definition´
Un el´ ement´ x2Z= est inversible s’il existey2Z= tel quexy = 1.m m On definit´ Z= =Z= rf0g et Z= :=fx2Z= jx est inversibleg.m mm m
Remarque
L’el´ ement´ 1 est inversible dansZ= , car 1 1 = 1.m
De memeˆ 1 est inversible, car ( 1) ( 1) = 1.
Exemple
DansZ= l’el´ ement´ 3 est inversible car 3 7 = 1.10
L’el´ ement´ 2, par contre, n’est pas inversible. (Pourquoi ?)
Exercice
Expliciter les el´ ements´ inversibles dansZ= et leur inverse.8
´Elements´ inversibles dansZ=m
Definition´
Un el´ ement´ x2Z= est inversible s’il existey2Z= tel quexy = 1.m m
1´Dans ce casy est unique et on l’appelle l’inverse dex, notex .Remarque
L’el´ ement´ 1 est inversible dansZ= , car 1 1 = 1.m
De memeˆ 1 est inversible, car ( 1) ( 1) = 1.
Exemple
DansZ= l’el´ ement´ 3 est inversible car 3 7 = 1.10
L’el´ ement´ 2, par contre, n’est pas inversible. (Pourquoi ?)
Exercice
Expliciter les el´ ements´ inversibles dansZ= et leur inverse.8
´Elements´ inversibles dansZ=m
Definition´
Un el´ ement´ x2Z= est inversible s’il existey2Z= tel quexy = 1.m m
1´Dans ce casy est unique et on l’appelle l’inverse dex, notex .
On definit´ Z= =Z= rf0g et Z= :=fx2Z= jx est inversibleg.m mm m De memeˆ 1 est inversible, car ( 1) ( 1) = 1.
Exemple
DansZ= l’el´ ement´ 3 est inversible car 3 7 = 1.10
L’el´ ement´ 2, par contre, n’est pas inversible. (Pourquoi ?)
Exercice
Expliciter les el´ ements´ inversibles dansZ= et leur inverse.8
´Elements´ inversibles dansZ=m
Definition´
Un el´ ement´ x2Z= est inversible s’il existey2Z= tel quexy = 1.m m
1´Dans ce casy est unique et on l’appelle l’inverse dex, notex .
On definit´ Z= =Z= rf0g et Z= :=fx2Z= jx est inversibleg.m mm m
Remarque
L’el´ ement´ 1 est inversible dansZ= , car 1 1 = 1.mExemple
DansZ= l’el´ ement´ 3 est inversible car 3 7 = 1.10
L’el´ ement´ 2, par contre, n’est pas inversible. (Pourquoi ?)
Exercice
Expliciter les el´ ements´ inversibles dansZ= et leur inverse.8
´Elements´ inversibles dansZ=m
Definition´
Un el´ ement´ x2Z= est inversible s’il existey2Z= tel quexy = 1.m m
1´Dans ce casy est unique et on l’appelle l’inverse dex, notex .
On definit´ Z= =Z= rf0g et Z= :=fx2Z= jx est inversibleg.m mm m
Remarque
L’el´ ement´ 1 est inversible dansZ= , car 1 1 = 1.m
De memeˆ 1 est inversible, car ( 1) ( 1) = 1.