summaryrefslogtreecommitdiffstats
path: root/exercices2.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2011-10-24 15:39:14 +0200
committerDavid A. Madore <david+git@madore.org>2011-10-24 15:42:06 +0200
commit2c0256cb192f4579ba7ae9c4d57886a5af93c043 (patch)
treee040dbbb928416ead98defa0a531683a509f6788 /exercices2.tex
parent78ff1da4ae114bd54763eb0faa054dc7c5be59d8 (diff)
downloadinfmdi720-2c0256cb192f4579ba7ae9c4d57886a5af93c043.zip
infmdi720-2c0256cb192f4579ba7ae9c4d57886a5af93c043.tar.gz
infmdi720-2c0256cb192f4579ba7ae9c4d57886a5af93c043.tar.bz2
Re-encode as utf-8.
Diffstat (limited to 'exercices2.tex')
-rw-r--r--exercices2.tex263
1 files changed, 132 insertions, 131 deletions
diff --git a/exercices2.tex b/exercices2.tex
index c36ddd2..7cee362 100644
--- a/exercices2.tex
+++ b/exercices2.tex
@@ -1,7 +1,7 @@
%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it?
\documentclass[12pt]{article}
\usepackage[francais]{babel}
-\usepackage[latin1]{inputenc}
+\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{times}
% A tribute to the worthy AMS:
@@ -25,12 +25,13 @@
\newcommand{\signe}{\operatorname{signe}}
\newcommand{\tee}{\mathbin{\top}}
\newcommand{\Frob}{\operatorname{Fr}}
+\DeclareUnicodeCharacter{00A0}{~}
%
\newif\ifcorrige
\corrigetrue
\newenvironment{corrige}%
{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
-\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}}
+\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}}
{{\hbox{}\nobreak\hfill\checkmark}%
\ifcorrige\relax\else\egroup\fi\par}
%
@@ -38,9 +39,9 @@
%
\begin{document}
\ifcorrige
-\title{INFMDI720\\Exercices --- Corrigé\\{\normalsize Rappels mathématiques pour la cryptographie}}
+\title{INFMDI720\\Exercices --- Corrigé\\{\normalsize Rappels mathématiques pour la cryptographie}}
\else
-\title{INFMDI720\\Exercices\\{\normalsize Rappels mathématiques pour la cryptographie}}
+\title{INFMDI720\\Exercices\\{\normalsize Rappels mathématiques pour la cryptographie}}
\fi
\author{}
\date{}
@@ -54,42 +55,42 @@
\exercice
-Déterminer une relation de Bézout entre les polynômes $A = t^7 - t^6 +
+Déterminer une relation de Bézout entre les polynômes $A = t^7 - t^6 +
t^4 - t + 1$ et $B = t^6 + t^5 - t^4 + t^3 + t^2 + 1$ dans
$\mathbb{F}_3[t]$. Quel est l'inverse de $\bar B$ dans
-$\mathbb{F}_3[t]/(A)$ ?
+$\mathbb{F}_3[t]/(A)$ ?
\begin{corrige}
-On calcule les divisions euclidiennes successives : $t^7 - t^6 + t^4 -
+On calcule les divisions euclidiennes successives : $t^7 - t^6 + t^4 -
t + 1 = (t+1)\penalty0 (t^6+t^5-t^4+t^3+t^2+1) + (t^4+t^3-t^2+t)$,
puis $t^6 + t^5 - t^4 + t^3 + t^2 + 1 = t^2(t^4+t^3-t^2+t) + (t^2+1)$,
puis $t^4 + t^3 - t^2 + t = (t^2+t+1)\penalty0 (t^2+1) - 1$. Le pgcd
-de $A$ et $B$ est donc $1$ (ou $-1$, mais on a choisi de le prendre
+de $A$ et $B$ est donc $1$ (ou $-1$, mais on a choisi de le prendre
unitaire).
-On calcule alors des relations $UP + VQ = D$ comme suit :
+On calcule alors des relations $UP + VQ = D$ comme suit :
\begin{itemize}
-\item[$\bullet$] $U= -1$ ; $P= t^4+t^3-t^2+t$ ; $V= t^2+t+1$ ; $Q=
- t^2+1$ ; $D= 1$ (d'après la dernière division effectuée).
-\item[$\bullet$] $U= -t^2$ ; $P= t^4+t^3-t^2+t$ ; $V= 1$ ; $Q=
- t^6+t^5-t^4+t^3+t^2+1$ ; $D= t^2+1$ (d'après l'avant-dernière
- division effectuée).
-\item[$\bullet$] $U= -t^2(t^2+t+1)-1 = -t^4-t^3-t^2-1$ ; $P=
- t^4+t^3-t^2+t$ ; $V= t^2+t+1$ ; $Q= t^6+t^5-t^4+t^3+t^2+1$ ; $D= 1$
- (en remplaçant la valeur de $t^2+1$ donnée par la dernière égalité à
- la place du $Q$ de l'égalité précédente).
-\item[$\bullet$] $U= 1$ ; $P= t^7-t^6+t^4-t+1$ ; $V= -(t+1)$ ; $Q=
- t^6+t^5-t^4+t^3+t^2+1$ ; $D= t^4+t^3-t^2+t$ (d'après la première
- division effectuée).
-\item[$\bullet$] $U= -t^4-t^3-t^2-1$ ; $P= t^7-t^6+t^4-t+1$ ; $V=
- (t^2+t+1) - (-t^4-t^3-t^2-1)\penalty0 (t+1) = t^5-t^4-t^3-t^2-t-1$ ;
- $Q= t^6+t^5-t^4+t^3+t^2+1$ ; $D= 1$ (en remplaçant la valeur de
- $t^4+t^3-t^2+t$ donnée par la dernière égalité à la place du $P$ de
- l'égalité précédente.
+\item[$\bullet$] $U= -1$ ; $P= t^4+t^3-t^2+t$ ; $V= t^2+t+1$ ; $Q=
+ t^2+1$ ; $D= 1$ (d'après la dernière division effectuée).
+\item[$\bullet$] $U= -t^2$ ; $P= t^4+t^3-t^2+t$ ; $V= 1$ ; $Q=
+ t^6+t^5-t^4+t^3+t^2+1$ ; $D= t^2+1$ (d'après l'avant-dernière
+ division effectuée).
+\item[$\bullet$] $U= -t^2(t^2+t+1)-1 = -t^4-t^3-t^2-1$ ; $P=
+ t^4+t^3-t^2+t$ ; $V= t^2+t+1$ ; $Q= t^6+t^5-t^4+t^3+t^2+1$ ; $D= 1$
+ (en remplaçant la valeur de $t^2+1$ donnée par la dernière égalité à
+ la place du $Q$ de l'égalité précédente).
+\item[$\bullet$] $U= 1$ ; $P= t^7-t^6+t^4-t+1$ ; $V= -(t+1)$ ; $Q=
+ t^6+t^5-t^4+t^3+t^2+1$ ; $D= t^4+t^3-t^2+t$ (d'après la première
+ division effectuée).
+\item[$\bullet$] $U= -t^4-t^3-t^2-1$ ; $P= t^7-t^6+t^4-t+1$ ; $V=
+ (t^2+t+1) - (-t^4-t^3-t^2-1)\penalty0 (t+1) = t^5-t^4-t^3-t^2-t-1$ ;
+ $Q= t^6+t^5-t^4+t^3+t^2+1$ ; $D= 1$ (en remplaçant la valeur de
+ $t^4+t^3-t^2+t$ donnée par la dernière égalité à la place du $P$ de
+ l'égalité précédente.
\end{itemize}
-On a donc trouvé la relation de Bézout : $(-t^4-t^3-t^2-1) \penalty0
+On a donc trouvé la relation de Bézout : $(-t^4-t^3-t^2-1) \penalty0
(t^7-t^6+t^4-t+1) + (t^5-t^4-t^3-t^2-t-1) \penalty0
(t^6+t^5-t^4+t^3+t^2+1) = 1$.
@@ -104,54 +105,54 @@ t^3-\bar t^2-\bar t-1$.
\exercice
-(A) On admet que le polynôme $P := t^4 + t^3 + t^2 + t + 1 \in
-\mathbb{F}_3[t]$ est irréductible. Combien d'éléments a $F :=
-\mathbb{F}_3[t]/(P)$ ?
+(A) On admet que le polynôme $P := t^4 + t^3 + t^2 + t + 1 \in
+\mathbb{F}_3[t]$ est irréductible. Combien d'éléments a $F :=
+\mathbb{F}_3[t]/(P)$ ?
-(B) Quel est l'ordre (additif) de $\bar t$ dans le groupe additif
-de $F$ ?
+(B) Quel est l'ordre (additif) de $\bar t$ dans le groupe additif
+de $F$ ?
-(C) Calculer $\bar t^4$ et $\bar t^5$. Quel est l'ordre
+(C) Calculer $\bar t^4$ et $\bar t^5$. Quel est l'ordre
(multiplicatif) de $\bar t$ dans le groupe multiplicatif $F^\times$
-des éléments non-nuls de $F$ ? L'élément $\bar t$ est-il primitif ?
-Le polynôme $P$ est-il primitif ?
+des éléments non-nuls de $F$ ? L'élément $\bar t$ est-il primitif ?
+Le polynôme $P$ est-il primitif ?
-(D) Quels sont les conjugués de $\bar t$ (=ses images successives par
-le morphisme de Frobenius) ? Quel est le degré de $\bar t$ ?
+(D) Quels sont les conjugués de $\bar t$ (=ses images successives par
+le morphisme de Frobenius) ? Quel est le degré de $\bar t$ ?
\begin{corrige}
-(A) Le nombre d'éléments de $F$ est $3^{\deg P} = 3^4 = 81$ (comme le
- nombre de polynômes de degré $<4$ sur $\mathbb{F}_3$). On peut donc
+(A) Le nombre d'éléments de $F$ est $3^{\deg P} = 3^4 = 81$ (comme le
+ nombre de polynômes de degré $<4$ sur $\mathbb{F}_3$). On peut donc
noter $F = \mathbb{F}_{81}$. Il s'agit d'un corps, puisque $P$ est
- irréductible.
-
-(B) Les multiples additifs de $\bar t$ sont $0$, $\bar t$ et $2\bar t
- = -\bar t$, après quoi on retombe sur $0$ (la caractéristique de $F$
- est $3$). L'ordre additif de $\bar t$, comme celui de n'importe
- quel élément non nul dans un corps de caractéristique $3$, est
- donc $3$.
-
-(C) On a $\bar t^4 = -\bar t^3 - \bar t^2 - \bar t - 1$ comme il
- résulte d'une division euclidienne (évidente) de $t^4$ par $P$. Par
- conséquent, $\bar t^5 = -\bar t^4 - \bar t^3 - \bar t^2 - \bar t =
- 1$ (on peut aussi faire la division euclidienne de $t^5$ par $P$).
- Ceci signifie que l'ordre multiplicatif de $\bar t$ divise $5$,
- c'est-à-dire qu'il vaut $1$ ou $5$. Comme il ne vaut pas $1$
- (puisque $\bar t$ ne vaut pas $1$), il vaut $5$. De fait, les
- puissances de $\bar t$ sont : $1$, $\bar t$, $\bar t^2$, $\bar t^3$
- et $-\bar t^3 - \bar t^2 - \bar t - 1$, après quoi on retombe
- sur $1$. Comme $F^\times$ a $80$ éléments, $\bar t$ n'est pas
- primitif (un élément primitif est un élément d'ordre
- multiplicatif $80$). Ceci signifie précisément que le polynôme $P$
+ irréductible.
+
+(B) Les multiples additifs de $\bar t$ sont $0$, $\bar t$ et $2\bar t
+ = -\bar t$, après quoi on retombe sur $0$ (la caractéristique de $F$
+ est $3$). L'ordre additif de $\bar t$, comme celui de n'importe
+ quel élément non nul dans un corps de caractéristique $3$, est
+ donc $3$.
+
+(C) On a $\bar t^4 = -\bar t^3 - \bar t^2 - \bar t - 1$ comme il
+ résulte d'une division euclidienne (évidente) de $t^4$ par $P$. Par
+ conséquent, $\bar t^5 = -\bar t^4 - \bar t^3 - \bar t^2 - \bar t =
+ 1$ (on peut aussi faire la division euclidienne de $t^5$ par $P$).
+ Ceci signifie que l'ordre multiplicatif de $\bar t$ divise $5$,
+ c'est-à-dire qu'il vaut $1$ ou $5$. Comme il ne vaut pas $1$
+ (puisque $\bar t$ ne vaut pas $1$), il vaut $5$. De fait, les
+ puissances de $\bar t$ sont : $1$, $\bar t$, $\bar t^2$, $\bar t^3$
+ et $-\bar t^3 - \bar t^2 - \bar t - 1$, après quoi on retombe
+ sur $1$. Comme $F^\times$ a $80$ éléments, $\bar t$ n'est pas
+ primitif (un élément primitif est un élément d'ordre
+ multiplicatif $80$). Ceci signifie précisément que le polynôme $P$
n'est pas primitif.
-(D) Le morphisme de Frobenius est l'application $x \mapsto x^3$
- dans $F$. Les conjugués de $\bar t$, c'est-à-dire ses images
- successives par le Frobenius sont : $\bar t$ lui-même, $\bar t^3$,
+(D) Le morphisme de Frobenius est l'application $x \mapsto x^3$
+ dans $F$. Les conjugués de $\bar t$, c'est-à-dire ses images
+ successives par le Frobenius sont : $\bar t$ lui-même, $\bar t^3$,
puis $\bar t^9 = \bar t^4 = -\bar t^3 - \bar t^2 - \bar t - 1$ (car
- $\bar t^5 = 1$ à ce qu'on a vu), et ensuite on retombe sur $\bar
- t^{81} = \bar t$. Le degré de $\bar t$ est $4$ (c'est forcément le
- degré de $P$).
+ $\bar t^5 = 1$ à ce qu'on a vu), et ensuite on retombe sur $\bar
+ t^{81} = \bar t$. Le degré de $\bar t$ est $4$ (c'est forcément le
+ degré de $P$).
\end{corrige}
%
@@ -160,29 +161,29 @@ le morphisme de Frobenius) ? Quel est le degré de $\bar t$ ?
\exercice
-(A) On admet que le polynôme $P := t^4 + t + 1 \in \mathbb{F}_2[t]$
-est irréductible. Combien d'éléments a $F := \mathbb{F}_2[t]/(P)$ ?
+(A) On admet que le polynôme $P := t^4 + t + 1 \in \mathbb{F}_2[t]$
+est irréductible. Combien d'éléments a $F := \mathbb{F}_2[t]/(P)$ ?
-(B) Dresser la liste des puissances successives de $\bar t$ dans $F$.
-Quel est l'ordre de $\bar t$ ? Est-il primitif ? Quel est l'inverse
-de $\bar t$ ? Quels sont tous les éléments primitifs de $F$ ? Quel
-est l'ordre multiplicatif de $\bar t^3$ ? Même question pour $\bar
+(B) Dresser la liste des puissances successives de $\bar t$ dans $F$.
+Quel est l'ordre de $\bar t$ ? Est-il primitif ? Quel est l'inverse
+de $\bar t$ ? Quels sont tous les éléments primitifs de $F$ ? Quel
+est l'ordre multiplicatif de $\bar t^3$ ? Même question pour $\bar
t^5$.
-(C) Quels sont les conjugués de $\bar t$ ? Quel est son degré ?
-Mêmes questions pour $\bar t^3$. Mêmes questions pour $\bar t^5$.
+(C) Quels sont les conjugués de $\bar t$ ? Quel est son degré ?
+Mêmes questions pour $\bar t^3$. Mêmes questions pour $\bar t^5$.
-(D) Quels sont les éléments de l'unique corps à $4$ éléments contenu
-dans $F$ ?
+(D) Quels sont les éléments de l'unique corps à $4$ éléments contenu
+dans $F$ ?
\begin{corrige}
-(A) Le nombre d'éléments de $F$ est $2^{\deg P} = 2^4 = 16$ (comme le
- nombre de polynômes de degré $<4$ sur $\mathbb{F}_2$). On peut donc
+(A) Le nombre d'éléments de $F$ est $2^{\deg P} = 2^4 = 16$ (comme le
+ nombre de polynômes de degré $<4$ sur $\mathbb{F}_2$). On peut donc
noter $F = \mathbb{F}_{16}$. Il s'agit d'un corps, puisque $P$ est
- irréductible.
+ irréductible.
-(B) On calcule successivement en multipliant par $t$ et en se
- rappelant que $t^4 \equiv t+1 \pmod{P}$ :
+(B) On calcule successivement en multipliant par $t$ et en se
+ rappelant que $t^4 \equiv t+1 \pmod{P}$ :
\begin{tabular}{r|l}
$i$&$\bar t^i$\\\hline
@@ -204,52 +205,52 @@ $14$&$\bar t^4+\bar t^3+\bar t = \bar t^3+1$\\\hline
$15$&$\bar t^4+\bar t = 1$\\
\end{tabular}
-L'ordre de $\bar t$ est donc $15$, il est primitif puisque $\#F^\times
-= \#F-1 = 15$, tous les éléments non-nuls de $F$ ont été listés
-ci-dessus et on a même, plus précisément, établi un isomorphisme de
+L'ordre de $\bar t$ est donc $15$, il est primitif puisque $\#F^\times
+= \#F-1 = 15$, tous les éléments non-nuls de $F$ ont été listés
+ci-dessus et on a même, plus précisément, établi un isomorphisme de
groupes $(\mathbb{Z}/15\mathbb{Z}) \to F^\times$ par $\bar\imath
-\mapsto \bar t^i$. Cet isomorphisme permet de répondre facilement aux
-questions suivantes : l'inverse de $\bar t$ est celui qui correspond à
-l'opposé de $1$, soit $\bar t^{14} = \bar t^3+1$. Les éléments
-primitifs sont ceux qui correspondent aux générateurs de
-$\mathbb{Z}/15\mathbb{Z}$ (c'est-à-dire les classes des nombres
+\mapsto \bar t^i$. Cet isomorphisme permet de répondre facilement aux
+questions suivantes : l'inverse de $\bar t$ est celui qui correspond à
+l'opposé de $1$, soit $\bar t^{14} = \bar t^3+1$. Les éléments
+primitifs sont ceux qui correspondent aux générateurs de
+$\mathbb{Z}/15\mathbb{Z}$ (c'est-à-dire les classes des nombres
premiers avec $15$, soit $\bar 1$, $\bar 2$, $\bar 4$, $\bar 7$, $\bar
8$, $\bar{11}$, $\bar{13}$, $\bar{14}$), donc $\bar t$, $\bar t^2$,
$\bar t^4 = \bar t+1$, $\bar t^7 = \bar t^3+\bar t+1$, $\bar t^8 =
\bar t^2+1$, $\bar t^{11} = \bar t^3+\bar t^2+\bar t$, $\bar t^{13} =
\bar t^3+\bar t^2+1$ et $\bar t^{14} = \bar t^3+1$. L'ordre
-(multiplicatif) de $\bar t^3$ dans $F^\times$ est le même que l'ordre
-(additif) de $3$ dans $\mathbb{Z}/15\mathbb{Z}$, soit $5$, et de même
-l'ordre multiplicatif de $\bar t^5$ dans $F^\times$ est $3$.
-
-(C) Le morphisme de Frobenius est l'application $x \mapsto x^2$
-dans $F$. Les conjugués de $\bar t$, c'est-à-dire ses images
-successives par le Frobenius sont : $\bar t$ lui-même, $\bar t^2$,
-$\bar t^4 = \bar t+1$, $\bar t^8 = \bar t^2+1$ après quoi on retombe
-sur $\bar t^{16} = \bar t$. Le degré de $\bar t$ est $4$ (c'est
-forcément le degré de $P$). Pour ce qui est du degré de $\bar t^3$,
-ses images successives par le Frobenius sont : $\bar t^3$ lui-même,
+(multiplicatif) de $\bar t^3$ dans $F^\times$ est le même que l'ordre
+(additif) de $3$ dans $\mathbb{Z}/15\mathbb{Z}$, soit $5$, et de même
+l'ordre multiplicatif de $\bar t^5$ dans $F^\times$ est $3$.
+
+(C) Le morphisme de Frobenius est l'application $x \mapsto x^2$
+dans $F$. Les conjugués de $\bar t$, c'est-à-dire ses images
+successives par le Frobenius sont : $\bar t$ lui-même, $\bar t^2$,
+$\bar t^4 = \bar t+1$, $\bar t^8 = \bar t^2+1$ après quoi on retombe
+sur $\bar t^{16} = \bar t$. Le degré de $\bar t$ est $4$ (c'est
+forcément le degré de $P$). Pour ce qui est du degré de $\bar t^3$,
+ses images successives par le Frobenius sont : $\bar t^3$ lui-même,
$\bar t^6 = \bar t^3+\bar t^2$, $\bar t^{12} = \bar t^3+\bar t^2+\bar
-t+1$ et $\bar t^{24} = \bar t^9 = \bar t^3+\bar t$, après quoi on
-retombe sur $\bar t^{48} = \bar t^3$ ; donc le degré de $\bar t^3$ est
-également $4$. Enfin, pour calculer le degré de $\bar t^5$, on a ses
-images successives qui sont $\bar t^5 = \bar t^2+\bar t$ lui-même et
+t+1$ et $\bar t^{24} = \bar t^9 = \bar t^3+\bar t$, après quoi on
+retombe sur $\bar t^{48} = \bar t^3$ ; donc le degré de $\bar t^3$ est
+également $4$. Enfin, pour calculer le degré de $\bar t^5$, on a ses
+images successives qui sont $\bar t^5 = \bar t^2+\bar t$ lui-même et
$\bar t^{10} = \bar t^2+\bar t+1$, puis $\bar t^{20} = \bar t^5$, donc
-il n'y a que deux conjugués (en comptant $\bar t^5$ lui-même), et son
-degré est $2$.
-
-(D) On sait que $\mathbb{F}_4$ est contenu dans $F = \mathbb{F}_{16}$
-car $16$ est une puissance de $4$, et on sait qu'alors $\mathbb{F}_4 =
-\{x\in F : x^4=x\}$. Une façon de trouver ces éléments est de
-réécrire $x^4 = x$ comme $(x^2)^2 = x$ (on retombe sur $x$ après deux
-applications du Frobenius : ou encore, le degré de $x$ est $1$
-ou $2$) ; les éléments vérifiant ceci sont $0$ et $1$, bien sûr, et
+il n'y a que deux conjugués (en comptant $\bar t^5$ lui-même), et son
+degré est $2$.
+
+(D) On sait que $\mathbb{F}_4$ est contenu dans $F = \mathbb{F}_{16}$
+car $16$ est une puissance de $4$, et on sait qu'alors $\mathbb{F}_4 =
+\{x\in F : x^4=x\}$. Une façon de trouver ces éléments est de
+réécrire $x^4 = x$ comme $(x^2)^2 = x$ (on retombe sur $x$ après deux
+applications du Frobenius : ou encore, le degré de $x$ est $1$
+ou $2$) ; les éléments vérifiant ceci sont $0$ et $1$, bien sûr, et
aussi $\bar t^5 = \bar t^2+\bar t$ comme on vient de le voir, et
-forcément $\bar t^5 + 1 = \bar t^2+\bar t+1$ (puisqu'un corps est
-stable ar addition). Une autre façon de résoudre $x^4 = x$ est de le
-réécrire comme $x=0$ ou bien $x^3 = 1$, c'est-à-dire qu'il s'agit de
-$0$ et des éléments d'ordre divisant $3$, donc, d'après l'isomorphisme
-déjà déterminé, $\bar t^5 = \bar t^2+\bar t$ et $\bar t^{10} = \bar
+forcément $\bar t^5 + 1 = \bar t^2+\bar t+1$ (puisqu'un corps est
+stable ar addition). Une autre façon de résoudre $x^4 = x$ est de le
+réécrire comme $x=0$ ou bien $x^3 = 1$, c'est-à-dire qu'il s'agit de
+$0$ et des éléments d'ordre divisant $3$, donc, d'après l'isomorphisme
+déjà déterminé, $\bar t^5 = \bar t^2+\bar t$ et $\bar t^{10} = \bar
t^2+\bar t+1$.
\end{corrige}
@@ -260,30 +261,30 @@ t^2+\bar t+1$.
\exercice
Calculer le pgcd dans $\mathbb{F}_{11}[t]$ de $t^2 - 2$ et $t^{11}-t$.
-En déduire que $2$ n'est pas un carré dans $\mathbb{F}_{11}$
-(c'est-à-dire qu'il n'existe pas de $\alpha \in \mathbb{F}_{11}$ tel
-que $\alpha^2 = 2$ ; indication : de quels polynômes intéressants
-$\alpha$ serait-il racine ?).
+En déduire que $2$ n'est pas un carré dans $\mathbb{F}_{11}$
+(c'est-à-dire qu'il n'existe pas de $\alpha \in \mathbb{F}_{11}$ tel
+que $\alpha^2 = 2$ ; indication : de quels polynômes intéressants
+$\alpha$ serait-il racine ?).
\begin{corrige}
-On calcule les divisions euclidiennes successives : $t^{11}-t = (t^9 +
+On calcule les divisions euclidiennes successives : $t^{11}-t = (t^9 +
2t^7 + 4t^5 - 3t^3 + 5t)\penalty0 (t^2-2) + 9t$, puis $t^2-2 =
(5t)(9t) - 2$, le dernier reste est une constante donc le pgcd
-vaut $1$.
+vaut $1$.
S'il y avait un $\alpha \in \mathbb{F}_{11}$ tel que $\alpha^2 = 2$,
-alors il serait racine à la fois de $t^2 - 2$ en vertu de
+alors il serait racine à la fois de $t^2 - 2$ en vertu de
$\alpha^2=2$, et $t^{11} - t$ en vertu de $\alpha\in\mathbb{F}_{11}$
-(et du petit théorème de Fermat). C'est-à-dire que $t-\alpha$ serait
-un facteur commu à $t^2-2$ et $t^{11}-t$, et on vient de voir qu'il
+(et du petit théorème de Fermat). C'est-à-dire que $t-\alpha$ serait
+un facteur commu à $t^2-2$ et $t^{11}-t$, et on vient de voir qu'il
n'y en a pas.
-\emph{Remarque :} Vérifier que $t^2-2$ et $t^{11}-t$ sont premiers
-entre eux est une des parties du critère de Rabin pour vérifier que
-$t^2-2$ est irréductible. Ici, il n'y a pas besoin d'en faire plus :
+\emph{Remarque :} Vérifier que $t^2-2$ et $t^{11}-t$ sont premiers
+entre eux est une des parties du critère de Rabin pour vérifier que
+$t^2-2$ est irréductible. Ici, il n'y a pas besoin d'en faire plus :
comme $t^2-2$ n'a pas de racine, cela signifie qu'il n'a pas de
-facteur de degré $1$, et comme il est de degré $2$, il est
-irréductible.
+facteur de degré $1$, et comme il est de degré $2$, il est
+irréductible.
\end{corrige}
%