Introduction a la Cryptologie Chapitre Le theoreme des restes chinois

117

pages

Français

Documents

Écrit par
Michael Eisermann

Publié par
profil-infoe-2012

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

117

pages

Français

Ebook

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Publié par

profil-infoe-2012

Nombre de lectures

Langue

Français

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

Voir

Publié par

profil-infoe-2012

Nombre de lectures

Langue

Français

Théorème

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 efﬁcacement l’inverse dansZ= .m
Appliquer efﬁcacement 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 efﬁcacement 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 deﬁnit´ 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
Deﬁnition´
Un el´ ement´ x2Z= est inversible s’il existey2Z= tel quexy = 1.m m On deﬁnit´ 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
Deﬁnition´
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
Deﬁnition´
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 deﬁnit´ 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
Deﬁnition´
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 deﬁnit´ 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
Deﬁnition´
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 deﬁnit´ 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.