%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? \documentclass[12pt]{article} \usepackage[francais]{babel} \usepackage[latin1]{inputenc} \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{Fr}} % % % \begin{document} \title{INFMDI720\\Contrôle de connaissance\\{\normalsize Rappels mathématiques pour la cryptographie}} \author{} \date{2 décembre 2008} \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. À l'intérieur d'un exercice, les questions se suivent normalement dans un ordre logique, et il est vivement recommandé de les traiter dans cet ordre. Le sujet étant volontairement trop long pour le temps imparti, il ne sera pas nécessaire de traiter tous les exercices pour avoir le maximum des points. Il est suggéré de prendre le temps de tous les lire, pour bien choisir ceux que l'on traitera. 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ée. L'usage des calculatrices électroniques est interdites. (Certains exercices peuvent apparaître calculatoires, mais les calculs sont toujours faisables à la main en un temps raisonnable, parfois au prix de quelques astuces.) Durée : 1h30 \newpage % % % \exercice Les deux questions suivantes sont indépendantes. (1) Montrer que $a^{31} \equiv a \pmod{341}$ pour tout $a \in \mathbb{Z}$ (note : on a $341 = 11\times 31$). (2) Pourquoi a-t-on $a^{32} \equiv 1 \pmod{128}$ pour tout $a$ impair (note : $128 = 2^7$) ? % % % \exercice Le calendrier religieux maya (ou Tzolkin) est la combinaison de deux cycles indépendant, l'un de $13$ jours numérotés de 1 à 13, l'autre de $20$ jours portant des noms de dieux (dans l'ordre : « Ahau », « Imix », « Ik », « Akbal », « Kan », « Chicchan », « Cimi », « Manik », « Lamat », « Muluc », « Oc », « Chuen », « Eb », « Ben », « Ix », « Men », « Cib », « Caban », « Etznab » et « Caunac »). Ces deux cycles sont complètement indépendants, c'est-à-dire que si un jour est numéroté « 11 Ahau », le lendemain sera « 12 Imix », puis « 13 Ik », puis « 1 Akbal », « 2 Kan » et ainsi de suite jusqu'à « 4 Caunac » auquel suit « 5 Ahau », etc. Il n'existe aucune irrégularité. (1) Quelle est le nombre de jours d'un cycle du Tzolkin ? Autrement dit, au bout de combien de jours après un jour donné retombe-t-on pour la première fois sur un jour ayant le même numéro et le même nom ? (2) Sachant que le 2 décembre 2008 est dénommé « 6 Ahau », déterminer quand aura lieu le prochain jour « 10 Oc » au calendrier religieux maya. (3) Les Mayas utilisaient également un calendrier civil (ou Haab) de $365$ jours exactement\footnote{Ce calendrier était lui-même organisé en mois, mais cela ne nous importe pas ici.}, qui se répétait lui aussi sans irrégularité, et complètement indépendamment du calendrier religieux Tzolkin. Quelle est la longueur approximative en années d'un cycle complet des deux calendriers ? Autrement dit, combien d'années faut-il attendre approximativement, à partir d'un jour donné, pour retrouver pour la première fois un jour ayant la même dénomination dans les deux calendriers (Tzolkin et Haab) à la fois ? % % % \exercice Soit $n = 2^{100}$ et $N = 2^n = 2^{2^{100}}$. (1) Quel est le reste de la division euclidienne de $n$ par $3$ et par $5$ ? % Réponses : 1, 1 (2) Quel est le reste de la division euclidienne de $n$ par $6$, par $10$ et par $4$ ? % Réponses : 4, 6, 0 (3) Quel est le reste de la division euclidienne de $N$ par $9$, par $11$ et par $10$ ? % Réponses : 7, 9, 6 (4) Quel est le reste de la division euclidienne de $N$ par $99$ ? Par $990$ ? % Réponses : 97, 196 % % % \exercice Une conjecture affirme que pour tout entier $n$ il existe $n' \neq n$ tel que $\varphi(n') = \varphi(n)$ (où $\varphi$ désigne la fonction indicatrice d'Euler). On va voir qu'on peut montrer cette conjecture au moins pour les petites valeurs de $n$. (1a) Si $n$ est impair, montrer que $\varphi(2n) = \varphi(n)$. (1b) Si $n$ est pair mais non multiple de $4$, montrer que $\varphi(\frac{1}{2}n) = \varphi(n)$. (1c) Si $n$ est multiple de $4$ mais non de $12$, montrer que $\varphi(\frac{3}{2}n) = \varphi(n)$. (1d) Si $n$ est multiple de $12$ mais non de $36$, montrer que $\varphi(\frac{2}{3}n) = \varphi(n)$. (1e) Si $n$ est multiple de $36$ mais non de $7\times 36 = 252$, montrer que $\varphi(\frac{7}{6}n) = \varphi(n)$. (1f) Si $n$ est multiple de $7\times 36 = 252$ mais non de $7^2\times 36 = 1764$, montrer que $\varphi(\frac{6}{7}n) = \varphi(n)$. (2) En continuant selon la même logique, montrer que la conjecture énoncée plus haut est valable lorsque $n$ n'est pas multiple de $(6\times 7 \times 43)^2$. (3) Si $n$ est multiple de $(6\times 7 \times 43)^2$ mais ni de $27$ ni de $13$, montrer que $\varphi(\frac{13}{18}n) = \varphi(n)$. (4) Sachant que $(6\times 7 \times 43)^2 \geq 3\times 10^6$, jusqu'à combien les questions précédentes permettent-elles d'affirmer la véracité de la conjecture ? % % % \exercice Cet exercice décrit le principe l'algorithme de factorisation « $p-1$ » de Pollard. \emph{Définition :} On dit qu'un entier naturel $m$ est « $B$-friable » (pour $B$ un entier naturel) lorsque tout facteur premier $\ell$ de $m$ est $\leq B$. (Par exemple, $720$ est $5$-friable.) (1) Soit $p$ un nombre premier tel que $p-1$ soit $B$-friable (pour une certaine borne $B$). Soient $\ell_1,\ldots,\ell_k$ les nombres premiers $\leq B$. Partant de $a \in (\mathbb{Z}/p\mathbb{Z})^\times$, on effectue les opérations suivantes : pour $i$ allant de $1$ à $k$, on remplace $a$ par $a^{\ell_i^{r_i}}$ (ce calcul étant fait dans $\mathbb{Z}/p\mathbb{Z}$), où $r_i$ est un entier supérieur ou égal à $\log(p)/\log(\ell_i)$. Quel est le résultat obtenu (autrement dit, que vaut $a$ après ces différentes opérations) ? \emph{Indication :} montrer qu'on a élevé $a$ à une puissance d'exposant multiple de $p-1$. \smallskip On suppose maintenant que $N$ est un entier non premier à factoriser, et on espère qu'un de ses facteurs premiers $p$ est tel que $p-1$ soit $B$-friable avec $B$ assez petit. (Naturellement, on ne sait pas ce que vaut $p$ : on cherche justement à le calculer ou, du moins, à trouver une factorisation non triviale $N = d d'$ avec $d,d'>1$.) L'algorithme $p-1$ de Pollard effectue le calcul suivant, en partant d'un nombre $N$ à factoriser et d'une borne $B$ de friabilité (typiquement de l'ordre de $10^6$) : \begin{itemize} \item tirer au hasard un entier $a$ entre $2$ et $N-2$ ; \item calculer $\pgcd(a,N)$ : s'il est $>1$, terminer : ($*$) on a trouvé une factorisation non triviale de $N$ ; \item énumérer les nombres premiers $\ell_1,\ldots,\ell_k$ inférieurs ou égaux à $B$ ; \item pour $i$ allant de $1$ à $k$ : \begin{itemize} \item soit $r \geq \log(N)/\log(\ell_i)$ entier, \item faire $a \leftarrow a^{\ell_i^r}$ dans $\mathbb{Z}/N\mathbb{Z}$ ; \end{itemize} \item calculer $d = \pgcd(a-1,N)$ ; \item si $1