%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
\documentclass[12pt]{article}
\usepackage[francais]{babel}
\usepackage[latin1]{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{Fr}}
%
\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{23 novembre 2010}
\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.

Le sujet étant volontairement trop long pour le temps imparti, il ne
sera pas nécessaire de traiter tous les exercices pour avoir le
maximum des points.  Il est suggéré de prendre le temps de tous les
lire, pour bien choisir ceux que l'on traitera.

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.  (Certains
exercices peuvent apparaître calculatoires, mais les calculs sont
toujours faisables à la main en un temps raisonnable, parfois au prix
de quelques astuces.)

Durée : 1h30

\newpage

%
%
%

\exercice

(A) Quel entier entre $1500$ et $2500$ est congru à $36$ modulo $47$
et à $49$ modulo $53$ ?

(B) Quel est le plus petit entier naturel multiple de $9$ et de $11$
et congru à $6$ modulo $10$ ?

(C) Quels sont les entier entre $0$ et $100$ congrus à $6$ modulo $18$
et à $15$ modulo $27$ ?

(D) Quels sont les entier entre $0$ et $9000$ congrus à $18$
modulo $91$ et à $24$ modulo $105$ ?

%
%
%

\exercice

On a $561 = 3\times 11\times 17$.

(1) Montrer que $n^{561} \equiv n \pmod{3}$ pour tout entier $n$, et
de même $\mathop{\mathrm{mod}} 11$ et $\mathop{\mathrm{mod}} 17$.
(Indication : la réponse à cette question doit faire intervenir le
nombre $560$ et \emph{non pas} la factorisation de $561$ donnée
ci-dessus.)

(2) En déduire que $n^{561} \equiv n \pmod{561}$ pour tout entier $n$.

%
%
%

\exercice

On admet que le polynôme suivant dans $\mathbb{F}_2[t]$ est
irréductible : $f := t^8 + t^4 + t^3 + t^2 + 1$.

(1) Quel est le nombre d'éléments de $\mathbb{F}_2[t]/(f)$ ?  Que
peut-on en dire et comment a-t-on l'habitude de le noter ?

(2) Dans $\mathbb{F}_2[t]/(f)$, calculer les puissances $\bar t^i$ de
l'élément $\bar t$ représenté par $t$, pour $i$ allant de $0$ à $20$
inclus.  (Ici, « calculer » sous-entend qu'on demande comme d'habitude
le représentant standard, c'est-à-dire celui donné par un polynôme de
degré $<\deg f$.)

(3) On a $255 = 3 \times 5 \times 17$.  L'élément $\bar t$ est-il
primitif ?  Si non, quel est son ordre multiplicatif ?  Si oui,
comment qualifie-t-on le polynôme $f$ du fait de cette propriété ?

(4) Donner un élément primitif de $\mathbb{F}_2[t]/(f)$, différent de
$\bar t$ (si on a répondu ci-dessus que $\bar t$ était primitif).
Combien y en a-t-il ?

(5) Quels sont les éléments $\bar\imath$ de $\mathbb{Z}/255\mathbb{Z}$
vérifiant $15\bar\imath = \bar0$ ?  Quels sont les éléments de
$\mathbb{F}_2[t]/(f)$ vérifiant $x^{16} = x$ ?  (Cette fois-ci, on ne
demande pas nécessairement de les écrire sous la forme d'un
représentant standard : n'importe quelle autre écriture conviendra.)
Combien y en a-t-il et que peut-on dire de l'ensemble de ces
éléments ?

%
%
%
\end{document}