Introduction

Bases

Ensembles

Soient $A$ et $B$ deux ensembles finis. Si $|A|=|B|$, alors pour toute fonction de $A$ dans $B$, l’injectivité, la surjectivité et la bijectivité sont des propriétés équivalentes.

Structure Algébrique :

Un structure algébrique est une paire :

• $A$ : un ensemble
• $\ast$ : un opérateur sur $A$ , c'est à dire une fonction $\ast :A\times A\to A$.

(On peut avoir plusieurs opérateurs, ou des opérateurs notés différemment, ainsi que des relations sur $A$)

(On écrit généralement $\ast (a,b)$ en notation infixe : $a\ast b$)

Exemples :

1. $({\mathbb{R}}^{\ast },\times )$
2. $({\mathbb{C}}^{n\times n},+,\times )$
3. $(P[X],+,\times )$
4. $(S(A),\circ )$ : l’ensemble des permutations sur $A$ muni de la composition
5. $(P(A),\cap )$ : l’ensemble des sous-ensembles de $A$ muni de l’intersection
6. $(\{0,1{\}}^{\ast },\circ )$ : l’ensemble des chaînes de bits muni de la concaténation

Monoïdes :

Un monoïde est une structure $(A,\ast )$ telle que (rappel: comme un monoïde est une structure algébrique $\ast$ est une fonction $\ast :A\times A\to A$ et donc $x\ast y\in A$) :

• $\ast$ est associatif : $a\ast (b\ast c)=(a\ast b)\ast c=a\ast b\ast c$
• $\ast$ admet un neutre, noté $1_A$ ou $ϵ\in A$ tel que $ϵ\ast a=a\ast ϵ=a$ pour tout $\in A$

(On parle souvent du monoïde $A$, abrège $a\ast b$ en $ab$, et $1_A$ en $1$)

Exemples :

1. $(\mathbb{N},-)$ n'est pas un monoïde

2. $(A^A,\ast )$ : l’ensemble des transformations de A muni de la composition est un monoïde (La notation $A^A$ signifie l'ensemble de toutes les applications (ou fonctions) qui prennent un élément de $A$ comme entrée et renvoient un élément de $A$ comme sortie.)

Propriétés/Théorèmes :

1. Le neutre d'un monoïde est unique

   Preuve : Soient $ϵ,{ϵ}^{\prime }$ neutres pour ($A,\ast$). Alors : $$ϵ\ast {ϵ}^{\prime }={ϵ}^{\prime }\text{et}ϵ\ast {ϵ}^{\prime }=ϵ$$ ce qui implique $ϵ={ϵ}^{\prime }$

2. Si un élément d'un monoïde fini est un inverse à gauche il est également un inverse à droite du même élément. Autrement dit, si un élément possède un inverse à gauche, alors cet élément est inversible.

   Preuve :

   Soit $b$ un inverse à gauche de $a$ tel que $ba=1_A$ ($a$ est donc aussi l'inverse à droite de $b$), et l'application $f:A\to A:x\to ax$.

   Soient $x_1$ et $x_2$ deux éléments de $A$, leur images par $f$ sont $a{x}_1$ et $a{x}_2$ respectivement, si $a{x}_1=a{x}_2$ alors $b(a{x}_1)=b(a{x}_2)$ et comme on est dans un monoïde $(ba)x_1=(ba)x_2\iff x_1=x_2$, ce qui prouve que l'application est injective. Il faut bien piger que si $a$ n'avait pas d'inverse à gauche on aurait pas pu prouver l'injectivité. Comme l'application est injective et qu'on est dans un monoïde fini on en déduit qu'il existe une relation unique bidirectionnelle entre $x$ et $ax$ pour tout $x$. L'ensemble d'entrée est donc de même taille (et de même nature parce que l'opération est stable) que l'ensemble image. Ceci implique que l'idéntité se trouve dans l'ensemble image et donc qu'il existe un $c$ tel que $ac=1_A$ où $c$ est donc l'inverse à droite de $a$. Maintenant il suffit de multiplier à gauche par $b:$ $b(ac)=b$, encore une fois on applique l'associativité : $(ba)c=b$ et donc $c=b$. CQFD

Sous-Monoïdes :

Une structure $B\subseteq A$ est un sous-monoïde (qui est lui-même un monoïde) si :

• $\forall x,y\in B$ on a $x\ast y\in B$ (stabilité)
• $1_A\in B$

Inverses :

Soit $(A,\ast )$ un monoïde et $(a,b)\in A$. $a$ est l'inverse de $b$ si $a\ast b=b\ast a=ϵ$.

Propriétés/Théorèmes :

1. Si $b$ possède un inverse, alors cet inverse est unique. Preuve : Soient $a_1,a_2$ tel que $a_1\ast b=b\ast a_2=1_A$. Alors : $$a_1=a_1\ast 1_A=a_1\ast (b\ast a_2)=(a_1\ast b)\ast a_2=1_A\ast a_2=a_2$$

Groupes

Un groupe est un monoïde $(G,\ast )$ tel que :

• tous les éléments de $G$ possèdent un inverse par rapport à l'opérateur $\ast$. (La façon de trouver un inverse peut être unique à l'élément en question, il ne faut pas savoir trouver de forme générale pour l'inverse comme $1/a$ pour que tous les éléments soient inversibles)

Exemple(s) :

1. $(\mathbb{Z},+)$ est un groupe, mais pas $(\mathbb{N},+)$
2. $({\mathbb{R}}^{\ast },\times )$ et $({\mathbb{R}}^{>0},\times )$ sont des groupes
3. $S(A)$ est un groupe
4. $\mathbb{T}=\{e^{i\alpha }|\alpha \in \mathbb{R}\}$ muni de la multiplication est un groupe
5. L’ensemble des matrices orthogonales muni de la multiplication est un groupe
6. L’ensemble $A^A$ des transformations de $A$ muni de la composition n’est pas un groupe

Propriétés/Théorèmes :

1. L'ordre d'un groupe est le nombre d'éléments qu'il contient.

2. Si $a,b,c$ sont membres d'un groupe alors : $$ac=bc\text{ou}ca=cb\text{alors}a=b$$ (Note : $ab$ est une façon plus courte d'écrire $a\ast b$)

   Preuve : Soit $d=c^{-1}$. Alors : $$ac=bc\Rightarrow a=aϵ=acd=bcd=bϵ=b$$

3. Les inverses sont symétriques. Si $ab=ϵ$ alors $a=b^{-1}$ et $b=a^{-1}$

   Preuve : $$ab=ϵ\Rightarrow bab=b\Rightarrow bab{b}^{-1}=b{b}^{-1}\Rightarrow ba=ϵ$$

4. Si tous les éléments d'un monoïde possèdent un inverse à gauche, alors le monoïde est un groupe.

   Preuve :

   Soit $a$ un élément de $A$, $b$ son inverse à gauche et $c$ l'inverse à gauche de $b$. On commence avec $ba=1_A$ et on multiplie à gauche par $c$ : $c(ba)=c$ et on applique l'associativité : $c(ba)=c$ et donc $(cb)a=c$. On sait que $cb=1_A$ et donc $a=c$. Comme $a$ est inversible à gauche par définition et inversible à droite par son égalité à $c$ ($b$ est son inverse à droite), on a donc que $a$ est inversible et $A$ est un groupe.

Groupes commutatifs/abéliens

Un groupe $G$ est commutatif si :

• $a\ast b=b\ast a$ $\forall a,b\in G$

Exemple(s) :

Sous-Groupes

$H\subseteq G$ est un sous-groupe de $(G,\ast )$ si :

• $\forall x,y\in H$ on a $x\ast y\in H$ (stabilité)
• $1_A\in H$
• Si $x\in H$ alors $x^{-1}\in H$

Exemple(s) :

Propriétés/Théorèmes :

1. Si $H$ est un sous-groupe de $(\mathbb{Z},+)$ alors $H=n\mathbb{Z}$ pour un certain $n\in \mathbb{N}$

   Preuve : Si $H=\{0\}$, alors $H=0\mathbb{Z}$ Soit $H\ne \{0\}$ et $n$ le plus petit entier $>0$ de $H$

   • Vu que $H$ est un groupe, $\{0,n,-n,2n,-2n,\dots \}=n\mathbb{Z}\in H$
   • Soit $a\in H$. On peut écrire $a=qn+r$ avec $r\in \{0,\dots ,n-1\}$. On a $r=0$ car sinon $a-qn=r\in H$ est un entier positif $\le n$ Donc $H=\{0,n,-n,2n,-2n,\dots \}=n\mathbb{Z}$ $$ac=bc\Rightarrow a=aϵ=acd=bcd=bϵ=b$$

2. Les inverses sont symétriques. Si $ab=ϵ$ alors $a=b^{-1}$ et $b=a^{-1}$

   Preuve : $$ab=ϵ\Rightarrow bab=b\Rightarrow bab{b}^{-1}=b{b}^{-1}\Rightarrow ba=ϵ$$

3. Soit $H$ un sous-ensemble fini non-vide d'un groupe $G$. Si $H$ est stable, alors $H$ est un sous-groupe de $G$.

   Preuve : Soit $a\in H$ et $f:H\to H:x\to ax$

   On observe que $f$ est bijective

   Présence du neutre : Comme $f$ est bijective, $\exists b\in H:f(b)=a=ab$. Donc $b=ϵ$

   Présence de l'inverse : $\exists b\in H:f(b)=ϵ$. Donc $b=a^{-1}$

4. Théorème de Lagrange Soient $G$ un groupe fini et $H$ un sous-groupe de $G$ tels que $|G|=n$ et $|H|=m$, alors $m$ divise $n$

   Preuve : Les classes latérales de $H$ sont toutes de taille $m$ et forment une partition de $G$ Donc $|G|=k|H|$ où $k$ est le nombre de classes latérales de $H$ On a donc : $|G/H|=|G|/|H|$

Classes Latérales/Suivant un Sous-Groupe $H$

Soit $H$ un sous-groupe de $G$. La classe latérale de $a\in G$ modulo $H$ est : $$aH=\{ax|x\in H\}$$

(ici, $ab$ signifie $a\ast b$ où $\ast$ est l'opérateur du groupe)

Exemple(s) :

1. $\mathbb{Z}$ est un sous-groupe de $(\mathbb{R},+)$ : les classes latérales sont $\{x+a|x\in \mathbb{Z}\}$ avec $a\in [0,1]$
2. $\{(x,ax)|x\in \mathbb{R}\}$ est un sous-groupe de $({\mathbb{R}}^2,+)$ (addition par composants) Les classes latérales sont $(x,ax+b),|,x\in \mathbb{R}$ avec $b\in \mathbb{R}$
3. $n\mathbb{Z}=\{nx|x\in \mathbb{Z}\}$ avec $n\in {\mathbb{N}}^{\ge 1}$ est un sous-groupe de $(\mathbb{Z},+)$ Les classes latérales sont $\{nx+b,|,x\in \mathbb{Z}\}$ avec $b\in \{0,\dots ,n-1\}$
4. $\{2^i|i\in \mathbb{Z}\}$ est un sous-groupe de $({\mathbb{R}}^{>0},\ast )$ Les classes latérales sont $\{a\ast 2^i,|,i\in \mathbb{Z}\}$ avec $a\in [1,2)$

Propriétés/Théorèmes :

1. Il existe une bijection entre $aH$ et $H$.

   Preuve : Soit $f:G\to aH$ tel que $f(x)=ax$

   • $f$ est injective : Vu que $a$ est inversible, $a{x}_1=a{x}_2\Rightarrow x_1=x_2$
   • $f$ est surjective : Par définition de $aH$, tout $y\in aH$ est dans l'image de $f$ Donc $f$ est bijective

2. Les classes latérales distinctes modulo $H$ forment une partition de $G$. Une partition est un ensemble de sous-ensembles non-vides et disjoints dont l'union est l'ensemble de départ.

   Preuve : Soient $a_{1}H,a_{2}H,\dots$ les classes latérales modulo $H$

   • Tout élément de $G$ est dans une classe latérale Si $g\in G$ alors $g\in gH$ puisque $ϵ\in H$

   • Les classes latérales $aH$ et $bH$ sont disjointes ou identiques. Soient $a,b\in G$ et $x\in bH$. On montre que $x\in aH\iff b^{-1}a\in H$ (Ainsi, $aH=bH$ si $b^{-1}a\in H$ et $aH\cap bH=\varnothing$ sinon)

     $\Rightarrow$ Soit $x=a{h}_1=b{h}_2$ avec $h_1,h_2\in H$. On a : $a{h}_1=b{h}_2\Rightarrow a=b{h}_2{h}_1^{-1}\Rightarrow b^{-1}a=h_2{h}_1^{-1}\in H$

     $\Leftarrow$ Soit $b^{-1}a\in H\Rightarrow a^{-1}b\in H$ et $x=b{h}_1=(a{a}^{-1})b{h}_1=a((a^{-1}b)h_1)\in aH$

3. Si $G$ est commutatif, alors $(ax)(bx)=(ab)(xy)$. En supposant que $x,y\in H$, $a^{\prime }=ax$ et $b^{\prime }=by$ cela implique que : $$a^{\prime }\in aH\text{et}{b}^{\prime }\in bH\Rightarrow (a^{\prime }{b}^{\prime })\in (ab)H$$ (Quand $H$ est clair dans le contexte, on écrit $[a]$ pour $aH$)

4. Soient $aH$ et $bH$, si il n'existe aucun $c\in G$ tel que $a\in cH$ et $b\in cH$ (dit autrement : si $a$ et $b$ ne partagent pas une même classe latérale) alors $aH\cap bH=\varnothing$. (Enfaite il s'agit en quelque sorte d'une reformulation de la propriété 2 mais je trouve que ça illustre mieux son utilité).

   Preuve : (ma preuve, pas encore vérifié par une autre personne mais, encore une fois, assez semblable à celle de la propriété 2)

   Par l'absurde, admettons qu'il existe un $c\in G$ tel que $c\in aH$ et $c\in bH$ alors que $a$ et $b$ ne sont trouvent pas dans une même classe, on en déduit les relations suivantes : $$c=a{h}_1\text{et}c=b{h}_2\iff h_1{h}_2^{-1}=a^{-1}b\in H$$ Or, si $a^{-1}b$ est dans $H$ on a $b$ dans $aH$ or $a$ est également dans $aH$ par la présence du neutre dans $H$ ce qui contredit le fait que $a$ et $b$ ne se trouvent pas dans une même classe.

Groupe Quotient

Le groupe quotient $G/H$ est le groupe commutatif formé de :

• l’ensemble des classes latérales de $G$ modulo $H$
• l’opérateur défini par $[a][b]=[ab]$ (Rappel : [a]=aH)
• le neutre défini par $[ϵ]=H$

Autre façon de le dire :

• Relation d’équivalence sur $G$ commutatif créée par le sous-groupe $H$ : $a\sim b$ ssi $a^{-1}b\in H$.
• Les classes d’équivalences sont précisément les classes latérales de $H$
• Le groupe quotient $G$ est le groupe $G$ quotienté par la relation d’équivalence

Exemple(s) :

a mod n

Soient $a\in \mathbb{Z}$ et $n\in {\mathbb{N}}^{>1}$ $a$ mod $n$ est le reste de la division de $a$ par $n$

Addition modulo

On dit que ${\mathbb{Z}}_n=\{0,\dots ,n-1\}$ est muni de l'addition modulo $n$ si $a+b=r$ mod $n$

Exemples :

1. $2+4=1$ dans ${\mathbb{Z}}_5$
2. $1+3=0$ dans ${\mathbb{Z}}_4$

Propriétés/Théorèmes :

1. ${\mathbb{Z}}_n$ est isomorphe à $\mathbb{Z}/n\mathbb{Z}$ Preuve : Considérer $f:{\mathbb{Z}}_n\to \mathbb{Z}/n\mathbb{Z}$ telle que $f(a)=[a]$

Sous-Groupe Engendré

Soit $G$ un groupe fini et $g\in G$.

Le sous-groupe $⟨g⟩$ engendré par $g$ est $⟨g⟩=\{g,g^2,g^3,\dots \}$. (On peut vérifier que l'ensemble $\{g,g^2,g^3,\dots \}$ est effectivement un sous-groupe et donc un groupe en vérifiant toutes les propriétés des groupes)

Exemples : soit $G={\mathbb{Z}}_6$

1. $⟨1⟩=\{1,2,3,4,5,0,1,\dots \}={\mathbb{Z}}_6$
2. $⟨2⟩=\{2,4,0,\dots \}⊊{\mathbb{Z}}_6$
3. $⟨3⟩=\{3,0,\dots \}⊊{\mathbb{Z}}_6$

Propriétés/Théorèmes :

1. Il existe $m$ tel que $g^m=ϵ$, vu que $⟨g⟩$ est un sous-groupe de $G$. L’ordre de $g$ est la plus petite valeur de $m$ telle que $g^m=ϵ$, c’est-à-dire $|⟨g⟩|$
2. Pour tout $g\in G$, l’ordre de $g$ divise $|G|$. (Résultat issu du théorème de Lagrange et du fait que $⟨g⟩$ est un sous-groupe de $G$)

Groupes cycliques

On dit que le groupe $G$ est cyclique si il existe $g$ tel que $⟨g⟩=G$

Propriétés/Théorèmes :

1. Si $G=⟨g⟩$ est d’ordre fini $n=|G|$, alors $g^n=ϵ$

   Preuve : Il doit exister $i$ tel que $g^i=ϵ$. Vu que les éléments de $G$ se répètent pour $j>i$, il faut que $i=n$ pour que $|⟨g⟩|=n$

2. Théorème [Euler-Fermat] : Si $G$ est d’ordre fini $n$, alors $g^n=ϵ$

   Preuve : Si $|⟨g⟩|=m$ alors $m$ divise $n$ vu que $⟨g⟩$ est un sous-groupe de $G$. Or, si $g^m=ϵ$, on a $g^{km}=ϵ$ pour tout $k\in \mathbb{N}$ et donc $g^n=ϵ$

3. On dit que $G$ est cyclique si $|G|=n$. $G$ possède un unique sous-groupe $H$ d’ordre $m$ pour tout $m$ divisant $n$, et $H$ est cyclique.

   Preuve : Soit $⟨g⟩=G$.

   Alors $⟨g^{n/m}⟩=\{g^{n/m},g^{2n/m},g^{3n/m},\dots ,g^{(m-1)n/m},ϵ\}$ est un sous-groupe cyclique d’ordre $m$ de $G$. 3.

   Pour vérifier l’unicité, s’intéresser à $⟨h⟩$ où $h=g^i$ et $i$ est le plus petit entier $>0$ tel que $g^i\in H$.

   Notation Ordre d'un élément

   Dans le contexte des groupes multiplicatifs, l'ordre d'un élément $a$ d'un groupe $G$ est le plus petit entier positif $n$ tel que $a^n=1$, où 1 est l'élément neutre du groupe. Autrement dit, c'est le plus petit $n$ pour lequel, effectue l'operation $a$ par lui-même $n$ fois, on obtient l'élément neutre.

   Plus spécifiquement, dans le groupe multiplicatif ${\mathbb{Z}}_{13}^{\ast }$, l'ordre d'un élément $a$ est le plus petit nombre entier positif $n$ tel que $a^n\equiv 1\mathrm{mod}13$.

   Par exemple, si on veut trouver l'ordre de 2 dans ${\mathbb{Z}}_{13}^{\ast }$, on cherche le plus petit $n$ tel que $2^n\equiv 1\mathrm{mod}13$.

Le groupe multiplicatif ${\mathbb{Z}}_p^{\ast }$

Soit ${\mathbb{Z}}_p^{\ast }=\{1,...,p-1\}$ avec $p$ premier, muni de la multiplication modulo $p$

Exemple(s) : ${\mathbb{Z}}_7^{\ast }=\{1,2,3,4,5,6\}$

1. $3\times 4=5$
2. $3\times 5=1$

Propriétés/Théorèmes :

1. ${\mathbb{Z}}_p^{\ast }$ est un groupe

   Preuve :

   Stable : Si $p$ est premier, le produit $ij$ avec $1\le i,j<p$ ne sera jamais un multiple de $p$. Donc $ij\ne 0$ mod $p$ et $ij\in {\mathbb{Z}}_p^{\ast }$

   Neutre : $1$ est le neutre

   Inverse : Soit $a\in {\mathbb{Z}}_p^{\ast }$, et considérons la fonction $f:{\mathbb{Z}}_p^{\ast }\to {\mathbb{Z}}_p^{\ast }:f(x)\to ax$, $f$ est injective : si $f(i)=f(j)$ alors $ai=aj$ mod $p$ et $ai-aj=kp$ pour $k\in \mathbb{Z}$. Or, $a,i$ et $j$ ne sont pas multiples de $p$, donc $k=0$ et $i=j$. Donc $f$ est bijective, et $\exists b:ab=1$.

Anneau

Un anneau est une structure $(A,+,\cdot )$ telle que :

• $(A,+)$ est un groupe commutatif — on écrit $0$ pour son neutre.
• $(A,\cdot )$ est un monoïde — on écrit $1$ pour son neutre.
• La multiplication se distribue sur l'addition, à gauche et à droite : $$x\cdot (y+z)=x\cdot y+x\cdot z\forall x,y,z\in A$$ $$(x+y)\cdot z=x\cdot z+y\cdot z\forall x,y,z\in A$$

Un anneau est commutatif si la multiplication est commutative.

Exemple(s) :

1. $\mathbb{Z},\mathbb{R},\mathbb{Q},\mathbb{C}$ munis des opérations habituelles.
2. $\mathbb{R}[X]$, l’ensemble des polynômes à coefficients réels.
3. ${\mathbb{R}}^{n\times n}$ — non commutatif quand $n\ge 2$.

Propriété(s) :

1. $0$ est absorbant : $\forall r,0\cdot r=r\cdot 0=0$ On voit : $r=r\cdot 1=r\cdot (1+0)=r+0\cdot r\Rightarrow 0=0\cdot r$
2. Si $A$ est un anneau et $0=1$ alors $A=\{0\}$ On voit : $r=r\cdot 1=r\cdot 0=0$ pour tout $r\in A$
3. Si $(A,+,\cdot )$ est un anneau tel que $0\ne 1$, alors $(A,\cdot )$ n'est pas un groupe. On voit : $0$ n'est pas inversible, vu qu'il est absorbant

L'anneau $Z_n$

L'anneau $Z_n$ est défini comme: $$Z_n=\{0,1,\dots ,n-1\}$$ muni de l'addition modulaire et de la multiplication modulaire forme un anneau commutatif.

Proposition(s) :

1. Si $n$ est premier, alors $Z_n$ est un corps, souvent noté $F_n$.
2. Si $n$ est composé, alors $Z_n$ n'est pas un corps.

Preuve :

Soit $a\ne 1$ divisant $n$ et $b=\frac{n}{a}$. $$Alorsab\equiv 0\mathrm{mod}n$$ ce qui veut dire que $a$ est un diviseur de 0 et n'est donc pas inversible.

Corollaire :

Un élément $a\in Z_n$ est inversible si et seulement si: $$gcd(a,n)=1$$

Preuve :

Si $gcd(a,n)\ne 1$, alors $$a\cdot \frac{n}{gcd(a,n)}\equiv 0\mathrm{mod}n$$ Si $gcd(a,n)=1$ alors $an$ est le premier multiple de $a$ qui est un multiple de $n$, et $a$ ne divise donc pas 0.

Corps

Un corps est un anneau $(A,+,\cdot )$ tel que :

• $(A-\{0\},\cdot )$ est un groupe.

Un corps est commutatif si :

• $(A-\{0\},\cdot )$ est un groupe commutatif.

Exemple(s) :

1. $\mathbb{R}$, $\mathbb{Q}$, et $\mathbb{C}$ sont des corps commutatifs.

2. $\mathbb{Z}$ n’est pas un corps.

3. $\mathbb{R}[X]$ n’est pas un corps.

4. ${\mathbb{R}}^{n\times n}$ n’est pas un corps quand $n\ge 2$.

https://crypto.stanford.edu/pbc/notes/numbertheory/poly.html

Le module d'un polynome en $F_{2^8}$ par un polynome de même degré peut être obtenu en prenant la représenation des polynomes en bits et en faisant un XOR entre les bits des deux polynomes. Le résultat est un polynome de degré $7$ .

Globalement si $a$ et $b$ sont deux polynomes de degré $7$ en $F_{2^8}$, alors le module $a\text{ mod }b$ est donné par $b_a\oplus b_b$ où $b_a$ et $b_b$ sont les représentations binaires de $a$ et $b$ et $\oplus$ est le XOR bit par bit.

Concept vient du devoir 2 de LEPL1108 :

L'algorithme suivant pour la multiplication dans $F_{2^8}$ :

Peut être implémenté en python comme suit :

def multiply(self, x, y, pol):

    a = int(x, 2)
    b = int(y, 2)
    p = int(pol, 2)

    product = 0

    while b:
        if b & 1:
            product ^= a
            b ^= 1
        a <<= 1
        if a & 256:
            a ^= p
        b >>= 1

    return self.toBinary(product)

Preuve :

TODO

(Note to self : pour la preuve, il suffit d'utiliser la division euclidienne pour un polynome général et de montrer que le reste est bien donné par XOR)

Séance 3

Énoncé

Solutions

Exercice 3.7

1. Le groupe est de taille 12 et donc d'ordre 12. Une propriété des sous-groupes engendrés par $g\in G$ est que leur ordre divise l'ordre de $G$. Donc l'ordre de $g$ divise 12 (voir Sous-Groupe Engendré dans le chapitre sur les groupes). Les diviseurs de 12 sont 1, 2, 3, 4, 6 et 12. Donc les ordres possibles de $g$ sont 1, 2, 3, 4, 6 et 12.

2. $⟨2⟩=\{2,4,8,3,6,12,11,9,5,10,7,1\}$, ordre $=12$

   $⟨3⟩=\{3,9,1\}$, ordre $=3$

   $⟨4⟩=\{4,3,12,9,10,1\}$, ordre $=6$

   $⟨5⟩=\{5,12,8,1\}$, ordre $=4$

3. On remarque premièrement que $⟨5⟩$ est un groupe (important). Comme les classes latérales forment une partition du groupe de départ et qu'elles sont de même taille, il faut qu'il y a 3 classes latérales modulo $⟨5⟩$ pour arriver à une partition d'ordre $12$. Ces classes sont :

   $⟨5⟩=\{5,12,8,1\}$

   $2⟨5⟩=\{10,11,3,2\}$

   $4⟨5⟩=\{7,9,6,4\}$

4. Comme tout élément de ${\mathbb{Z}}_{13}^{\ast }$ à la puissance $12$ donne $1$ (voir raisonnement de la sous-question $1$). On peut dire que $x^{2019}=5\iff x^{2016}{x}^3=5\iff x^3=5$. Maintenant on peut essayer tous les éléments de $G$ pour voir lequel à la puissance $3$ donne $5$ ou on remarque que $2$ est un élément générateur et que donc tout élément de $G$ peut être exprimé comme une puissance de $2$ et donc : $$(2^y{)}^3=2^9\iff 3y=9\text{mod}12$$

En ajoutant plusieurs fois $12$ à $9$ dans $3y=9$ et en regardant les valeurs possibles de $y$ on trouve $3,7,11$ ce qui donne des valeurs de $x$ : $8,11,7$ 5. On a trouvé que $11=2^7$ donc $2^{7n}=2$ donne $7n=1\text{mod12}$, ce qui donne $n=7$. Askip le fait que la solution est unique vient du fait que $\text{gcd}(7,12)=1$.

Exercice 3.8

On calcule les puissance de $3$ dans ${\mathbb{Z}}_7^{\ast }$ ce qui donne : $3,2,6,4,5,1$. On en déduit que $x=2$ et $y=5$. Et donc $g^{10}=g^6{g}^4=4$. Encore une fois faut bien faire gaffe de prendre le modulo $6$ et pas $7$.

Interesting Links

1. Stanford : Roots of polynomials with modulus
2. AES explained using fields

Sources