diff options
| -rw-r--r-- | controle-20121127.tex | 127 |
1 files changed, 127 insertions, 0 deletions
diff --git a/controle-20121127.tex b/controle-20121127.tex new file mode 100644 index 0000000..e030222 --- /dev/null +++ b/controle-20121127.tex @@ -0,0 +1,127 @@ +%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? +\documentclass[12pt]{article} +\usepackage[francais]{babel} +\usepackage[utf8]{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}} +\DeclareUnicodeCharacter{00A0}{~} +% +\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{27 novembre 2012} +\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 : 2h + +\newpage + +% +% +% + +\exercice + +La décomposition en facteurs premiers de $65\,535$ est : $3 \times 5 +\times 17 \times 257$. + +(1a) Soit $x$ un entier : que vaut $x^{256}$ modulo $p = 257$ ? (On +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$.) + +(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é). + +(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$ ? + +(3) Que vaut $\varphi(65\,535)$ ? + +(4) Comparer le résultat de la question (2) à l'énoncé du théorème +d'Euler modulo $65\,535$. + +(5) Montrer que $x^{257} \equiv x \pmod{p}$ pour tout entier $x$ et +pour tout $p \in \{3,5,17, 257\}$. + +(6) En déduire que $x^{257} \equiv x \pmod{65\,535}$ pour tout +entier $x$. + +(7) Rappeler pourquoi il existe des éléments de +$(\mathbb{Z}/257\mathbb{Z})^\times$ dont l'ordre multiplicatif vaut +exactement $256$. + +(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 +$(\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$. + +(9) En déduire l'ordre multiplicatif maximal possible d'un élément de +$(\mathbb{Z}/65535\mathbb{Z})^\times$. + +(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}$.) + +% +% +% +\end{document} |