République Algérienne Démocratique et Populaire

Ministère de l’Enseignement Superieur et de la Recherche Scientifique

Université Oran1-Es Senia
Faculté des sciences exactes et appliquées

Notes de cours
Outils Mathématiques pour la Cryptographie

Auteur : [Link]
Table des matières

0.1 La structure des groupes cycliques . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

0.1.1 Une autre définition de l’ordre d’un élément . . . . . . . . . . . . . . . . . . 2
0.2 Sous groupe monogène fini . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
0.2.1 Proposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
0.3 Produit de groupes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
0.4 Sous-groupe d’un groupe cyclique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
0.4.1 Proposition : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
0.4.2 Commutativité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
0.5 Théorème de Lagrange sur les groupes . . . . . . . . . . . . . . . . . . . . . . . . . 5
0.6 Théorème d’Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
0.7 Petit théorème de Fermat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1 Z/nZ, les nombres de la cryptographie 7

1.1 Congruence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1.1 Formulations équivalentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1.2 C’est une relation d’équivalence . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Addition et multiplication dans Z/nZ . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.1 Addition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.2 Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.3 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.4 Equation du 1er degré . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3 Inverse d’un élément dans Z/nZ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3.1 Théorème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3.2 Cas particulier : Z/pZ avec p premier . . . . . . . . . . . . . . . . . . . . . 9

1
Chapitre 1

Suite du chapitre précédent

1.1 La structure des groupes cycliques

Soit (G, .) un groupe (1 le neutre de (G, .)) et g un élément de G (g ∈ G). Considérons l’appli-
cation φ définie par :
φ : Z −→< g >
k −→ g k
• φ est un morphisme de groupe de (Z, +) dans (< g >, .)
∀k, l ∈ Z, φ(k + l) = g k+l = g k .g l = φ(k).φ(l)
• φ est surjectif par construction.
• φ injectif ? :
• Si oui : =⇒ φ est un isomorphisme et < g > ∼ = (isomorphe à) Z
• Si non : φ n’est pas injectif =⇒ Ker(φ) 6= ∅ =⇒ ∃k ∈ Z ∗ et g k = 1(g −k = 1 aussi).
Nous allons montrer dans ce cas que < g > ∼ = Z/nZ

1.1.1 Une autre définition de l’ordre d’un élément

Soit (G, .) un groupe et g ∈ G. Si ∃k ∈ Z ∗ et g k = 1, alors on dit que g est d’ordre fini et
l’entier n = min{k ∈ N ∗ et g k = 1} est appelé l’ordre de g (| < g > |).

1.2 Sous groupe monogène fini

1.2.1 Proposition
Soit (G, .) un groupe et g ∈ G un élément d’ordre n. Alors, on a :
< g >= {1, g, g 2 , ... , g n−1 } et card(< g >) = n (ou | < g > | = n).

Preuve : < g >=? {1, g, g 2 , ... , g n−1 }

1. {1, g, g 2 , ... , g n−1 } ⊂? < g >
Par construction (par définition) < g >= {....., g −2 , g −1 , 1, g, g 2 , ... , g n−1 , g n , ...} =⇒
{1, g, g 2 , ... , g n−1 } ⊂< g >
2. < g > ⊂? {1, g, g 2 , ... , g n−1 }
Réciproquement, soit x ∈< g >=⇒ ∃a ∈ Z tel que x = g a .
Effectuons la division de a par n : a = qn + r avec 0 ≤ r < n
x = g qn+r = (g n )q .g r = 1q .g r = g r ∈ {1, g, g 2 , ... , g n−1 } =⇒ x ∈ {1, g, g 2 , ... , g n−1 }
=⇒< g > ⊂ {1, g, g 2 , ... , g n−1 }
3. Il reste à montrer que : 1 6= g 6= g 2 6= ........ 6= g n−1 =⇒ card(< g >) = n
Soient a, b tels que g a = g b et 0 ≤ a ≤ b ≤ n − 1
g a .g −a = g a .g −a =⇒ g b−a = 1 avec 0 ≤ b − a < n
=⇒ b − a < n =⇒ b − a = 0 (car n est le plus petit k tel que g k = 1) =⇒ b = a

2
< g > est un groupe cyclique de cardinal n. il est isomorphe à Z/nZ :
¯ 1}
{1, g, g 2 , ... , g n−1 } ←→ {0̄, 1̄, ..., n −

1.3 Produit de groupes

soit g ∈ (G, .) d’ordre p et soit h ∈ (H, .) d’ordre q ((G, .) et (H, .) sont des groupes) :

∀k ∈ Z, g k = 1 ⇐⇒ k multiple de p
0 0 0
∀k ∈ Z, hk = 1 ⇐⇒ k multiple de q

Soit x = (g, h) ∈ G × H =⇒ x2 = (g 2 , h2 ), ..., xk = (g k , hk )

L’ordre de x c’est xk = (1, 1) ⇐⇒ k multiple de p et q.

L’ordre de x est le ppcm(p, q).

Conséquence :
Soient (G, .) et (H, .) deux groupes cycliques finis de cardinaux respectifs p et q. Si p et q sont
premiers entre eux alors G × H est cyclique.

Si p et q sont deux entiers premiers entre eux : Z/pZ × Z/qZ ∼

= Z/pqZ

justification :
N’importe quel groupe fini cyclique d’ordre p est isomorphe à Z/pZ.

(G, ×) ∼
= Z/pZ et (H, ×) ∼
= Z/qZ =⇒
(G × H, ×) ∼
= Z/pZ × Z/qZ
=⇒ (G × H, ×) ∼
= Z/pqZ
Et si p et q ne sont pas premiers entre eux ? −→ pas forcément

Contre exemple : Z/2Z × Z/2Z = {(0̄ , 0̄), (0̄ , 1̄), (1̄, 0̄), (1̄ , 1̄)}
< (0̄ , 0̄) >= {(0̄ , 0̄)}
< (0̄ , 1̄) >= {(0̄ , 1̄) , (0̄ , 0̄)}
< (1̄ , 1̄) >= {(1̄ , 0̄) , (0̄ , 0̄)}
< (1̄ , 1̄) >= {(1̄ , 1̄) , (0̄ , 0̄)}

Aucun élément de Z/2Z × Z/2Z ne génère ce dernier =⇒ Z/2Z × Z/2Z n’est pas cyclique.

1.4 Sous-groupe d’un groupe cyclique

1.4.1 Proposition :
Soit (G, .) un groupe cyclique. Tout sous-groupe de G est cyclique

Preuve :
∃g ∈ G tel que G =< g > et H un sous-groupe de G.
Si H 6= {1} le sous-groupe trivial ({eG }), ∃k > 0, et g k ∈ H,
soit m = min{k ∈ N ∗ , g k ∈ H}, Montrons que H =< g m > :

14 décembre 2025 3/ 9
[Link]
 1. < g m > ⊂? H
g m ∈ H =⇒< g m > ⊂ H,
Trivial, car < g m > est un sous ensemble dont les éléments sont obtenus par la composition
de g m avec lui même autant de fois qu’on veut. Cette composition reste dans H car ce
dernier est un sous-groupe.
2. Réciproquement, H ⊂? < g m >
Soit h ∈ H, ∃p ∈ Zeth = g p .
Effectuons la division euclidenne de p par m : ∃q, r tels que : p = qm + r avec 0 ≤ r < m
h = g qm+r = g qm .g r = (g m )q .g r
(g m )−q .h = g qm+r = (g m )−q (g m )q .g r = g r =⇒ g r = (g m )−q .h ∈ H
m étant le plus petit entier tel que g m ∈ H =⇒ r = 0
=⇒ h = (g m )q ∈ < g m >=⇒ H ⊂ < g m >

1.4.2 Commutativité
Proposition
Un groupe cyclique est commutatif.

preuve :
Soit (G, .) un groupe cyclique et g ∈ G un générateur de G.
∀x, y ∈ G, ∃a, b ∈ Z, x = g a et y = g b
x.y = g a .g b = g a+b = g b+a = g b .g a = y.x

14 décembre 2025 4/ 9
[Link]
1.5 Théorème de Lagrange sur les groupes
Soit (G, .) un groupe fini et H un sous groupe de G.
Le cardinal de H divise le cardinal de G.

Conséquences :
1. Les sous-groupes stricts non-triviaux de (Z/25Z, +) ont 5 éléments.
En effet, 25 n’est divisible que par 1, 5 et 25
2. Si le cardinal d’un groupe G est un nombre premier, alors les seuls sous-groupes de G sont
les sous-groupes triviaux {eG } et G.
(Z/13Z, +) n’admet comme sous groupe que {0̄} et Z/13Z

Preuve :
L’idée de la preuve consiste en la partition du groupe G en un ensemble {H, Hx1 , Hx2 , ..., Hxm−1 }
d’ensembles tous de même taille que H (|H| = |Hxi |, ∀i ∈ {1, 2, ..., m − 1}). avec :

• H ∪ Hx1 ∪ Hx2 ∪ ... ∪ Hxm−1 = G

• H ∩ Hxi = ∅, ∀i ∈ {1, 2, ..., m − 1} et Hxi ∩ Hxj = ∅, ∀i, j ∈ {1, 2, ..., m − 1}

On voit bien que : |G| = m.|H| par construction.

— Soit x ∈ G, x ∈
/ H ; Hx = {h.x, h ∈ H}
• Montrons que H ∩ Hx = ∅ :
Soit y = hx =⇒ y ∈ Hx avec h ∈ H
Si y ∈ H alors h−1 y = x ∈ H =⇒ contradiction. =⇒ Hx ∩ H = ∅
• Montrons que : card(Hx) = card(H), soit φ définie par :

φ : H −→ Hx
h −→ hx
• φ est surjective par construction
• φ est elle injective ?
h1 x = h2 x =⇒ h1 x.x−1 = h2 x.x−1 =⇒ h1 = h2 , oui φ est injective φ est bijective.
Nous avons trouvé une bijection entre H et Hx, ils ont alors, le même nombre d’élémnts.

— Soit y ∈ G, y ∈
/ H et y ∈
/ Hx
On sait déjà que H ∩ Hy = ∅, Montrons que Hx ∩ Hy = ∅ :
Supposons que z ∈ Hx et z ∈ Hy =⇒ ∃h1 , h2 ∈ H, z = h1 x et z = h2 y =⇒
h1 x = h2 y =⇒ h−1 −1
2 h1 x = h2 h2 y = y =⇒ y ∈ Hx =⇒ contradiction. =⇒ Hx ∩ Hy = ∅

— On réitère le processus jusqu’à épuisement de tous les éléments de G. Comme G est fini le
processus s’arrête après un nombre fini d’étapes et donc card(G) = m × card(H)

Proposition
Soit (G, .) un groupe fini de cardinal p ∈ N ∗ . Si p est un nombre premier, alors G est cyclique.

Preuve :
Soit x ∈ G, avec x 6= e.
Le sous-groupe < x > engendré par x n’est pas réduit à l’élément neutre. Le seul sous-groupe
possible restant est G.

14 décembre 2025 5/ 9
[Link]
Proposition
L’ordre de tout élément d’un groupe fini est un diviseur de l’ordre (du cardinal) du groupe.

Preuve :
conséquence du théorème de Lagrange : l’ordre d’un élément est le cardinal du sous groupe engendré
par cet élément qui est fini aussi.
En effet, soit (G, .) un groupe fini d’ordre n et g ∈ G d’ordre fini m = min{k ∈ N ∗ , g k = 1}.
m divise n car < g > est un sous groupe de G.

1.6 Théorème d’Euler

Soit (G, .) un groupe fini de cardinal n. Alors : ∀g ∈ G, g n = 1.

Preuve :
D’après la proposition précédente : | < g > | = m et m divise n =⇒
(g m = 1) et (∃k ∈ Z ∗ , n = k.m). Calculons g n :
g n = g km =⇒ g n = (g m )k = 1k = 1 =⇒ g n = 1

1.7 Petit théorème de Fermat

Si p est un nombre premier, si a est un entier non divisible par p alors,
ap−1 − 1 est un multiple de p

Exemples :
• a = 2 et p = 7 −→ 27−1 − 1 = 64 − 1 = 63 = 7 × 9
• a = 3 et p = 5 −→ 35−1 − 1 = 81 − 1 = 80 = 5 × 16
• a = 11 et p = 3 −→ 113−1 − 1 = 112 − 1 = 120 = 3 × 40

Preuve :
Considérons le groupe multiplicatif ((Z/pZ)× , ×), où (Z/pZ)× représente l’ensemble des inver-
sibles de (Z/pZ, +) − {0}.
Comme p est premier, les nombres {1̄, 2̄, ... , p −¯ 1} sont tous inversibles car ils sont tous premiers
avec p.
=⇒ (Z/pZ)× = {1̄, 2̄, ... , p − ¯ 1}}
¯ 1}}
Comme a n’est pas divisible par p, la classe de a = ā est dans {1̄, 2̄, ... , p −
l’ordre de ā = | < ā > | = m divise l’ordre de (Z/pZ)× = p − 1
=⇒T [Link] (ā)(p−1) = 1̄ =⇒ (ā)(p−1) − 1̄ = 0̄
Ceci est vrai quelquesoit l’élément de la classe de a, en particulier a lui même.

14 décembre 2025 6/ 9
[Link]
Chapitre 2

Z/nZ, les nombres de la

cryptographie

Dans ce chapitre, nous allons revoir l’ensemble Z/nZ sous un angle différent.

2.1 Congruence
Soit n ∈ N , n > 1. Soient a et b ∈ Z, on dit que a et b sont congrus modulo n lorsque a − b est
multiple de n. On note alors : a ≡ b [n].

2.1.1 Formulations équivalentes

a ≡ b [n] ⇐⇒ a et b ont le même reste dans la division par n ⇐⇒
∃k ∈ Z, a = b + kn.

2.1.2 C’est une relation d’équivalence

La relation de congruence est une relation d’équivalence sur Z.

Définition
Soit n ∈ N , n > 1. On note Z/nZ l’ensemble des classes d’équivalence de la relation de congruence
modulo n.
¯ 1}, où ā est l’ensemble des entiers congrus à a modulo n.
Z/nZ = {0̄, 1̄, 2̄, ..., n −

2.2 Addition et multiplication dans Z/nZ

2.2.1 Addition
¯ b
1. Dans Z/nZ, on peut définir une addition par : ā + b̄ = a +
2. si x̄ = ā et ȳ = b̄ alors x̄ + ȳ = ā + b̄
3. (Z/nZ, +) est un groupe commutatif.

2.2.2 Multiplication
1. Dans Z/nZ, on peut définir une multiplication par : ā × b̄ = a × ¯ b
2. ∀ā, b̄, c̄ ∈ Z/nZ, ā × (b̄ × c̄) = (ā × b̄) × c̄, la multiplication est associative.
3. ∀ā, b̄ ∈ Z/nZ, ā × b̄ = b̄ × ā, la multiplication est commutative.
4. ∀ā, b̄, c̄ ∈ Z/nZ, ā × (b̄ + c̄) = ā × b̄ + ā × c̄, la multiplication est distributive.
5. ∀ā ∈ Z/nZ, ā × 1̄ = ā, 1̄ est un élément neutre pour la multiplication.
6. (Z/nZ, +, ×) est un anneau commutatif.

7
2.2.3 Définitions
• Tous les éléments de Z/nZ ont un opposé mais pas forcément un inverse.
• Soit ā un élément de Z/nZ. On dit que ā est inversible ssi ∃b̄ ∈ Z/nZ tel que ā × b̄ = 1
• On appelle b̄ l’inverse de ā et on le note ā−1
• L’ensemble des éléments inversibles de Z/nZ est noté (Z/nZ)× .
• Soit ā un élément de Z/nZ. On dit que ā est un diviseur de zéro ssi :
• ā 6= 0
• ∃b̄ ∈ Z/nZ, b̄ 6= 0 et ā × b̄ = 0̄

2.2.4 Equation du 1er degré

Resoudre dans Z/20Z les équations suivantes :
1. 3̄x = 9̄ =⇒ 7̄ × 3̄x = 7̄ × 9̄ =⇒ 1̄ × x = 3̄ =⇒ x = 3̄
2. 3̄x = 4̄ =⇒ 7̄ × 3̄x = 7̄ × 4̄ =⇒ 1̄ × x = 8̄ =⇒ x = 8̄
3. 4̄x = 3̄ Il n’y a pas de solutions, car 4x = 3 + 20n =⇒ 4x − 20n = 3 =⇒ 4(x − 5n) = 3 =⇒
aucune paire d’entiers (x, n) ne vérifient cette équation (un nombre pair=un nombre impair)

4. 4̄x = 8̄ 4x = 8 + 20n =⇒ 4x − 20n = 8 =⇒ 4(x − 5n) = 8 =⇒ x = 2 + 5n =⇒

¯ 17}
Solutions : {2̄, 7̄, 12, ¯
Conclusion :
• Dans les deux premiers cas une solution unique car 3̄ est inversible dans Z/20Z
• Dans les deux cas suivants pas de solutions ou solution multiple car 4̄ n’est pas inversible
dans Z/20Z

2.3 Inverse d’un élément dans Z/nZ

Exercice :
Donner les éléments inversibles de Z/5Z et de Z/6Z (notés respectivement : (Z/5Z)× , (Z/6Z)× )

¯ sont toujours leurs

• Dans Z/nZ, 1̄ et −1 propres inverses.
• Dans Z/5Z, (Z/5Z)× = {1̄, 2̄, 3̄, 4̄}
• Dans Z/6Z,
X 0 1 2 3 4 5
0 0 0 0 0 0 0
1 0 1 2 3 4 5
2 0 2 4 0 2 4
3 0 3 0 3 0 3
4 0 4 2 0 4 2
5 0 5 4 3 2 1
Dans la table de multiplication, nous remarquons que seuls 1̄ et 5̄ sont inversibles et leurs
inverses sont eux même. (Z/6Z)× = {1̄, 5̄}

Astuce :
Un diviseur de zéro de Z/nZ ne peut pas être inversible.
Par exemple pour trouver (Z/30Z)× on élimine les diviseurs de zéro :
a, b 6= 0, ā × b̄ = 0̄, ie : a × b multiple de 30
(Z/30Z)× = {1̄, 7̄, 11, ¯ 13¯ 17,
¯ 19,
¯ 23,
¯ 29}
¯

14 décembre 2025 8/ 9
[Link]
2.3.1 Théorème
Soit ā un élément de Z/nZ,

ā est inversible ⇐⇒ a est premier avec n

Preuve :
La preuve repose sur le théorème de Bachet-Bézout :

a est premier avec n ⇐⇒ ∃s, t ∈ Z, as + nt = 1

⇐⇒ ∃s, t ∈ Z, as − 1 = nt
⇐⇒ ∃s ∈ Z, ās̄ − 1̄ = 0̄
⇐⇒ ∃s ∈ Z, ās̄ = 1̄
⇐⇒ ā est inversible

2.3.2 Cas particulier : Z/pZ avec p premier

Soit p ∈ N , un nombre premier.
∀a ∈ {1, 2, ...., p − 1}, a est premier avec p ; donc ā est inversible dans Z/pZ
(Z/pZ)× = Z/pZ − {0̄}

Exercice :
Calculons l’inverse de 37¯ dans Z/63Z.
Il s’agit de trouver une relation de Bachet-Bézout entre 37 et 63 (as+nt = 1, avec a = 37 et n = 63).
soit s = −17 et t = 10 =⇒ 37.(−17) + 63.10 = 1
On en déduit que dans Z/63Z on a : −17 ¯ × 37
¯ = 1̄
L’inverse de 37 ¯ est −17
¯ = 46¯

D’où vient la relation de Bézout ?

On applique l’algorithme d’Euclide à 63 et 37 (divisions euclidiennes succéssives).

1 = 10 × 63 − 17 × 37
63 = 1 × 37 + 26 1 = −7 × 37 + 10 × (63 − 1 × 37) = 10 × 63 − 17 × 37
37 = 1 × 26 + 11 1 = 3 × 26 − 7 × (37 − 1 × 26) = −7 × 37 + 10 × 26
26 = 2 × 11 + 4 1 = 3 × (26 − 2 × 11) − 1 × 11 = 3 × 26 − 7 × 11
11 = 2 × 4 + 3 1 = 4 − 1 × (11 − 2 × 4) = 3 × 4 − 1 × 11
4 = 1 × 3 + 1 =⇒ On remonte : 1 = 4 − 1 × 3

14 décembre 2025 9/ 9
[Link]