L'arithmétique modulaire - Partie 1
#Bowie41#crypto#rsa
Note: au cours de ce wiki, je vais utiliser de nombreuses notations mathématiques, il n'est pas grave de ne pas les comprendre :)
L'arithmétique modulaire est une branche des mathématiques qui s'interesse aux entiers relatifs
L'ensemble des entiers relatifs est noté Z
Il contient tous les nombres entiers de −∞ à +∞
Par exemple :
- −42∈Z
- 67∈Z
- 5.3∈/Z
- π∈/Z
Note: "∈" veut dire "appartient à", on dit qu'un nombre appartient à un ensemble si on peut le trouver dans cet ensemble.
L'arithmétique modulaire s'interesse particulièrement à la divisibilité. On dit que "a divise b" si et seulement si il existe q entier tel que :
b=q⋅a
En notations mathématiques, on écrit :
a∣b⇔∃q∈Ztel queb=q⋅a
- 2 divise 42 car 42=12⋅2 -> On a donc bien q=12 et 12∈Z
- -11 divise 121 car 121=−11⋅−11 -> On a donc bien q=−11 et −11∈Z
- 5 ne divise pas 22 car il n'existe pas de q entier tel que 22=q⋅5
On note alors : 5∤22
L'arithmétique modulaire utilise souvent la division euclidienne.
-
La division euclidienne de 10 par 5 est:
10052
-
La division euclidienne de 20 par 3 est :
20236
-
La division euclidienne de 43 par -5 :
433−5−8
On dit alors que pour tout couple (a,b) de Z2 avec a=0 (on ne divise jamais par 0) il existe un couple (ou plusieurs) (q,r) de Z2 tel que :
b=q⋅a+r
Note: Z2 est l'ensemble des couples (x,y) avec x∈Z et y∈Z
Et en notations mathématiques :
∀(a,b)∈Z2,a=0,∃(q,r)∈Z2tel queb=q⋅a+r
-
Pour (a,b)=(5,10) on trouve (q,r)=(2,0) :
10052
on vérifie :
10=2⋅5+0
-
Pour (a,b)=(3,20) on trouve (q,r)=(6,2) :
20236
on vérifie :
20=6⋅3+2
-
Pour (a,b)=(−5,43) on trouve (q,r)=(−8,3) :
43−8−53
on vérifie :
43=−8⋅−5+3
Les congruences se conecntrent uniquement sur l'anayse du reste de la division euclidienne.
Pour tout 4-uplet (a,b,q,r)∈Z4 avec a=0 et b=q⋅a+r on note :
b≡r(moda)
En notations mathématiques :
∀(a,b,q,r)∈Z4,(a=0,b=q⋅a+r)⟹b≡r(moda)
- 10≡0(mod5) car 10=2⋅5+0
- 20≡2(mod3) car 20=6⋅3+2
- 43≡3(mod−5) car 43=−8⋅−5+3
-
La congruence est stable par addition :
six1≡y1(modn)etx2≡y2(modn)alorsx1+x2≡y1+y2(modn)
-
La congruence est stable par produit :
six1≡y1(modn)etx2≡y2(modn)alorsx1⋅x2≡y1⋅y2(modn)
-
La congruence est stable par passage a la puissance :
six1≡y1(modn)alorsx1k≡y1k(modn)pour tout k entier≥0
En notations mathématiques :
-
∀(x1,y1,x2,y2,n)∈Z5,(n=0,x1≡y1(modn),x2≡y2(modn))⇒x1+x2≡y1+y2(modn)
-
∀(x1,y1,x2,y2,n)∈Z5,(n=0,x1≡y1(modn),x2≡y2(modn))⇒x1⋅x2≡y1⋅y2(modn)
-
∀(x1,y1,n)∈Z3,(n=0,x1≡y1(modn))⇒∀k∈Nx1k≡y1k(modn)
Promis ça sera plus fun après mais faut bien commencer quelque part :3