diff options
| -rw-r--r-- | controle-20121127.tex | 93 |
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} % % |