\documentclass{article}
\usepackage[latin1]{inputenc}
\usepackage{fullpage}
\usepackage{amsfonts}

\newtheorem{theoreme}{Théorème}

\def\mod{~\mathrm{mod}~}
\def\Z{\mathbb{Z}}

\title{TD 1 de Cryptologie}
\date{Lundi 10 octobre 2005}

\begin{document}
\maketitle

\section{Rappels d'arithmétique modulaire}

\begin{enumerate}
\item Définitions
\item Bézout, pgcd, Euclide
\item Algorithmes sur les grands entiers
    \begin{enumerate}
    \item Addition
    \item Multiplication
    \item Exponentiation modulaire
    \item PGCD binaire
    \end{enumerate}
\item Ordre d'un élément
\end{enumerate}

\section{Fonctions à trappe}

\subsection{Restes chinois}
\begin{theoreme}
Soit $n_1, n_2, \ldots, n_k$ $k$ nombres premiers entre eux deux à
deux, alors
\begin{eqnarray*}
\varphi: \mathbb{Z}/n\mathbb{Z} & \rightarrow & \Z/n_1\Z \times \Z/n_2\Z
\times \ldots \times \Z/n_k\Z\\
x & \mapsto & (x \mod n_1, \ldots, x \mod n_k)
\end{eqnarray*}
est une bijection.
\end{theoreme}

\begin{enumerate}
\item Montrer que $\varphi$ est injective.
\item Vérifier que $\varphi$ est un morphisme.
\item Calculer $x \in [ 0, 59 ]$ tel que
\[
\begin{array}{rccl}
x & \equiv & 1 &[3]\\
x & \equiv & 3 &[4]\\
x & \equiv & 4 &[5]\\
\end{array}
\]
\end{enumerate}
\subsection{Calcul de racine troisième}
Calculer la racine troisième de $3$ modulo $n = 3211286527$ est une
opération pour laquelle la connaissance de la factorisation de $n$ est
une trappe.

En effet le calcul de racine troisième est "facile" dans un corps
fini.

\begin{enumerate}
\item On donne $n = 43573 \cdot 73699$ et
\[ 1847 \cdot 73699 - 3124 \cdot 43573 = 1\]
En déduire un inverse de $43573$
modulo $73699$, et un inverse de $73699$ modulo $43573$.

\item L'équation $x^3 = 3$ admet trois solutions $39165$, $42225$ et
$5756$ modulo $43573$, et trois solutions $40608$, $65677$ et $41113$
modulo $73699$. Combien l'équation a-t-elle de solutions modulo $n$ ?

\item Calculer deux de ces solutions.
\end{enumerate}

\section{Recherche de générateur}

\begin{enumerate}

\item On suppose $p$ premier de la forme $p = 2q + 1$ où $q$ est
premier. Que devient le calcul de l'ordre d'un élément de
$(\Z/p\Z)^{*}$~? Combien y a-t-il de générateurs~? Quel est le temps
moyen de recherche d'un générateur~?
\end{enumerate}

\end{document}