%% 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}