\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}}
 \newcommand{\hs}{\hspace{1cm}}
 \newcommand{\hsp}{\hspace{0.4cm}}


\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
Corrig\'e partiel novembre 2020
\hfill 2020-2021 \\




\noindent\textbf{Exercice \no 1}

\begin{enumerate}
 \item MUBC
 \item FOURIER
 \item 
 \begin{enumerate}
  \item 
JAIME+COVID=LODUH,\\
MONMA+COVID=OCIUD,\\
SQUEL+COVID=UEPMO,\\
AVABL+COVID=CJVJO,\\
E+C=G  
 
 \item {\em 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]]| ?}\\
\verb|CH[i]=(T[i]+C[i%5])%26|
 
 \item {\em Combien de chiffrements diff\'erents peut-on obtenir avec des cl\'es de 5 lettres ?}\\
 26 choix possibles pour chaque lettre donc $26^5=11881376$ choix.
 \item {\em Quelle(s) m\'ethode(s) peut-on utiliser pour casser un tel
     chiffrement si on ne connait pas la cl\'e}~?\\
Si on sait que la clef est de longueur 5 et le message assez long, on
peut faire une analyse statistique des lettres d'indice 0 modulo 5,
puis 1 modulo 5, etc. pour retrouver chaque lettre de la clef.
On peut aussi faire une attaque par force brute en testant toutes les
clefs possibles (un peu plus de 11 millions de possibilit\'es).
Si on ne connait pas la longueur de la clef, on peut
 essayer une attaque statistique ou par force brute
en testant pour une clef de 1 lettre, puis de 2 lettres, puis de 3
 lettres, etc. L'attaque par force brute ne peut s'envisager que pour
 une clef d'au plus une douzaine de lettres.
 \item {\em \'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}}
\begin{verbatim}
fonction codage d'arguments msg,cle
l <- len(cle)
n <- len(msg)
msgcode <- msg
pour j de 0 jusque n-1 faire
  msgcode[j]=chr((ord(msg[j])+ord(cle[j%l]))%26)
renvoyer msgcode
\end{verbatim}
Code Python/Xcas correspondant (un peu plus compliqu\'e car les
caract\`eres ne commencent pas \`a 0)~:
\begin{verbatim}
def code(msg,cle):
    l=len(cle)
    n=len(msg)
    msgcode=""
    for j in range(n):
        msgcode += chr((ord(msg[j])-ord("A")+ord(cle[j%l])-ord("A"))%26 +ord("A"))
    return msgcode
\end{verbatim}
On teste~: \verb|code("JAIMEMONMASQUELAVABLE","COVID")|
renvoie LODUHOCIUDUEPMOCJVJOG.
\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 \verb|0,0b1,0b10,0b11, 0b100, 0b101, 0b110, 0b111|, etc.
 \item 
{\em Chiffrer de cette mani\`ere le mot {\bf COVID}.} \\
\verb|10 1110 10101 1000 11| soit en groupant par quatre
\verb|1 0111 0101 0110 0011=0x17563|
 
{\em Proposer un autre mot ayant le m\^eme chiffrement.}\\
Par exemple \verb|101 110 10101 1000 11| soit {\bf FGVID}
 
 \item {\em 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}.\\
 \verb|00010 01110 10101 01000 00011| soit \verb|0x275503|
 \item  {\em 
 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.}\\
\begin{tabular}[c]{|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|}\hline
&\hsp 1 & \hsp  2 & \hsp  3 & \hsp  4 & \hsp  5 & \hsp  6 & \hsp  7 & \hsp  8 & \hsp  9 & \hsp  A & \hsp  B & \hsp  C & \hsp  D & \hsp  E & \hsp  F\\\hline
*6 & 6 & c & 12 & 18 & 1e & 24 & 2a&30 & 36 & 3c & 42 & 48 & 4e & 54 & 5a\\\hline
\end{tabular}

\begin{verbatim}
 275503 | 6
-24     |--------
---     | 68e2b
  35    | 
 -30    |
 ---    |
   55   |
  -54   |
  ---   |
    10  |
    -c  |
    --  |
     43 |
    -42 |
    --- |
      1 |
\end{verbatim}
On obtient quotient \verb|0x68e2b|, reste 1.
\end{enumerate}
\noindent\textbf{Exercice \no 3}

\begin{enumerate}
 \item {\em 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.}
\\ 
\verb|L0        2020   1    0|\\
\verb|L1          33   0    1|\\
\verb|L2=L0-61L1   7   1  -61|\\
\verb|L3=L1-4L2    5  -4  245|\\
\verb|L4=L2-L3     2   5 -306|\\
\verb|L5=L3-2L4    1 -14  857|\\
Donc \verb|-14*2020+857*33=1| 
 \item {\em D\'eterminer tous les couples d'entiers $(x,y)$ tels que
   $2020x-33y=3$}.\\
on multiplie par -3 l'identit\'e de B\'ezout pour avoir une solution
particuli\`ere $x=-42, y=-2571$ et on utilise que 2020 et
33 sont premiers entre eux pour avoir la solution g\'en\'erale
 $x=-42+33k, y=-2571+2020k$
 \item {\em 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.}\\
Comme 33 et 2020 sont premiers entre eux, $x$ existe parmi les
entiers, mais pas forc\'ement entre 0 et 20000. 
Comme la longueur de l'intervalle des $x$ possibles est 20001 qui est plus petit que
$2020\times 33$, il y aura 0 ou 1 solution, on ne peut pas le
savoir sans faire le calcul pr\'ecis.\\
On a $x=1+33v=4+2020u$ donc $-2020u+33v=4-1=3$
dont on a calcul\'e des solutions (au signe pr\`es) juste avant, par exemple $v=2571$
On a donc une solution particuli\`ere $x=1+33\times 2571=84844$
et la solution g\'en\'erale $x=84844+2020\times 33  k$. Reste \`a
d\'eterminer $k$, on a~:
$$0 \leq x=84844+66660k \leq 20000 \quad \Leftrightarrow \quad \frac{-84844}{66660} \leq k
\leq \frac{20000-84844}{66660} $$
donc $k=-1$ et $x=18184$. On v\'erifie que $x$ convient.
\end{enumerate}

\noindent\textbf{Exercice \no 4}

\begin{enumerate}
 \item {\em D\'eterminer le reste de la division euclidienne de
   $2020^{873}$ par 14. La m\'ethode doit \^etre explicit\'ee.}\\
On divise 2020 par 14, il reste 4, donc on calcule $4^{873}$ mod 14.
On calcule les carr\'es successifs de 4 mod 14, on obtient  mod 14
$$4^1=4, 4^2=2, 4^{2^2}=2^2=4, 4^{2^3}=4^2=2...$$
Comme \verb|873=0b1101101001|, les bits \`a 1 d'indice pair
(indices commen\c{c}ant \`a 0) contribuent \`a un facteur 4 et les bits \`a 1 d'indice impair \`a un
facteur 2, on a modulo 14~:
$$ 4^{873}= 4\times 2\times 2\times 4\times 4 \times 2=8$$
R\'esultat~: 8

Autre m\'ethode~: Pour calculer $4^{873}$, on peut observer que $4^4=16^2=2^2=4$ modulo
14. Attention, on ne peut pas simplifier par 4 qui est un diviseur de
0 modulo 14, $4^3 \neq 1$ modulo 14.
Donc $4^{1+3k}=4$ modulo 14, donc 
$$4^{873}=4^2\times 4^{1+3\times  290}=4^2 \times 4=8 \pmod  14$$
 \item {\em Donner la liste des inversibles de
   $\Z\textfractionsolidus14\Z$}.\\
Comme $14=2\times 7$, ce sont les classes des entiers premiers avec 2 et 7~: $\overline{1},
\overline{3},\overline{5},\overline{9},\overline{11},\overline{13}$
 \item {\em R\'esoudre l'\'equation dans $\Z\textfractionsolidus14\Z$,
   $\overline{11}x=\overline{3}$}.\\
L'\'equation a une solution unique puisque 11 est inversible modulo
14. \\Si on voit que $\overline{3}=\overline{-11}$, on trouve
imm\'ediatement $x=\overline{-1}$.
Sinon, on peut aussi obtenir $x$ rapidement,
comme on veut inverser 11 modulo 14,
on cherche l'identit\'e de B\'ezout sur 11 et 14,
or la premi\`ere division euclidienne de l'algorithme d'Euclide donne
la relation 14-11=3 donc modulo 14 on a
$\overline{11} \times \overline{-1}=\overline{3}$ et
$x=\overline{-1}=\overline{13}$.\\
Si on ne le voit aucune de ces astuces, on utilise la m\'ethode standard\\
\verb|L0        14  1  0|\\
\verb|L1        11  0  1|\\
\verb|L2=L0-L1   3  1 -1|\\
\verb|L3=L1-3L2  2 -3  4|\\
\verb|L4=L2-L3   1  4 -5|\\
Donc l'inverse de $\overline{11}$ est $\overline{-5}$, on multiplie
  par $\overline{3}$, on obtient $\overline{-15}=\overline{13}$.
\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 
{\em  Montrer que $x^2+y^2\equiv0\ [7]$}\\
En effet,  -13=1 et 7=0 modulo 7
 \item {\em Calculer les carr\'es de tous les \'el\'ements de
   $\Z\textfractionsolidus7\Z$.}\\
Modulo 7, on a
$0^2=0, 1^2=6^2=1, 2^2=5^2=4, 3^2=4^2=2,$
 \item {\em En d\'eduire que $x$ et $y$ sont multiples de 7.}\\
Si on somme deux \`a deux les carr\'es non nuls
$1+1=2, 1+4=5, 1+2=3, 4+4=1, 4+2=6, 2+2=4$
on n'obtient jamais 0, donc la seule possibilit\'e d'obtenir 0
est de sommer $0+0=0$
donc $x$ et $y$ sont multiples de 7.\\
Autre m\'ethode~: on v\'erifie que -1 n'est pas un carr\'e modulo 7
(soit en regardant la table des carr\'es, soit en calculant
$(-1)^{(7-1)/2} \neq 1$ mod 7)
\item  {\em $(*)$ 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$$}\\
On a donc $7^2a^2-13\times 7^2b^2=7$
on simplifie par 7, $7(a^2-13b^2)=1$
ce est impossible car 7 ne divise pas 1.
Donc il n'y a pas de solutions.
\end{enumerate}

\end{document}