From 7d67681735428e1aa4da3be51fc85ed337f15d42 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Tue, 13 Nov 2012 19:10:11 +0100
Subject: Start writing test for 2012.  Not really happy about this exercise.

---
 controle-20121127.tex | 127 ++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 127 insertions(+)
 create mode 100644 controle-20121127.tex

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}
-- 
cgit v1.2.3