Cryptographie, préliminaires mathématiques
Par Matt • 9 Décembre 2017 • 4 310 Mots (18 Pages) • 422 Vues
...
[pic 16]
Exercice : Supposons que pgcd(a; b) = d. Soient u0; v0 2 Z tels que au0 + bv0 = d. Montrer que les autres solutions (u; v) 2 Z2 telles que au + bv = d sont u = u0 + kb et v = v0 ka; k 2 Z.
Maple ! igcdex(a; b; u; v) (integer great common divisor extended)
[pic 17][pic 18][pic 19][pic 20][pic 21]
3. Congruences modulo n
[pic 22]
Soit n 2 N un entier positif xe. On de nit la relation R dans Z par :
8 (a; b) 2 Z2 a R b , 9 k 2 Z j a b = k n
Autrement dit, a et b sont en relation si et seulement si leur di erence est un multiple de n.
On peut veri er que R est une relation d'equivalence (re exive, symetrique, transitive) compatible avec l'addition, la soustraction et la multiplication.
On ecrira a b [n] au lieu de a R b.
Regle 1 : 8 (a; b; c; d) 2 Z2 a b [n] et c d [n] =) a c b + d [n] et a c b d [n]. On peut montrer que a b [n] () a mod n = b mod n.
[pic 23]
Regle 2 : a et b sont congrus modulo n si et seulement s'ils ont le m^eme reste dans leur division par n.
[pic 24]
3
---------------------------------------------------------------
Cryptographie Ann. Univ. 2016-17
[pic 25]
Exemple 5 : 35 0 [7], 48 1 [7]. Si a est pair alors a 0 [2] sinon a 1 [2].
[pic 26]
Maple ! a mod b ou irem(a; b) (integer remainder).
[pic 27][pic 28][pic 29][pic 30][pic 31]
4. L'anneau (nZZ; +; :)
[pic 32][pic 33]
Soit n 2 N et a 2 f0; 1; 2; 3; : : : ; n 1g . On designe par a la classe des elements congrus a a modulo n. La classe a est toujours in nie. On pose aussi nZZ = f0; 1; 2; 3; : : : ; n 1g. On de nit deux lois de composition internes dans nZZ. L'addition par :
a + b = a + b et la multiplication par : a:b = a:b.[pic 34][pic 35][pic 36][pic 37][pic 38][pic 39][pic 40][pic 41][pic 42][pic 43][pic 44][pic 45][pic 46]
(nZZ; +; :) admet alors une structure d'anneau commutatif unitaire.[pic 47][pic 48]
[pic 49]
Exemple 6 : Supposons que n = 6. Nous avons 6 classes :
[pic 50][pic 51][pic 52]
0 = f: : : ; 18; 12; 6; 0; 6; 12; 18; : : :g, 1 = f: : : ; 17; 11; 5; 1; 7; 13; 19; : : :g
[pic 53][pic 54]
2 = f: : : ; 16; 10; 4; 2; 8; 14; 20; : : :g, 3 = f: : : ; 15; 9; 3; 3; 9; 15; 21; : : :g
[pic 55][pic 56]
4 = f: : : ; 14; 8; 2; 4; 10; 16; 22; : : :g, 5 = f: : : ; 13; 7; 1; 5; 11; 17; : : :g
Z = f0; 1; 2; 3; 4; 5g 6 Z
[pic 57][pic 58][pic 59][pic 60][pic 61][pic 62][pic 63]
Voici les tables d'addition et de multiplication de l'anneau (6ZZ; +; :) :
[pic 64]
+
0
1
2
3
4
5
0
0
1
2
3
4
5
1
1
2
3
4
5
0
2
2
3
4
5
0
1
3
3
4
5
0
1
2
4
4
5
0
1
2
3
5
5
0
1
2
3
4
---------------------------------------------------------------
.
0
1
2
3
4
5
0
0
0
0
0
...