%% 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}$.)

%
%
%

\exercice

Soit $f = t^8 + t^4 + t^3 + t^2 + 1 \in \mathbb{F}_2[t]$.  On admet
que ce polynôme est irréductible.  On pose $E = \mathbb{F}_2[t]/(f)$.

(1) Combien d'éléments $E$ a-t-il ?  Combien d'éléments $E^\times$ (le
groupe des inversibles de $E$) a-t-il ?

On désignera par $\alpha \in E$ (plutôt que $\bar t$) la classe de $t$
modulo $f$.

(2) Que peut-on dire \textit{a priori} de l'ordre multiplicatif
de $\alpha$ ?  C'est-à-dire : quelles sont les valeurs \textit{a
  priori} possibles ?  (Remarque : $255 = 3 \times 5 \times 17$.)

(3) Calculer les valeurs de $\alpha^i$ dans $E$ (c'est-à-dire la
classe de $t^i$ modulo $f$) pour $i \leq 17$.

Pour permettre de vérifier les calculs, on donne le dernier résultat :
$\alpha^{17} = \alpha^7 + \alpha^4 + \alpha^3$.  On notera aussi
$\beta$ cet élément $\alpha^{17} \in E$.

(4) Calculer de même les valeurs de $\alpha^i$ les valeurs suivantes
de $i$ : $34$, $51$, $68$ et $85$ (c'est-à-dire les multiples de $17$
jusqu'à $85$ inclus) ; si l'on préfère, ce sont les premières
puissances de $\beta$.

Pour permettre de vérifier les calculs, on donne le dernier résultat :
$\alpha^{85} = \alpha^7 + \alpha^6 + \alpha^4 + \alpha^2 + \alpha$.

(5) Que vaut l'ordre multiplicatif de $\alpha$ ?  Quel est l'ordre
multiplicatif de $\beta = \alpha^{17}$ ?

(6) Que vaut $\beta^{16}$ ?

(7) Vérifier que $\beta^4 + \beta + 1 = 0$.

On pose $g = t^4 + t + 1 \in \mathbb{F}_2[t]$, et $K =
\mathbb{F}_2[t]/(g)$.

On appelle $\Phi\colon \mathbb{F}_2[t] \to E$ l'application $P \mapsto
P(\beta)$ qui à un polynôme $P \in \mathbb{F}_2[t]$ associe la valeur
de celui-ci en $\beta$.  Par exemple, la question (7) signifie que
$\Phi(g) = 0$.

(8) (a) Expliquer pourquoi $\Phi(h_1 + h_2) = \Phi(h_1) + \Phi(h_2)$
et $\Phi(h_1 h_2) = \Phi(h_1)\, \Phi(h_2)$ pour tous $h_1,h_2 \in
\mathbb{F}_2[t]$.  (b) Montrer que $\Phi(h) = \Phi(h')$ si $h \equiv
h' \pmod{g}$.

(9) Déduire de (8b) qu'on peut définir une application $\varphi \colon
K \to E$ qui envoie la classe (modulo $g$) d'un polynôme $h \in
\mathbb{F}_2[t]$ sur $\Phi(h) \in E$.  Déduire de (8a) que
$\varphi(u_1 + u_2) = \varphi(u_1) + \varphi(u_2)$ et $\varphi(u_1
u_2) = \varphi(u_1) \, \varphi(u_2)$ pour tous $u_1,u_2 \in K$.
Comment qualifie-t-on $\Phi$ et $\varphi$ ?

On désignera par $\gamma \in K$ (plutôt que $\bar t$) la classe de $t$
modulo $g$.  Ainsi, on a $\varphi(\gamma) = \beta$ (puisque $\Phi(t) =
\beta$).

(10) Montrer que le cardinal de l'image de $\varphi$, autrement dit,
le nombre de valeurs distinctes atteintes par $\varphi$, vaut au
moins $16$.  (On pourra, par exemple, dire ce que vaut
$\varphi(\gamma^i)$ et compter toutes les valeurs ainsi atteintes,
sans oublier d'ajouter $\varphi(0)$.)  En déduire que $\varphi$ est
injective (=deux éléments distincts de $K$ ont toujours des images
distinctes dans $E$), et que le polynôme $g$ est irréductible.

%
%
%
\end{document}