summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2012-11-22 23:35:12 +0100
committerDavid A. Madore <david+git@madore.org>2012-11-22 23:35:12 +0100
commita390bb936ec7ed5c4568d456e902cb6f460999fd (patch)
treeb9dd7d2b92e2d9cccc645e87080bb87abab4f0bf
parent1a08343a8b3171052e9cc91e3f8de9fcbf08ae65 (diff)
downloadinfmdi720-a390bb936ec7ed5c4568d456e902cb6f460999fd.tar.gz
infmdi720-a390bb936ec7ed5c4568d456e902cb6f460999fd.tar.bz2
infmdi720-a390bb936ec7ed5c4568d456e902cb6f460999fd.zip
Write solution for exercise 1.
-rw-r--r--controle-20121127.tex93
1 files changed, 93 insertions, 0 deletions
diff --git a/controle-20121127.tex b/controle-20121127.tex
index d402e5f..1d3c8d5 100644
--- a/controle-20121127.tex
+++ b/controle-20121127.tex
@@ -81,29 +81,89 @@ La décomposition en facteurs premiers de $65\,535$ est : $3 \times 5
discutera selon la valeur de $x$ modulo $p$, et on dira clairement
quelles sont toutes les valeurs possibles que peut prendre $x^{256}$
modulo $p$.)
+\begin{corrige}
+Le petit théorème de Fermat (ou le théorème d'Euler) affirme que
+$x^{256} \equiv 1 \pmod{257}$ si $x$ n'est pas nul modulo $257$ ; et
+si $x$ \emph{est} nul modulo $257$ (c'est-à-dire, multiple de lui),
+alors évidemment $x^{256} \equiv 0 \pmod{257}$. Les deux valeurs
+possibles de $x^{256}$ modulo $257$ sont donc $0$ et $1$.
+\end{corrige}
(1b) Même question que (1a) mais cette fois pour $x^{256}$ modulo $p$
avec $p \in \{3,5,17\}$ (on prendra garde que l'exposant est toujours
$256$ dans cette question, ce n'est pas une erreur de l'énoncé).
+\begin{corrige}
+Comme en (1a), on a $x^{p-1} \equiv 1 \pmod{p}$ si $x$ n'est pas nul
+modulo $p$ et $x^{p-1} \equiv 0 \pmod{p}$ si $x$ est nul modulo $p$ ;
+et comme $256$ est multiple de $p-1$ dans chacun des cas considérés
+(c'est-à-dire multiple de $2,4,16$), et comme toute puissance de $1$
+vaut $1$ et toute puissance non nulle de $0$ vaut $0$, on a aussi
+$x^{256} \equiv 1 \pmod{p}$ si $x$ n'est pas nul modulo $p$ et
+$x^{256} \equiv 0 \pmod{p}$ si $x$ est nul modulo $p$.
+\end{corrige}
(2) Montrer que $x^{256} \equiv 1 \pmod{65\,535}$ si $x$ est premier
avec $65\,535$. Que peut-on en déduire sur l'ordre multiplicatif des
éléments de $(\mathbb{Z}/65535\mathbb{Z})^\times$ ?
+\begin{corrige}
+Si $x$ est premier avec $65\,535$, cela signifie qu'il est n'est pas
+multiple de $p$ pour $p \in \{3,5,17,257\}$, autrement dit qu'il est
+non-nul modulo $p$ pour chacun de ces $p$. On a vu que dans ces
+conditions $x^{256} \equiv 1 \pmod{p}$ pour chacun de ces $p$. Comme
+$3,5,17,257$ sont premiers entre eux deux à deux, le théorème chinois
+assure que la congruence $x^{256} \equiv 1$ modulo ces quatre nombres
+implique la même congruence $x^{256} \equiv 1$ modulo leur produit,
+c'est-à-dire $x^{256} \equiv 1 \pmod{65\,535}$.
+
+Autrement dit, l'ordre multiplicatif de n'importe quel élément de
+$(\mathbb{Z}/65535\mathbb{Z})^\times$ divise $256$ (ou, si on préfère,
+est de la forme $2^i$ pour un $0\leq i \leq 8$).
+\end{corrige}
(3) Que vaut $\varphi(65\,535)$ ?
+\begin{corrige}
+Par multiplicativité de $\varphi$, cela vaut $(3-1) \times (5-1)
+\times (17-1) \times (257-1) = 2 \times 4 \times 16 \times 256 =
+2^{1+2+4+8} = 2^{15} = 32\,768$.
+\end{corrige}
(4) Comparer le résultat de la question (2) à l'énoncé du théorème
d'Euler modulo $65\,535$.
+\begin{corrige}
+Le théorème d'Euler modulo $65\,535$ assure que $x^{\varphi(65\,535)}
+\equiv 1 \pmod{65\,535}$ pour tout $x$ premier avec $65\,535$,
+c'est-à-dire $x^{32\,768} \equiv 1 \pmod{65\,535}$. Le résultat de la
+question (2) est plus fort puisqu'il affirme que déjà $x^{256} \equiv
+1 \pmod{65\,535}$ (autrement dit, le théorème d'Euler affirme que
+l'ordre multiplicatif de n'importe quel élément de
+$(\mathbb{Z}/65535\mathbb{Z})^\times$ divise $32\,768$ tandis que la
+question (2) affirme qu'en fait il divise $256$).
+\end{corrige}
(5) Montrer que $x^{257} \equiv x \pmod{p}$ pour tout entier $x$ et
pour tout $p \in \{3,5,17, 257\}$.
+\begin{corrige}
+Si $x$ n'est pas multiple de $p$, on a vu $x^{256} \equiv 1 \pmod{p}$
+et on en déduit $x^{257} \equiv x \pmod{p}$ ; si $x$ est multiple
+de $p$, alors $x^{257} \equiv 0 \equiv x \pmod{p}$.
+\end{corrige}
(6) En déduire que $x^{257} \equiv x \pmod{65\,535}$ pour tout
entier $x$.
+\begin{corrige}
+Comme $3,5,17,257$ sont premiers entre eux deux à deux, le théorème
+chinois assure que la congruence $x^{257} \equiv x$ modulo ces quatre
+nombres implique la même congruence $x^{257} \equiv x$ modulo leur
+produit, c'est-à-dire $x^{257} \equiv x \pmod{65\,535}$.
+\end{corrige}
(7) Rappeler pourquoi il existe des éléments de
$(\mathbb{Z}/257\mathbb{Z})^\times$ dont l'ordre multiplicatif vaut
exactement $256$.
+\begin{corrige}
+Ces éléments sont dits primitifs, et ils existent car $257$ est
+premier.
+\end{corrige}
(8) On suppose que $x$ est un entier premier avec $65\,535$ et que
l'ordre multiplicatif de sa classe modulo $257$ (qui est un élément de
@@ -111,15 +171,48 @@ $(\mathbb{Z}/257\mathbb{Z})^\times$) vaut exactement $256$. Montrer
que la classe de $x$ modulo $65\,535$ (qui est cette fois un élément
de $(\mathbb{Z}/65535\mathbb{Z})^\times$) est elle aussi d'ordre
multiplicatif $256$.
+\begin{corrige}
+On sait déjà que l'ordre multiplicatif de $x$ modulo $65\,535$
+divise $256$ (c'est la question (2)), il s'agit de montrer qu'il n'est
+pas moindre. Mais si on avait $x^i \equiv 1 \pmod{65\,536}$ pour $0 <
+i < 256$, alors \emph{en particulier} on aurait $x^i \equiv 1
+\pmod{257}$ puisque $257$ divise $65\,536$. Or on a supposé que
+l'ordre multiplicatif de $x$ modulo $257$ vaut $256$, ce qui signifie
+que $x^i \equiv 1 \pmod{257}$ ne se produit pas avant $256$.
+\end{corrige}
(9) En déduire l'ordre multiplicatif maximal possible d'un élément de
$(\mathbb{Z}/65535\mathbb{Z})^\times$.
+\begin{corrige}
+On a vu en question (2) que l'ordre multiplicatif d'un élément de
+$(\mathbb{Z}/65535\mathbb{Z})^\times$ divise toujours $256$, et on
+vient de voir en combinant (7) et (8) qu'il existe effectivement des
+éléments d'ordre $256$.
+\end{corrige}
(10) Sans aucune hypothèse sur l'entier $x$, combien de valeurs
distinctes peut prendre $x^{256}$ modulo $65\,535$ ? (On ne demande
pas de calculer ces valeurs, uniquement de calculer leur nombre,
c'est-à-dire, si on préfère, le cardinal de l'image de $x \mapsto
x^{256}$ sur $\mathbb{Z}/65535\mathbb{Z}$.)
+\begin{corrige}
+On a vu que modulo chacun des $p \in \{3,5,17, 257\}$, il n'y a que
+deux valeurs possibles de $x^{256}$ modulo $p$, à savoir $0$ ou $1$.
+Comme $3,5,17,257$ sont premiers entre eux deux à deux, le théorème
+chinois assure qu'une congruence modulo $65\,535$ équivaut exactement
+à une congruence modulo chacun de $3,5,17, 257$. Appelons « valeur
+ magique » une classe de congruence $65\,535$ qui est congrue à $0$
+ou $1$ modulo chacun des $4$ nombres $3,5,17, 257$ : il y a $16$
+« valeurs magiques » (une pour chacune des combinaisons de $0$ ou de
+$1$ modulo chacun des $4$ nombres $3,5,17, 257$, ce qui fait $2^4 =
+16$). D'après ce qu'on a vu, $x^{256}$ est toujours une valeur
+magique modulo $65\,535$. Et de plus, si $x$ lui-même est une valeur
+magique, alors $x^{i} \equiv x \pmod{65\,535}$ pour tout $i\geq 1$
+puisque $0^{i} \equiv 0$ et $1^{i} \equiv 1$ modulo chacun des $p \in
+\{3,5,17, 257\}$. En particulier, $x^{256} \equiv x \pmod{65\,535}$.
+Donc les $16$ valeurs magiques sont bien toutes atteintes
+par $x^{256}$.
+\end{corrige}
%
%