Arithmétique et Cryptographie

Chapitre 2: Ensembles et Applications

Dr Mamadou Ibrahima KONÉ

UP Mathématiques
ESATIC

17 septembre 2025

Dr Mamadou Ibrahima KONÉ (UP Mathématiques ESATIC) Arithmétique et Cryptographie 17 septembre 2025 1 / 17
 Plan du cours
1 Introduction au Chapitre
2 Ensembles
Ensembles : Dénition et Opérations
Ensembles : Règles de calculs et Produit Cartésien
3 Applications
Applications : Dénitions et Graphe
Applications : Images et Antécédents
4 Injection, Surjection, Bijection
5 Ensembles Finis
Ensembles Finis : Cardinal et Propriétés
6 Relation d'équivalence

Dr Mamadou Ibrahima KONÉ (UP Mathématiques ESATIC) Arithmétique et Cryptographie 17 septembre 2025 2 / 17
 Introduction et Contexte

Ce chapitre est fondamental pour la compréhension approfondie de l'arithmétique et de la

cryptographie.
Il jette les bases d'un langage mathématique rigoureux nécessaire pour conceptualiser
les algorithmes cryptographiques.
Nous allons aborder les notions d'ensembles, d'applications, et leurs propriétés essentielles
qui sont omniprésentes en informatique et en cryptographie.

Dr Mamadou Ibrahima KONÉ (UP Mathématiques ESATIC) Arithmétique et Cryptographie 17 septembre 2025 3 / 17
 Ensembles : Dénition et Opérations

1. Dénir des ensembles

Dénition informelle : Une collection d'éléments.
Exemples : {0, 1}, {rouge, noir}, N.
Ensemble vide (∅).
Notation d'appartenance : x ∈ E , x ∈/ E .
Dénition par propriété : Une collection d'éléments qui vérient une propriété.
exemple : {x ∈ R | |x − 2| < 1}.

Dr Mamadou Ibrahima KONÉ (UP Mathématiques ESATIC) Arithmétique et Cryptographie 17 septembre 2025 4 / 17
 Ensembles : Dénition et Opérations
2. Inclusion, union, intersection, complémentaire
Inclusion : E ⊂ F (tout élément de E est aussi dans F ). (∀x ∈ E , (x ∈ F )). On dit alors
que E est un sous-ensemble de F ou une partie de F
Égalité : E = F ⇐⇒ E ⊂ F et F ⊂ E .
Ensemble des parties : On note P(E ) l'ensemble des parties de E.
Complémentaire : Si A ⊂ E ,
{E A = {x ∈ E |x ∈
/ E}
On le note aussi E \ A.
Union : Pour A, B ⊂ E ,
A ∪ B = {x ∈ E |x ∈ A ou x ∈ B }
(le "ou" n'est pas exclusif).
Intersection :
A ∩ B = {x ∈ E |x ∈ A et x ∈ B }
.
Dr Mamadou Ibrahima KONÉ (UP Mathématiques ESATIC) Arithmétique et Cryptographie 17 septembre 2025 5 / 17
 Ensembles : Règles de calculs et Produit Cartésien

3. Règles de calculs Soient A, B , C des parties d'un ensemble E .

Commutativité : A ∩ B = B ∩ A, A ∪ B = B ∪ A.
Associativité : (A ∩ B ) ∩ C = A ∩ (B ∩ C ), (A ∪ B ) ∪ C = A ∪ (B ∪ C ).
Neutres et idempotence : A ∩ ∅ = ∅, A ∪ ∅ = A, A ∩ A = A, A ∪ A = A.
Distributivité : A ∩ (B ∪ C ) = (A ∩ B ) ∪ (A ∩ C ), A ∪ (B ∩ C ) = (A ∪ B ) ∩ (A ∪ C ).
Lois de De Morgan : {(A ∩ B ) = {A ∪ {B , {(A ∪ B ) = {A ∩ {B .
{({(A)) = A et donc A ⊂ B équivaut {(B ) ⊂ {(A)
4. Produit cartésien
Dénition : E × F = {(x , y ) | x ∈ E , y ∈ F }.
Exemples fondamentaux : R2 , intervalles (e.g., ×R).

Dr Mamadou Ibrahima KONÉ (UP Mathématiques ESATIC) Arithmétique et Cryptographie 17 septembre 2025 6 / 17
 Applications : Dénitions et Graphe

1. Dénitions
Une Application/Fonction : f : E → F , c'est la donnée pour chaque x ∈ E , d'un unique
élément f (x ) ∈ F .
Représentations : graphe cartésien.
Égalité d'applications : f , g : E → F , f = g ⇐⇒ ∀x ∈ E , f (x ) = g (x ).
Graphe d'une application : Γf = {(x , f (x )) ∈ E × F | x ∈ E }.
2. Composition d'applications
Dénition : g ◦ f : E → G , (g ◦ f )(x ) = g (f (x )).
Exemple : f (x ) = 1/x , g (x ) = (x − 1)/(x + 1) =⇒ g ◦ f (x ) = (1 − x )/(1 + x ).
Identité : idE : E → E , x 7→ x .

Dr Mamadou Ibrahima KONÉ (UP Mathématiques ESATIC) Arithmétique et Cryptographie 17 septembre 2025 7 / 17
 Applications : Images et Antécédents

3. Image directe et image réciproque Soient E , F deux ensembles.

Image directe de A ⊂ E : f (A) = {f (x ) | x ∈ A}.
Image réciproque de B ⊂ F : f −1 (B ) = {x ∈ E | f (x ) ∈ B }.
Remarques importantes :
f (A) est un sous-ensemble de F , f −1 (B ) est un sous-ensemble de E .
La notation f (B ) existe toujours, même si f n'est pas bijective.
−1

Image directe d'un singleton f ({x }) = {f (x )}. Image réciproque d'un singleton f ({y })
−1

peut être vide, un singleton, ou multiple.

4. Antécédents
Dénition : Fixons y ∈ F . Tout x ∈ E tel que f (x ) = y est un antécédent de y .
L'ensemble des antécédents de y est f −1 ({y }).

Dr Mamadou Ibrahima KONÉ (UP Mathématiques ESATIC) Arithmétique et Cryptographie 17 septembre 2025 8 / 17
 Injection, Surjection

1. Injection
Dénition : f est injective si ∀x , x 0 ∈ E , (f (x ) = f (x 0 ) =⇒ x = x 0 ).
Reformulation : Tout élément de F a au plus un antécédent.
2. Surjection
Dénition : f est surjective si ∀y ∈ F , ∃x ∈ E , y = f (x ).
Reformulation : Tout élément de F a au moins un antécédent, ou f (E ) = F .

Dr Mamadou Ibrahima KONÉ (UP Mathématiques ESATIC) Arithmétique et Cryptographie 17 septembre 2025 9 / 17
 Bijection et Propriétés
3. Bijection
Dénition : f est bijective si elle est à la fois injective et surjective.
Équivalence : Tout élément de F a un unique antécédent (∃!x ). Autrement dit :
∀y ∈ F ∃!x ∈ E (y = f (x )

L'existence du x vient de la surjectivité

4. Bijection réciproque
Proposition : : f : E → F est bijective ⇐⇒ il existe g : F → E telle que f ◦ g = idF et
g ◦ f = idE .
g est unique, bijective, et notée f −1 .
Exemple : exp(x ) et ln(y ).
5. Composition de bijections
Proposition : Si f , g sont bijectives, alors g ◦ f est bijective et (g ◦ f )−1 = f −1 ◦ g −1 .
Dr Mamadou Ibrahima KONÉ (UP Mathématiques ESATIC) Arithmétique et Cryptographie 17 septembre 2025 10 / 17
 Ensembles Finis : Cardinal et Propriétés
1. Cardinal
Dénition : Un ensemble E est ni s'il existe une bijection de E vers {1, ..., n}. n est le
cardinal (CardE ).
Exemples : ∅ (cardinal 0), N n'est pas ni.
2. Propriétés du cardinal
Si A est un ensemble ni et B ⊂ A, alors B est un ensemble ni et CardB ≤ CardA.
Si A, B sont des ensembles nis disjoints (A ∩ B = ∅), alors
Card(A ∪ B ) = CardA + CardB .
Si A est un ensemble ni et B ⊂ A alors Card(A \ B ) = CardA − CardB (si B ⊂ A).
Pour A, B deux ensembles nis quelconques :
Card(A ∪ B ) = CardA + CardB − Card(A ∩ B )
.
Dr Mamadou Ibrahima KONÉ (UP Mathématiques ESATIC) Arithmétique et Cryptographie 17 septembre 2025 11 / 17
 Ensembles Finis : Injection, surjection, bijection et ensembles
nis

3. Injection, surjection, bijection et ensembles nis

Proposition
Soient E et F deux ensembles nis et f : E → F une application.
Si f injective alors CardE ≤ CardF .
Si f surjective alors CardE ≥ CardF .
Si f bijective alors CardE = CardF .
Proposition :
Soit E , F deux ensembles nis et f : E → F
Si CardE = CardF , alors :
f est injective ⇐⇒ f est surjective ⇐⇒ f est bijective.

Dr Mamadou Ibrahima KONÉ (UP Mathématiques ESATIC) Arithmétique et Cryptographie 17 septembre 2025 12 / 17
 Ensembles Finis : Injection, surjection, bijection et ensembles
nis

Principe des tiroirs : Si l'on range dans k tiroirs, n > k paires de chaussettes alors il
existe (au moins) un tiroir contenant (au moins) deux paires de chaussettes.
4. Nombres d'applications
Soient E et F des ensembles nis, non vides. On note Card (E ) = n et Card (F ) = p .
Le nombre d'applications diérentes de E dans F : CardF CardE = p n .
Le nombre d'injections de E dans F : Ppn = p (p − 1) . . . (p − n + 1).
Le nombre de bijections de E dans E : n!.

Dr Mamadou Ibrahima KONÉ (UP Mathématiques ESATIC) Arithmétique et Cryptographie 17 septembre 2025 13 / 17
 Ensembles Finis : Sous-ensembles et Coecients Binomiaux
Soit E un ensemble ni de cardinal n.
5. Nombres de sous-ensembles
Nombre de sous-emnembles de E : 2CardE = 2n .
6. Coecients du binôme de Newton
Dénition : kn (nombre de parties à k éléments d'un ensemble à n éléments).

Propriétés : n0 = 1, n1 = n, nn = 1, n−n k = kn , nk =0 kn = 2n .





P

Formule de Pascal : kn = n−k 1 + kn− 1

−1 (construction du triangle de Pascal).

Formule factorielle : kn = k !(nn−! k )! .

7. Formule du binôme de Newton

(a + b)n = nk =0 kn an−k bk .
P

Exemples fondamentaux : (a + b)2 , (a + b)3 .

Dr Mamadou Ibrahima KONÉ (UP Mathématiques ESATIC) Arithmétique et Cryptographie 17 septembre 2025 14 / 17
 Relations d'Équivalence et Z/nZ

1. Dénition Une relation sur un ensemble E , c'est la donnée pour tout couple (x , y ) ∈ ExE
vrai s'ils sony en relation ou faux sinon.

2. Dénition
Une relation R sur E est une relation d'équivalence si elle est :
Réexive : ∀x ∈ E , xRx .
Symétrique : ∀x , y ∈ E , xRy =⇒ yRx .
Transitive : ∀x , y , z ∈ E , (xRy et yRz ) =⇒ xRz .
Exemples : "être parallèle", "être du même âge". Contre-exemples : "être
perpendiculaire", ≤.

Dr Mamadou Ibrahima KONÉ (UP Mathématiques ESATIC) Arithmétique et Cryptographie 17 septembre 2025 15 / 17
 Relations d'Équivalence et Z/nZ
Soit R une relation d'équivalence sur un ensemble E .
3. Classes d'équivalence
Dénition : Soit x ∈ E , la classe d'équivalence de x est
cl(x ) = {y ∈ E | yRx }
. cl (x ) est donc un sous-ensemble de E , on le note x . Si y ∈ x , on dit que y est un
représentant de x .
Propriétés :
cl(x ) = cl(y ) ⇐⇒ xRy . Les classes partitionnent E .
Pour tout x , y ∈ E , cl (x ) = cl (y ) ou cl (x ) ∩ cl (y ) = ∅
Soit C {cl (x )|x ∈ C } constitue une
un ensemble de représentants de toutes les classes alors

E.
partition de

Une partition de E est un ensemble (Ei ) de parties de E tels que E = ∪i Ei et Ei ∩ Ej = ∅,

si i 6= j
Dr Mamadou Ibrahima KONÉ (UP Mathématiques ESATIC) Arithmétique et Cryptographie 17 septembre 2025 16 / 17
 Z/nZ et Applications en Cryptographie
3. L'ensemble Z/nZ
Dénition : Soit n ≥ 2 un entier. Dénissons la relation suivante sur l'ensemble E = Z :
a≡b (mod n) ⇐⇒ a − b est un multiple de n
.
Preuve : C'est une relation d'équivalence.
Classes d'équivalence : ā = {a + kn | k ∈ Z}.
L'ensemble Z/nZ : {0̄, 1̄, . . . , n − 1} (n éléments).
Exemples quotidiens : L'heure (mod 24/12), jours de la semaine (mod 7).
4. Opérations dans Z/nZ (Rappel et approfondissement)
Addition : (ā + b̄) = a + b (mod n) .
Multiplication : (ā × b̄) = a × b (mod n).
Exemples : Critère de divisibilité par 9. Calcul rapide de puissances (e.g., 221 (mod 37)).
Dr Mamadou Ibrahima KONÉ (UP Mathématiques ESATIC) Arithmétique et Cryptographie 17 septembre 2025 17 / 17