From 3c42fa94b6b0379076e2c7d463b98ef41340bc08 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Tue, 8 Nov 2011 11:43:18 +0100
Subject: Another exercise.

---
 exercices2b.tex | 103 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 103 insertions(+)
 create mode 100644 exercices2b.tex

(limited to 'exercices2b.tex')

diff --git a/exercices2b.tex b/exercices2b.tex
new file mode 100644
index 0000000..656c670
--- /dev/null
+++ b/exercices2b.tex
@@ -0,0 +1,103 @@
+%% 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}
-- 
cgit v1.2.3