Introduction a la Cryptologie Chapitre Arithmetique modulaire

Michael Eisermann

Description

Niveau: Supérieur, Master
Introduction a la Cryptologie Chapitre 4 : Arithmetique modulaire 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

• entiers pairs


• fourierinstitutfi www-fourier


• developper des algorithmes efficaces pour le calcul dans z


• calcul dans z modulo


• developpement mathematique


• impairs entiers modulo


• anneaux z

Informations

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

Extrait

Introduction a` la Cryptologie
Chapitre 4 : Arithmetique´ modulaire
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 :
Dev´ elopper des algorithmes efficaces pour le calcul dansZ=m
Puissance modulaire rapide (« puissance dichotomique»)
Objectifs de ce chapitre
Dev´ eloppement mathematique´ :
Comprendre le calcul dansZ modulo un entierm
Construire l’anneau quotientZ= des entiers modulommObjectifs de ce chapitre
Dev´ eloppement mathematique´ :
Comprendre le calcul dansZ modulo un entierm
Construire l’anneau quotientZ= des entiers modulomm
Dev´ eloppement algorithmique :
Dev´ elopper des algorithmes efficaces pour le calcul dansZ=m
Puissance modulaire rapide (« puissance dichotomique»)Sommaire
1 Premiers exemples
2 L’anneauZ= des entiers modulomm
3 Puissance modulaire rapideSommaire
1 Premiers exemples
Entiers pairs et impairs modulo 3
Processeurs binaires
2 L’anneauZ= des entiers modulomm
3 Puissance modulaire rapideLes tables suivantes resument´ les regles` comme« pair plus impair = impair»
ou« pair fois impair = pair» :
+ 0 1 0 1
0 0 1 0 0 0
1 1 0 1 0 1
Entiers pairs et impairs
Les nombres entiers se repar´ tissent en entiers pairs et entiers impairs :
0 :=fa2Zja rem 2 = 0g
1 :=fa2Zja rem 2 = 1g + 0 1 0 1
0 0 1 0 0 0
1 1 0 1 0 1
Entiers pairs et impairs
Les nombres entiers se repar´ tissent en entiers pairs et entiers impairs :
0 :=fa2Zja rem 2 = 0g
1 :=fa2Zja rem 2 = 1g
Les tables suivantes resument´ les regles` comme« pair plus impair = impair»
ou« pair fois impair = pair» : 0 1
0 0 0
1 0 1
Entiers pairs et impairs
Les nombres entiers se repar´ tissent en entiers pairs et entiers impairs :
0 :=fa2Zja rem 2 = 0g
1 :=fa2Zja rem 2 = 1g
Les tables suivantes resument´ les regles` comme« pair plus impair = impair»
ou« pair fois impair = pair» :
+ 0 1
0 0 1
1 1 0Entiers pairs et impairs
Les nombres entiers se repar´ tissent en entiers pairs et entiers impairs :
0 :=fa2Zja rem 2 = 0g
1 :=fa2Zja rem 2 = 1g
Les tables suivantes resument´ les regles` comme« pair plus impair = impair»
ou« pair fois impair = pair» :
+ 0 1 0 1
0 0 1 0 0 0
1 1 0 1 0 1Ici les nombres entiers se repar´ tissent en trois classes :
0 :=fa2Zja rem 3 = 0g
1 :=fa2Zja rem 3 = 1g
2 :=fa2Zja rem 3 = 2g
´ `Les tables suivantes resument les regles de calculs que l’on observe sur les
restes modulo 3 :
+ 0 1 2 0 1 2
0 0 1 2 0 0 0 0
1 1 2 0 1 0 1 2
2 2 0 1 2 0 2 1
L’objectif de ce chapitre et de gen´ er´ aliser cette construction dem = 2 et
m = 3 a` toutm2Z puis d’analyser assez finement la structure qui en resulte´ .
Entiers modulo 3
Gen´ er´ alisons cette idee´ des entiers pairs et entiers impairs,
et regardons maintenant le reste modulo 3 au lieu de 2.