%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? \documentclass[12pt]{article} \usepackage[francais]{babel} \usepackage[latin1]{inputenc} \usepackage[T1]{fontenc} \usepackage{times} % A tribute to the worthy AMS: \usepackage{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsthm} % \usepackage{mathrsfs} \usepackage{wasysym} \usepackage{url} % \theoremstyle{definition} \newtheorem{comcnt}{Tout} \newcommand\exercice{% \refstepcounter{comcnt}\bigbreak\noindent\textbf{Exercice~\thecomcnt.}} \newcommand{\limp}{\mathrel{\Rightarrow}} \newcommand{\liff}{\mathrel{\Longleftrightarrow}} \newcommand{\pgcd}{\operatorname{pgcd}} \newcommand{\ppcm}{\operatorname{ppcm}} \newcommand{\signe}{\operatorname{signe}} \newcommand{\tee}{\mathbin{\top}} \newcommand{\Frob}{\operatorname{Frob}} % \newif\ifcorrige \corrigetrue \newenvironment{corrige}% {\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi% \smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}} {{\hbox{}\nobreak\hfill\checkmark}% \ifcorrige\relax\else\egroup\fi\par} % % % \begin{document} \ifcorrige \title{INFMDI720\\Contrôle de connaissance --- Corrigé\\{\normalsize Rappels mathématiques pour la cryptographie}} \else \title{INFMDI720\\Contrôle de connaissance\\{\normalsize Rappels mathématiques pour la cryptographie}} \fi \author{} \date{23 novembre 2010} \maketitle \pretolerance=10000 \tolerance=8000 \vskip1truein\relax \textbf{Consignes :} Les exercices sont complètement indépendants. Ils pourront être traités dans un ordre quelconque, mais on demande de faire apparaître de façon très visible dans les copies où commence chaque exercice. Il n'est pas nécessaire de faire des réponses longues. L'usage de tous les documents (notes de cours manuscrites ou imprimées, livres) est autorisé. L'usage des calculatrices électroniques est interdit. Durée : 1h30 \newpage % % % \exercice (A) Quel entier entre $1500$ et $2500$ est congru à $36$ modulo $47$ et à $49$ modulo $53$ ? \begin{corrige} Trouvons d'abord une relation de Bézout entre $47$ et $53$, en vérifiant du même coup qu'ils sont premiers entre eux. On a les divisions euclidiennes successives $53 = 1 \times 47 + 6$, puis $47 = 7 \times 6 + 5$, puis $6 = 1 \times 5 + 1$ : ceci montre que le pgcd est bien $1$, et on peut ensuite écrire $1 = 1\times 6 - 1\times 5 = 8\times 6 - 1\times 47 = 8\times 53 - 9\times 47$, cette dernière constituant la relation de Bézout recherchée. Comme $47$ et $53$ sont premiers entre eux, le théorème chinois assure que se donner une congruence modulo $47$ et une congruence modulo $53$ équivaut à se donner une congruence modulo $47\times 53$ ; comme $47\times 53$ est certainement $>1000$, ceci suffira à définir un unique entier entre $1500$ et $2500$ s'il en existe un. On sait par ailleurs que l'entier $36\times 8\times 53 - 49\times 9\times 47$ vérifiera les congruences recherchées ; on peut simplifier le calcul en calculant $36\times 8 = 288 \equiv 6 \pmod{47}$ et $-49\times 9 = -441 \equiv 36 \pmod{53}$, ce qui donne $6\times 53 + 36\times 47 = 2010$, qui vérifie les conditions demandées. \end{corrige} \ifcorrige\medbreak\else\relax\fi (B) Quel est le plus petit entier naturel multiple de $9$, congru à $6$ modulo $11$ et congru à $6$ modulo $10$ ? \begin{corrige} D'après le théorème chinois, être congru à $6$ modulo $10$ et $11$, comme ceux-ci sont premiers entre eux, revient à être congru à $6$ modulo $10 \times 11 = 110$. Cherchons maintenant une relation de Bézout entre $110$ et $9$ : on a $110 = 12\times 9 + 2$ et $9 = 4\times 2 + 1$ donc $1 = 1\times 9 - 4\times 2 = 49\times 9 - 4\times 110$. Le théorème chinois assure qu'être congru à $6$ modulo $110$ et à $0$ modulo $9$ équivaut à être congru à $6\times 49\times 9 - 0\times 4\times 110$ modulo $990$ ; or $6\times 49 = 294 \equiv 74 \pmod{110}$ donc $6\times 49\times 9 \equiv 74\times 9 = 666 \pmod{990}$. Ceci démontre que les entiers congrus à $0$ modulo $9$, à $6$ modulo $11$ et à $6$ modulo $10$ sont ceux congrus à $666$ modulo $990$, dont le plus petit positif est $666$. \end{corrige} \ifcorrige\medbreak\else\relax\fi (C) Quels sont les entiers entre $0$ et $100$ congrus à $12$ modulo $15$ et à $2$ modulo $20$ ? \begin{corrige} Les nombres $15$ et $20$ ne sont pas premiers entre eux : leur pgcd vaut $5$ puisque $15 = 3\times 5$ et $20 = 4\times 5$. Ceci étant, les congruences $12$ modulo $15$ et $2$ modulo $20$ sont compatibles modulo $5$ (toutes deux se réduisent sur $2$). Vérifier ces deux congruences revient donc simplement à être congru à $12$ modulo $15$ et à $2$ modulo $4$. Trouvons une relation de Bézout entre $15$ et $4$ : on a $15 = 3\times 4 + 3$ et $4 = 1\times 3 + 1$ donc $1 = 1\times 4 - 1\times 3 = 4\times 4 - 1\times 15$. Donc être congru à $12$ modulo $15$, et à $2$ modulo $4$ (ou ce qui revient au même à $2$ modulo $20$) revient à être congru à $12\times 4\times 4 - 2\times 1\times 15 = 162$ modulo $15\times 4 = 60$. Le seul nombre entre $0$ et $100$ vérifiant cette congruence est $42$. \end{corrige} \ifcorrige\medbreak\else\relax\fi (D) Quels sont les entiers entre $0$ et $9000$ congrus à $18$ modulo $91$ et à $24$ modulo $105$ ? \begin{corrige} Les nombres $91$ et $105$ ne sont pas premiers entre eux : leur pgcd est $7$ comme on le voit par exemple en appliquant l'algorithme d'Euclide ($105 = 1\times 91+14$ puis $91 = 6\times 14 + 7$ puis $14 = 2\times 7$). Or $18$ et $24$ ne sont pas congrus modulo $7$, donc aucun nombre congru à $18$ modulo $91$ n'est congru à $24$ modulo $105$. \end{corrige} % % % \exercice On a $561 = 3\times 11\times 17$. (1) Montrer que $n^{561} \equiv n \pmod{3}$ pour tout entier $n$, et de même $\mathop{\mathrm{mod}} 11$ et $\mathop{\mathrm{mod}} 17$. (Indication : la réponse à cette question doit faire intervenir le nombre $560$ et \emph{non pas} la factorisation de $561$ donnée ci-dessus.) (2) En déduire que $n^{561} \equiv n \pmod{561}$ pour tout entier $n$. \begin{corrige} (1) On sait que $n^2 \equiv 1 \pmod{3}$ pour tout entier $n$ non multiple de $3$ (théorème d'Euler ou petit théorème de Fermat). Comme $560$ est multiple de $2$, on a \textit{a fortiori} $n^{560} \equiv 1 \pmod{3}$. Ceci permet d'affirmer $n^{561} \equiv n \pmod{3}$ lorsque $n$ n'est pas multiple de $3$ ; or la même égalité vaut encore pour $n \equiv 0 \pmod{3}$ (c'est simplement $0=0$). On a bien prouvé $n^{561} \equiv n \pmod{3}$ pour tout $n$. De même : on sait que $n^{10} \equiv 1 \pmod{11}$ pour tout entier $n$ non multiple de $11$. Comme $560$ est multiple de $10$, on a \textit{a fortiori} $n^{560} \equiv 1 \pmod{11}$. Ceci permet d'affirmer $n^{561} \equiv n \pmod{11}$ pour $n$ non multiple de $11$, et c'est encore vrai pour $n$ multiple de $11$. De même : on sait que $n^{16} \equiv 1 \pmod{17}$ pour tout entier $n$ non multiple de $17$. Comme $560$ est multiple de $16$, on a \textit{a fortiori} $n^{560} \equiv 1 \pmod{17}$. Ceci permet d'affirmer $n^{561} \equiv n \pmod{17}$ pour $n$ non multiple de $17$, et c'est encore vrai pour $n$ multiple de $17$. (2) On a montré $n^{561} \equiv n \pmod{3}$ et $n^{561} \equiv n \pmod{11}$ et $n^{561} \equiv n \pmod{17}$ pour tout entier $n$. Comme $3,11,17$ sont premiers entre eux deux à deux, le théorème chinois assure qu'on a alors la congruence $n^{561} \equiv n$ modulo $3\times 11\times 17 = 561$. \end{corrige} % % % \exercice On admet que le polynôme suivant dans $\mathbb{F}_2[t]$ est irréductible : $f := t^8 + t^4 + t^3 + t^2 + 1$. (1) Quel est le nombre d'éléments de $\mathbb{F}_2[t]/(f)$ ? (Il s'agit comme d'habitude des polynômes modulo $f$.) Que peut-on en dire et comment le note-t-on ? (2a) Dans $\mathbb{F}_2[t]/(f)$, calculer les puissances $\bar t^i$ de l'élément $\bar t$ représenté par $t$, pour $i$ allant de $0$ à $20$ inclus. (Ici, « calculer » sous-entend qu'on demande comme d'habitude le représentant standard, c'est-à-dire celui donné par un polynôme de degré $<\deg f$.) (2b) Calculer $\bar t^{34} = (\bar t^{17})^2$ et $\bar t^{68} = (\bar t^{34})^2$ ; puis vérifier que $\bar t^{51} = \bar t^{34} \times \bar t^{17}$ vaut $\bar t^3 + \bar t$, et que $\bar t^{85} = \bar t^{68} \times \bar t^{17}$ vaut $\bar t^7 + \bar t^6 + \bar t^4 + \bar t^2 + \bar t$. (3) On a $255 = 3 \times 5 \times 17$. Quel est l'ordre multiplicatif de l'élément $\bar t$ ? Est-il primitif ? (4) Donner un élément primitif de $\mathbb{F}_2[t]/(f)$, différent de $\bar t$ si on a répondu ci-dessus que $\bar t$ était primitif. Combien y en a-t-il ? (5) Quels sont les éléments $\bar\imath$ de $\mathbb{Z}/255\mathbb{Z}$ vérifiant $15\bar\imath = \bar0$ ? Quels sont les éléments de $\mathbb{F}_2[t]/(f)$ vérifiant $x^{16} = x$ ? (Cette fois-ci, on ne demande pas nécessairement de les écrire sous la forme d'un représentant standard : n'importe quelle écriture conviendra.) Combien y en a-t-il et que peut-on dire de l'ensemble de ces éléments ? (6) Trouver un élément $z$ de $\mathbb{F}_2[t]/(f)$ tel que $z^2 = \bar t$. \begin{corrige} (1) Le polynôme $f$ étant irréductible, $\mathbb{F}_2[t]/(f)$ est un corps. Son nombre d'éléments est $2^{\deg f} = 2^8 = 256$, et on le note donc généralement $\mathbb{F}_{256}$. (2a) Pour $i < 8$, il n'y a rien de mieux à écrire pour $\bar t^i$ que $\bar t^i$. On peut ensuite calculer successivement (à chaque fois on multiplie par $t$ et on soustrait le polynôme $f$ le cas échéant pour se ramener à un degré $<8$) : \begin{itemize} \item[$\bullet$]$\bar t^8 = \bar t^4 + \bar t^3 + \bar t^2 + 1$ \item[$\bullet$]$\bar t^9 = \bar t^5 + \bar t^4 + \bar t^3 + \bar t$ \item[$\bullet$]$\bar t^{10} = \bar t^6 + \bar t^5 + \bar t^4 + \bar t^2$ \item[$\bullet$]$\bar t^{11} = \bar t^7 + \bar t^6 + \bar t^5 + \bar t^3$ \item[$\bullet$]$\bar t^{12} = \bar t^8 + \bar t^7 + \bar t^6 + \bar t^4 = \bar t^7 + \bar t^6 + \bar t^3 + \bar t^2 + 1$ \item[$\bullet$]$\bar t^{13} = \bar t^8 + \bar t^7 + \bar t^4 + \bar t^3 + \bar t = \bar t^7 + \bar t^2 + \bar t + 1$ \item[$\bullet$]$\bar t^{14} = \bar t^8 + \bar t^3 + \bar t^2 + \bar t = \bar t^4 + \bar t + 1$ \item[$\bullet$]$\bar t^{15} = \bar t^5 + \bar t^2 + \bar t$ \item[$\bullet$]$\bar t^{16} = \bar t^6 + \bar t^3 + \bar t^2$ \item[$\bullet$]$\bar t^{17} = \bar t^7 + \bar t^4 + \bar t^3$ \item[$\bullet$]$\bar t^{18} = \bar t^8 + \bar t^5 + \bar t^4 = \bar t^5 + \bar t^3 + \bar t^2 + 1$ \item[$\bullet$]$\bar t^{19} = \bar t^6 + \bar t^4 + \bar t^3 + \bar t$ \item[$\bullet$]$\bar t^{20} = \bar t^7 + \bar t^5 + \bar t^4 + \bar t^2$ \end{itemize} (2b) On a calculé $\bar t^{17} = \bar t^7 + \bar t^4 + \bar t^3$, on en déduit, par application du Frobenius (c'est-à-dire en utilisant le fait que, dans $\mathbb{F}_{256}$, on a $(u+v)^2 = u^2+v^2$), que $\bar t^{34} = (\bar t^{17})^2 = \bar t^{14} + \bar t^8 + \bar t^6$ et en utilisant les valeurs de $\bar t^{14}, \bar t^8$ calculées ci-dessus, on trouve $\bar t^{34} = \bar t^6 + \bar t^3 + \bar t^2 + \bar t$. De même, en appliquant de nouveau le Frobenius, on trouve $\bar t^{68} = (\bar t^{34})^2 = \bar t^{12} + \bar t^6 + \bar t^4 + \bar t^2 = \bar t^7 + \bar t^4 + \bar t^3 + 1$. On a alors $\bar t^{51} = \bar t^{34} \times \bar t^{17} = (\bar t^6 + \bar t^3 + \bar t^2 + \bar t) \times (\bar t^7 + \bar t^4 + \bar t^3) = \bar t^{13} + \bar t^8 + \bar t^7 + \bar t^4 = \bar t^3 + \bar t$. De même, $\bar t^{85} = \bar t^{68} \times \bar t^{17} = (\bar t^7 + \bar t^4 + \bar t^3 + 1) \times (\bar t^7 + \bar t^4 + \bar t^3) = \bar t^{14} + \bar t^8 + \bar t^7 + \bar t^6 + \bar t^4 + \bar t^3 = \bar t^7 + \bar t^6 + \bar t^4 + \bar t^2 + \bar t$. (3) L'ordre de l'élément $\bar t \in \mathbb{F}_{256}^\times$ doit diviser l'ordre de ce groupe, c'est-à-dire $255 = 3\times 5 \times 17$. Il vaut l'un des entiers : $1$, $3$ $5$, $17$, $3{\times}5{=}15$, $3{\times}17{=}51$, $5{\times}17{=}85$ ou $3{\times}5{\times}17{=}255$. Or dans les questions précédentes on a calculé $\bar t^{15}, \bar t^{51}, \bar t^{85}$ et constaté qu'aucun d'entre eux ne valait $1$ (et \textit{a fortiori} pas non plus $\bar t^3$, $\bar t^5$ ou $\bar t^{17}$). On en déduit que l'ordre de $\bar t$ ne peut être que $255$, c'est-à-dire que $\bar t$ est primitif. (On dit donc que le polynôme $f$ est primitif.) Ceci prouve que le morphisme $\psi\colon \mathbb{Z}/{255}\mathbb{Z} \to \mathbb{F}_{256}^\times$ (du groupe additif des entiers modulo $255$ vers le groupe multiplicatif des éléments non nuls du corps $\mathbb{F}_{256}$) défini par $\bar\imath \mapsto \bar t^i$ est un isomorphisme. On va s'en servir dans les questions suivantes. (4) Les éléments primitifs, c'est-à-dire multiplicativement générateurs, de $\mathbb{F}_{256}^\times$, correspondent, via l'isomorphisme $\psi$, aux éléments additivement générateurs de $\mathbb{Z}/255\mathbb{Z}$, autrement dit les classes modulo $255$ des entiers premiers à $255$. Il y en a $\varphi(255) = 2\times 4 \times 16 = 128$, à savoir les $\psi(\bar\imath) = \bar t^i$ avec $i$ non multiple de $3,5,17$, et on peut donner par exemple $\bar t^2$ ou encore $\bar t^7$. (Remarque : pour répondre $\bar t^2$, on pouvait aussi invoquer l'argument suivant : le Frobenius est un isomorphisme, donc l'image par lui d'un élément primitif est encore primitif, donc $\bar t^2, \bar t^4, \bar t^8, \ldots$ sont primitifs.) (5) Dire que $15 \bar\imath = 0$ dans $\mathbb{Z}/255\mathbb{Z}$ signifie que $15 i$ est multiple de $255 = 15\times 17$, c'est-à-dire que $i$ est multiple de $17$. Autrement dit, les (quinze) $\bar\imath$ qui vérifient ceci sont : $0$, $17$, $34$, $51$, $68$, $85$, $102$, $119$, $136$, $153$, $170$, $187$, $204$, $221$ et $238$. Dire que $x^{16} = x$ dans $\mathbb{F}_{256}$ signifie que soit $x=0$ (qui vérifie bien $0^{16}=0$) soit $x^{15} = 1$ (en divisant par $x$). Dans le second cas, quitte à écrire $x = \psi(\bar\imath)$, dire $x^{15}=1$ équivaut à $15\bar\imath = \bar 0$ dans $\mathbb{Z}/255\mathbb{Z}$. Or on vient de résoudre cette équation. Les (seize) solutions de $x^{16} = x$ sont donc : $0$, $\bar t^0 = 1$, $\bar t^{17}$, $\bar t^{34}$, $\bar t^{51}$, $\bar t^{68}$, $\bar t^{85}$, $\bar t^{102}$, $\bar t^{119}$, $\bar t^{136}$, $\bar t^{153}$, $\bar t^{170}$, $\bar t^{187}$, $\bar t^{204}$, $\bar t^{221}$ et $\bar t^{238}$. L'ensemble $\{x \in \mathbb{F}_{256} : x^{16} = x\}$ forme alors un corps à $16$ éléments, qui est une copie de $\mathbb{F}_{16}$ dans $\mathbb{F}_{256}$. (6) Comme manifestement $0$ ne convient pas, on cherche $z$ tel que $z^2 = \bar t$ sous la forme $z = \psi(\bar\jmath)$. L'équation devient alors $2\bar\jmath = \bar 1$ dans $\mathbb{Z}/255\mathbb{Z}$. L'inverse de $2$ dans $\mathbb{Z}/255\mathbb{Z}$, si on ne voit pas immédiatement que c'est $128$, peut se calculer à partir d'une relation de Bézout entre $2$ et $255$ (soit : $255 = 127\times 2 + 1$ donc c'est $-127 \equiv 128 \pmod{255}$). L'unique solution de $z^2 = \bar t$ dans $\mathbb{F}_{256}$ est donc $\bar t^{128}$ (on peut calculer que c'est $\bar t^7 + \bar t^2 + 1$). (Autre solution de cette question : on sait qu'appliquer $8$ fois le Frobenius à n'importe quel élément de $\mathbb{F}_{256}$ retombe sur l'élément en question, i.e. $\Frob^8(y)=y$ pour tout $y$. Ici, on cherche à résoudre $\Frob(z) = \bar t$, et en appliquant $7$ fois le Frobenius, on voit que cela équivaut à : $\Frob^8(z) = \Frob^7(\bar t)$, soit $z = \bar t^{128}$.) \end{corrige} % % % \end{document}