Mathématiques pour la cryptographie

Mathématiques pour la cryptographie

Groupes

Groupes et Sous-groupes

Groupes Définition

. Soit G un ensemble non-vide. On appelle loi de composition interne dans G, ou opération interne dans G, toute application ? : G × G −→ G. (x, y) −→ x ∗ y Une telle loi de composition interne permet donc d’associer à tout couple (x, y) d’élément de G un autre éléments de G, noté x ? y, et appelé le produit de x par y pour la loi ?. Exemple 1.1.2. Sur G = Z, l’addition définie par Z × Z −→ Z (x, y) −→ x + y , la multiplication 4 Mathématiques pour la cryptographie 1.1 Groupes 5 Z × Z −→ Z (x, y) −→ x ? y et la soustraction Z × Z −→ Z (x, y) −→ x − y sont des lois de composition internes. Ce n’est pas le cas de la division car a/b n’est pas défini pour tous les couples (a, b) d’entiers.

Définition 1.1.3. On appelle groupe tout ensemble non-vide G muni d’une loi de composition interne ?, vérifiant les 3 propriétés suivantes (appelées axiomes de la structure de groupe) : (A1) la loi ? est associative dans G ; rappelons que cela signifie que x ? (y ? z) = (x ? y) ? z pour tous x, y, z ∈ G. (A2) la loi ? admet un élément neutre dans G ; rappelons que cela signifie qu’il existe e ∈ G tel que x ? e = e ? x = x pour tout x ∈ G. (A3) tout élément de G admet un symétrique dans G pour la loi ? ; rappelons que cela signifie que, pour tout x ∈ G, il existe x 0 ∈ G tel que x?x0 = x 0?x = e [2].

Définition 1.1.4. On appelle groupe commutatif, ou groupe abélien, tout groupe G dont la loi ? vérifie de plus la condition supplémentaire de commutativité : x ? y = y ? x pour tous x, y ∈ G Exemple 1.1.5. 1. Pour tout ensemble X, l’ensemble S(X) des bijectives de X dans X muni de la loi ◦ de composition est un groupe, appelé groupe symétrique sur X. (i) La loi ◦ est associative dans S(X) car : f ◦ (g ◦ h) = f ◦ g ◦ (h) = (f ◦ g) ◦ h pour toute f, g, h ∈ S(X) (ii) Le neutre en est l’identité de X,car f ◦ idX = idX ◦ f = f pour toute f ∈ S(X) (iii) Pour toutef ∈ S(X), le symétrique de f pour la loi ◦ est la bijection réciproque f −1 , car f f ◦ f −1 = f −1 ◦ f = idX . 2. L’ensemble C des nombres complexes muni de l’addition est un groupe abélien. (i) La l’addition est associative dans C ; (ii) Le neutre en est le nombre complexe nul 0 ,car z + 0 = 0 + z = z pour toute z ∈ C ; (iii) Pour tout z ∈ C, le symétrique de z pour l’addition est son opposé −z, car z + (−z) = (−z) + z = 0

Sous-groupes

Définition 1.1.6. Soit G un groupe muni d’une loi de composition interne ? et soit H un sous- ensemble non-vide de G. On dit que H est un sous-groupe de G lorsque les deux conditions suivantes sont vérifiées : 1. H est stable pour la loi ? (ce qui signifie x.y ∈ H pour tous x, y ∈ H), 2. H est stable par passage à l’inverse (ce qui signifie x −1 ∈ Hpour tout x ∈ H). Exemple 1.1.7. 1. Z, Q, R sont des sous-groupes du groupe C muni de l’addition, mais pas N (car l’opposé d’un élément de N n’est pas nécessairement un élément de N). 2. G et ({1}, ·) sont des sous-groupes de G appelés sous-groupes triviaux de G. Proposition 1. Soit G un groupe. Un sous-ensemble H de G est un sous-groupe de G si et seulement si les deux conditions suivantes sont vérifiées : (i) L’ensemble H n’est pas vide. (ii) Pour tous a et b de H, le produit ab−1 est aussi dans H. Définition 1.1.8. Un groupe fini est un groupe constitué d’un nombre fini d’éléments