\documentclass[10pt,a4paper]{article}
\parindent=0cm
 \pagestyle{empty}
   \textheight=23,5cm
   \textwidth=18cm
\oddsidemargin=0cm
\usepackage{amsmath,amssymb,amsthm,epsfig}
\usepackage[frenchb]{babel}
\usepackage[latin1]{inputenc}
\usepackage{graphicx}
\usepackage{tikz} 
\usepackage{textcomp}
\newcommand{\C}{\mathbb C}
\newcommand{\R}{\mathbb R}
\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\Q}{\mathbb Q}
\newcommand{\CC}{{\cal C}}
\newcommand{\espmes }{(\Omega, {\cal F})}
\newcommand{\espprob}{(\Omega, {\cal F}, P)}
\newcommand{\va}{variable al\'eatoire }
\newcommand{\vas}{variables al\'eatoires }
\newcommand{\Vas}{Variables al\'eatoires }
\newcommand{\cov}{\hbox{cov}}


\newtheorem{theo}{Th\'eor\`eme}[section]
\newtheorem{coro}{Corollaire}[section]
\newtheorem{lemm}{Lemme}[section]
\newtheorem{defi}[theo]{D\'efinition}
\newtheorem{prop}[theo]{Proposition}
\newtheorem{rque}[theo]{Remarque}
\newtheorem{exem}[theo]{Exemple}
\newtheorem{exer}[theo]{Exercice}
\def\card{\mathrm{card}\,}

\newcommand{\tran}[1]{\,{}^{t}\!#1}
\renewcommand\det{\mathop{\textrm{d\'et}}}
\newcommand{\exergue}[2]{\vspace*{-2ex}
\begin{flushright}\begin{em}
\og #1\fg\ #2\end{em}\end{flushright}\medskip}
\renewcommand{\le}{\leqslant}
\renewcommand{\ge}{\geqslant}
 \def\demi{\frac{1}{2}}
\def\ds{\displaystyle}
\def\btheo{\begin{theo}}\def\etheo{\end{theo}}
\def\bcoro{\begin{coro}}\def\ecoro{\end{coro}}
\def\blemm{\begin{lemm}}\def\elemm{\end{lemm}}
\def\bdefi{\begin{defi}}\def\edefi{\end{defi}}
\def\bprop{\begin{prop}}\def\eprop{\end{prop}}
\def\brque{\begin{rque}}\def\erque{\end{rque}}
\def\bexem{\begin{exem}}\def\eexem{\end{exem}}
\def\bexer{\begin{exer}\begin{em}}\def\eexer{\end{em}\end{exer}}
\def\F{{\cal F}}
\def\1{{\rm 1\kern-.8ex 1}}

\begin{document}

\noindent MAT309  \hfill
Universit\'e Grenoble Alpes\\
\noindent 2020-2021 \\



\begin{center}
\textsc{\large Partiel du 12/11/2020}

\medskip
{\em Ordinateurs et portables interdits. Calculatrice autoris\'ee. Feuille
recto-verso A4 manuscrite autoris\'ee.\\
Toutes les r\'eponses doivent \^etre justifi\'ees et la qualit\'e de
la r\'edaction sera prise en compte.\\
Certaines r\'eponses aux exercices 1 et 2 doivent \^etre report\'ees sur la
feuille de r\'eponse.\\
Le bar\^eme tiendra compte de la longueur du sujet.}


\end{center}
\vspace{0,7cm}
\begin{center}
 Tableau de correspondance
\end{center}
{\footnotesize


\begin{center}
\begin{tabular}[c]{|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|}\hline
A &B &C  & D & E & F & G & H & I & J & K & L & M & N & O & P & Q & R & S & T & U & V & W & X & Y &Z\\\hline
0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 &24 &25 \\\hline
\end{tabular}
\end{center}}


\noindent\textbf{Exercice \no 1}
Un d\'ecalage de C\'esar d'ordre $k$ o\`u $0\leq k\leq 25$ est la m\'ethode de chiffrement consistant \`a d\'ecaler chaque lettre de l'alphabet de $k$ positions en suivant une permutation circulaire des lettres.

\begin{enumerate}
 \item Chiffrer le mot {\bf DLST} en utilisant un d\'ecalage de C\'esar d'ordre 9.
 \item D\'echiffrer le mot {\bf PYEBSOB} sachant que le mot initial a \'et\'e chiffr\'e par un d\'ecalage d'ordre 10.
 \item Les chiffrements pr\'ec\'edents \'etant trop simples \`a casser, on propose le chiffrement suivant. On choisit une cl\'e qui sera dans notre cas le mot {\bf COVID}.
 
 La premi\`ere lettre du texte \`a chiffrer sera modifi\'ee en
 utilisant le d\'ecalage de C\'esar qui envoie A sur C
(o\`u C est la premi\`ere lettre de la cl\'e COVID), 
la deuxi\`eme par le d\'ecalage de C\'esar qui envoie A sur O, 
la troisi\`eme par le d\'ecalage de C\'esar qui envoie A sur V, la
quatri\`eme par le d\'ecalage de C\'esar qui envoie A sur I, la
cinqui\`eme par le d\'ecalage de C\'esar qui envoie A sur D, la
sixi\`eme par le d\'ecalage de C\'esar qui envoie A sur C (on
recommence au d\'ebut de la cl\'e), etc, ...
 
 \begin{enumerate}
  \item 
 
     Chiffrer la phrase {\bf J AIME MON MASQUE LAVABLE} par cette
     m\'ethode (sans tenir compte des espaces).
 
 \item On note \verb|T[i]| l'entier donn\'e par le tableau de
   correspondance pour la lettre d'indice $i$ du texte \`a chiffrer,
   \verb|C[i]| l'entier donn\'e par le tableau de la lettre d'indice $i$ de la
   cl\'e et \verb|CH[i]| l'entier  donn\'e par le tableau de la lettre
   d'indice $i$ du texte chiffr\'e. On utilise des indices
   commen\c{c}ant \`a 0.
 
 Comment obtient-on la liste des \verb|CH[i]| \`a partir de la liste des
 \verb|T[i]| et de la liste 
\verb|[C[0],C[1],|$\cdots$\verb|,C[4]]| ?
 
 \item Combien de chiffrements diff\'erents peut-on obtenir avec des cl\'es de 5 lettres ?
 
 \item Quelle(s) m\'ethode(s) peut-on utiliser pour casser un tel chiffrement si on ne connait pas la cl\'e~?
 
 \item \'Ecrire un algorithme en langage naturel 
% ou un programme   Python 
qui \`a un texte (compos\'e uniquement des lettres A \`a Z) et une
   cl\'e associe le texte chiffr\'e par la m\'ethode pr\'ec\'edente.
   On supposera que
\begin{itemize}
\item le caract\`ere d'indice $i$
   d'une chaine de caract\`ere \verb|s| est \verb|s[i]|,
  avec des indices commen\c{c}ant \`a 0,
\item la fonction \verb|len(s)| renvoie la longueur de la chaine \verb|s|
\item la fonction \verb|ord(c)|
convertit un caract\`ere \verb|c| en entier 
\item la fonction \verb|chr(n)| convertit un entier \verb|n|
en caract\`ere
\end{itemize}
\end{enumerate}
\end{enumerate}

\noindent\textbf{Exercice \no 2}

On rappelle qu'en base 16 les chiffres sont donn\'es par \verb|0,1,|$\cdots$\verb|9,A,B,C,D,E,F|.
\begin{enumerate}
 \item Convertir tous les nombres du tableau de correspondance en base 2.
 \item On d\'ecide alors de coder un texte en rempla\c{c}ant chacune de ses lettres par le nombre correspondant \'ecrit en base deux.
 
 Ainsi par exemple {\bf INF} devient \verb|1000 1101 101|
 
 En enlevant les espaces, on obtient un entier \'ecrit en base 2, ici
 \verb|0b10001101101|, que l'on recode en base 16, soit ici \verb|0x46D|.
 
 Chiffrer de cette mani\`ere le mot {\bf COVID}. 
 
 Proposer un autre mot ayant le m\^eme chiffrement.
 
 \item Pour corriger le d\'efaut de la m\'ethode pr\'ec\'edente on
   \'ecrit tous les nombres de 0 \`a 25 en base 2 avec 5 bits (en
   ajoutant des 0 au d\'ebut si n\'ecessaire). On le convertit ensuite en base 16.
 
 Chiffrer de cette mani\`ere le mot {\bf COVID}.
 
 \item  
 Notons $n$ le chiffrement du mot COVID obtenu à la question
 précédente. Donner le quotient et le reste, en base 16, de la
 division euclidienne de $n$ par 6. On utilisera l'algorithme de la
 potence. 
Pour s'aider, on pourra écrire la table de multiplication par 6 en base 16.
 
\end{enumerate}
\noindent\textbf{Exercice \no 3}

\begin{enumerate}
 \item Montrer que 2020 et 33 sont premiers entre eux et donner l'identit\'e de B\'ezout. On d\'etaillera les calculs en utilisant l'algorithme d'Euclide \'etendu.
 
 \item D\'eterminer tous les couples d'entiers $(x,y)$ tels que $2020x-33y=3$.
 
 \item Existe t-il des entiers $x$ positifs et plus petit que 20000
   tels que le reste de la dision euclidienne de 
$x$ par 33 soit 1 et le reste de la dision euclidienne de 
$x$ par 2020 soit 4 ? Si oui, donner toutes les solutions.
\end{enumerate}

\noindent\textbf{Exercice \no 4}

\begin{enumerate}
 \item D\'eterminer le reste de la division euclidienne de $2020^{873}$ par 14. La m\'ethode doit \^etre explicit\'ee.
 \item Donner la liste des inversibles de $\Z\textfractionsolidus14\Z$.
 \item R\'esoudre l'\'equation dans $\Z\textfractionsolidus14\Z$, $\overline{11}x=\overline{3}$.
\end{enumerate}

\noindent\textbf{Exercice \no 5}
On consid\`ere l'\'equation suivante : 
\[(*)\ \ \ \ \ \ \ \ x^2-13y^2=7\].
On suppose dans les questions 1 et 3 que $(x,y)$ est un couple d'entiers v\'erifiant $(*)$.
\begin{enumerate}
 \item 
 Montrer que $x^2+y^2\equiv0\ [7]$
 \item Calculer les carr\'es de tous les \'el\'ements de $\Z\textfractionsolidus7\Z$.
 \item En d\'eduire que $x$ et $y$ sont multiples de 7.
\item  $(*)$ a-t-elle des solutions~?
Indication: si c'est le cas,  il existe des entiers $a$ et $b$ tels que~:
$$ x=7a, y=7 b$$
\end{enumerate}

\end{document}