%% 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}
\makeatletter\relax\let\Square\@undefined\relax\makeatother
\usepackage{bbding}
\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}}
\newcommand{\dothis}{\leavevmode\hbox to0pt{\hskip-\parindent\HandRight{}\hskip0ptplus1fil}}
\DeclareUnicodeCharacter{00A0}{~}
%
%
%
\begin{document}
\title{INFMDI720\\Exercices\\{\normalsize Rappels mathématiques pour la cryptographie}}
\author{}
\date{}
\maketitle
\pretolerance=10000
\tolerance=8000

%
%
%

\setcounter{comcnt}{4}

\exercice

On admet que le polynôme $P(t) = t^8+t^4+t^3+t+1 \in \mathbb{F}_2[t]$
et irréductible.  On pose $F = \mathbb{F}_2[t]/(P)$.

On fait la convention suivante : un élément $a_0 + a_1 \bar t + \cdots
+ a_7 \bar t^7$ de $F$, où $a_0,\ldots,a_7 \in \{0,1\}$ sera
« représenté » par l'entier $a_0 + a_1 \times 2 + \cdots + a_7 \times
2^7$ entre $0$ et $255$.

\dothis Expliquer pourquoi cette convention a bien
un sens.

\dothis Avec cette convention, quels sont par exemple les entiers
représentant les éléments $\bar t$ et $\bar t^7 + \bar t^6 + \bar t^5
+ \bar t^4 + \bar t^3 + \bar t$ ?

\dothis Inversement, quels éléments de $F$ sont représentés par les
entiers $31$ et $64$ ?

On appelle $\oplus$ et $\otimes$ les opérations définies sur les
entiers entre $0$ et $255$ qui correspond aux opérations $+$ et
$\times$ sur $F$ (autrement dit : $a\oplus b$ est l'entier qui
représente la somme dans $F$ des éléments représentés par $a$ et $b$,
et de même $a\otimes b$ pour le produit ; ces opérations font donc de
$\{0,\ldots,255\}$ un corps isomorphe à $F$, puisqu'il s'agit juste
d'une représentation différente de la même chose).

\dothis Calculer par exemple $7\oplus 11$, puis $4\otimes 4$, et enfin
$141 \otimes 2$.

\dothis Expliquer pourquoi l'opération $\oplus$ est, sur les entiers
de 8 bits, l'opération \texttt{XOR} de « ou exclusif » (c'est-à-dire
l'opération calculée bit à bit par les règles : $\mathtt{XOR}(0,0) =
0$, $\mathtt{XOR}(0,1) = \mathtt{XOR}(1,0) = 1$ et $\mathtt{XOR}(1,1)
= 0$).  Le polynôme $P$ a-t-il joué un rôle ici ?

\dothis En distinguant les deux cas $x<128$ et $x\geq 128$, donner une
expression générale de $2 \otimes x$ (qui pourra utiliser l'opération
$\oplus$ de « ou exclusif »).  Expliquer où le polynôme $P$ a joué un
rôle.

\dothis Écrire une fonction (dans un langage de programmation
quelconque) qui calcule $2 \otimes x$ en fonction de $x$.

\dothis Utiliser cette fonction, et notamment la distributivité
$\otimes$ sur $\oplus$, pour écrire une fonction calculant $x \otimes
y$ en général.

\dothis Calculer $250 \otimes 250$.

%
%
%
\end{document}