\documentclass[11pt,a4paper]{article}
\usepackage{t1enc}
\usepackage{amsmath,amssymb,amsthm,amscd,graphicx}
\pagestyle{empty}
\usepackage[frenchb]{babel}
\usepackage[utf8]{inputenc}

\newcommand{\N}{\mathbb{N}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\ZZ}{\mathbb{Z}}
\def\ds{\displaystyle}
\newcommand{\mathframe}[1]{\fbox{$#1$}}
\def\ima{\mathrm{Im}}

\topmargin-2.8cm
\oddsidemargin-2.4mm
\textwidth17.5cm
\textheight26.7cm
\parskip=3pt
\parindent=0pt

\pagestyle{empty}

\def\soluce#1{} % n'affiche pas les indications de solutions

\begin{document}



\noindent
UGA, mat309  \hfill Feuille de TD 3 \hfill 2021-2022

\vspace{0.5cm}

{\bf Exercice 1}
R\'esoudre dans $\Z/2\Z$ le syst\`eme lin\'eaire
$$ \left\{\begin{matrix}
x+2y+3z&=&0\\
4x+5y+6z&=&1\\
7x+8y+4z&=&2\\
\end{matrix} \right.
$$
M\^eme question dans $\Z/5\Z$ et $\Z/3\Z$.

{\bf Exercice 2}
\begin{enumerate}
\item La famille de vecteurs
$$ \{  v_1=[1,2,3],v_2=[-1,-1,1],v_3=[2,1,1]\}$$
est-elle libre sur $K=\Z/2\Z$? 
\item Si cette famille n'est pas libre, d\'eterminez une combinaison
lin\'eaire non triviale.
\item Donner la dimension et le nombre d'\'el\'ements
du sous-espace vectoriel de $K^3$ engendr\'e par $\{v_1,v_2,v_3\}$.
\item
Soit $\varphi$ l'application lin\'eaire de $K^3$ dans $K^3$
telle que les images
des vecteurs de la base canonique $\{e_1,e_2,e_3\}$ 
soient $v_1=\varphi(e_1), v_2=\varphi(e_2), v_3=\varphi(e_3)$.
D\'eterminer le noyau et l'image de $\varphi$.
\end{enumerate}
M\^emes questions sur $K=\Z/7Z$.

{\bf Exercice 3}
Soit la matrice \`a coefficients dans $\Z/5\Z$~
$ A=\begin{pmatrix} 
1 & 2 & 3 \\
-1 & -1 & 1 \\
2 & 1 & 1
\end{pmatrix}$.
D\'eterminez $A^{12}$ en appliquant l'algorithme
d'exponentiation rapide. 
Quel est le plus petit entier $n>0$ tel que $A^n=I_3$~?
Exprimer $A^{-1}$ comme une puissance enti\`ere positive de $A$.

{\bf Exercice 4}
Calculez l'inverse de la matrice 
$ A=\begin{pmatrix} 
1 & 2 & 3 \\
-1 & -1 & 1 \\
2 & 1 & 1
\end{pmatrix}$
dans $\Z/5\Z$ et dans $\Z/2\Z$. V\'erifiez en effectuant le produit de
$A$ par son inverse!

    
{\bf Exercice 5 (cryptographie de Hill)}
On code les lettres de A \`a Z par les nombres de 1 \`a 26,
l'espace par 0, \verb|,| par 27 et \verb|.| par 28. On groupe les caract\`eres par paires
et on utilise la matrice
$A=\left( \begin{array}{cc}5&7\\1&15\end{array}\right) \pmod{29}$.
\begin{enumerate}
 \item Coder le message suivant : ``VIVE LES VACANCES''
 \item A quelle condition sur la matrice $A$ le destinataire du message cod\'e pourra t'il le d\'echiffrer ?
 \item D\'ecoder : ``IKYTYEH HSAHVRDAM ''
% a:=[[5,7],[1,15]]
% b:=inv(a mod 29)
% M:="@VIVE@LES@VACANCES"
% L:=asc(M).-64
% m:=char(flatten(irem(seq(a*L[2j..2j+1],j,0,size(L)/2-1) mod 0,29).+64)
% l:=asc(m).-64
% char(flatten(irem(seq(b*l[2j..2j+1],j,0,size(l)/2-1) mod 0,29).+64)
% \item Dans cette question, la matrice $A$ n'est pas connue.
% Pouvez-vous d\'ecoder le message suivant sachant qu'il commence par ``les'' suivi d'un espace ?
% YGSCN CYSGSC
\end{enumerate}

{\bf Janvier 2021: Cryptage matriciel \`a clef secr\`ete (10 points)}\\
Pour coder des messages pouvant contenir des caract\`eres de
diverses langues, on repr\'esente chaque caract\`ere par
un entier sur 16 bits (codage UTF16 par exemple). On d\'ecide ensuite
de crypter le message par blocs de 2 caract\`eres, en multipliant
chaque vecteur $v$ des 2 entiers repr\'esentant un bloc par une matrice carr\'ee $A$ 
de taille 2 modulo un entier $p$ qui sera suppos\'e premier dans les
questions 1 \`a 6. La matrice $A$ est tenue
secr\`ete, c'est la clef secr\`ete du syst\`eme de cryptage.
\begin{enumerate}
\item Dans quel intervalle se trouve un entier sur 16 bits~?\\
On suppose que $p$ est un nombre premier qui permet de repr\'esenter
de mani\`ere unique tous les entiers sur 16 bits par leur classe dans
$\Z/p\Z$. Quel est le nombre minimal de bits de $p$~?
\item On admettra que $p=65537$ est bien premier.
On pose~:
$$ p=65537, \quad
A=\left(\begin{array}{cc}263&4122\\1&1799\end{array}\right)
$$
Crypter le vecteur $v$ correspondant aux deux caractères ``intégrale
double'' et ``intégrale triple'' représentés respectivement par les
entiers 8748 et 8749,
%les deux caract\`eres
%int\'egrale double (8748) et int\'egrale triple (8749),
%$\left(\begin{array}{c}65\\66\end{array}\right)$,
 i.e. calculer $w=Av$ modulo $p$
\item D\'eterminer tous les vecteurs $z$ \`a coefficients
dans $\Z/p\Z$ tels que $Az=Av$ modulo $p$ pour $ p=65537$.\\
En d\'eduire tous les vecteurs $z$ \`a coefficients entiers
qui v\'erifient $Az=Av$ modulo $p$. \\
Si on impose que les coordonn\'ees de $z$ sont
dans l'intervalle du codage sur 16 bits, combien y-a-t-il de
solutions~?
\item
Que se passerait-il si on avait choisi la m\^eme matrice mais $p=6551$~?
\item Expliquer comment on peut d\'ecrypter, i.e. \'etant donn\'e $w$ quelconque,
  comment on trouve $v$ tel que $Av=w$ modulo $p$.
\item Quel est le nombre de matrices $A$ possibles pour $p=65537$~?
  Cela vous parait-il suffisant pour r\'esister \`a une attaque de la
  clef secr\`ete $A$ par  force brute~? Peut-on imaginer un autre
type d'attaque~? Comment pourrait-on renforcer la s\'ecurit\'e~?
\item Dans cette question, on suppose que $p=2^{16}$ et
n'est donc pas premier.
Peut-on appliquer l'algorithme du pivot de Gauss pour
r\'esoudre $Az=w=Av$ si on travaille modulo $p$ bien que $p$ ne
soit alors pas premier~? \\
En est-il de m\^eme pour la matrice 
$$ p=65536, \quad
A=\left(\begin{array}{cc}262&4122\\1&1799\end{array}\right)
$$
\item Quel(s) avantage(s) et inconv\'enient(s)
y-a-t-il \`a travailler modulo $2^{16}$
par rapport \`a $p=65537$~?
\end{enumerate}


{\bf Exercice 7}
Parmi les octets suivants \'ecrits en base 16 lesquels sont-ils de parit\'e paire~:\\
\verb|0x7f|, \verb|0x35|, \verb|0x45|, \verb|0xca|\\
Pour l'un de ces octets qui n'est pas de parit\'e paire, d\'eterminer les octets
de parit\'e paire qui ne diff\'erent que par un bit de cet octet.

{\bf Exercice 8}
Parmi les parties suivantes de $\Z/2\Z^n$, lesquels sont des codes
lin{\'e}aires ? 
Si oui, en donner une matrice g{\'e}n{\'e}ratrice.
\begin{enumerate}
\item $n=2, C=\{ 00,10 \}.$
\item
$n=4, C=\{ 0000,1010,0111,1011,0110 \}.$
\item
$n=3, C=\{ 000,100,001,111 \}.$
\item
$n=4, C=\{ 0000,0101,1010,1111 \}.$
\item
$n=4, C=\{ 0000,1011,1000,0011\}.$
\item
$n=4, C=\{ 0000,1101,1011,1001\}.$
\end{enumerate}

{\bf Exercice 9}
On consid\`ere le code lin\'eaire de matrice $M$ sur $\Z/2\Z$ et
le vecteur $v$~:
$$
M=\begin{pmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 \\
1 & 1 & 0 & 0 \\
0 & 0 & 1 & 1 \\
1 & 0 & 1 & 0 
\end{pmatrix}, \quad
v=\begin{pmatrix}1 \\ 1 \\ 0 \\
    1\end{pmatrix}
$$
\begin{enumerate}
\item D\'eterminer l'image $w$ du vecteur $v$
\item Comment retrouve-t-on $v$ \`a partir de son image $w=Mv$~?
\item D\'eterminer la matrice de controle $H$ ayant 3 lignes et 7 colonnes
telle que l'ensemble des mots du code soit le noyau de $H$.
V\'erifiez que $Hw=0$.
\item Montrez que tout vecteur dans l'image de $M$ a au moins
2 composantes non nulles. D\'eterminer la distance de ce code.
\end{enumerate}


{\bf Exercice 10}
\begin{enumerate}
\item Créez une matrice $M$ de taille 7,4 
sur $\Z/2\Z$ telle que le code correspondant soit syst\'ematique
et sa distance de Hamming 3.
\item Pour cette matrice, d\'eterminer la matrice de controle
$H$ (3 lignes, 7 colonnes)
telle que tout mot du code $w=Mv$ soit dans le noyau de $H$.
\item Calculer les entiers $h_i$ dont l'\'ecriture en base 2 est la
$i$-i\`eme colonne de $H$. En d\'eduire comment corriger
une erreur de transmission sur un vecteur $w \in K^7$ en
utilisant la valeur de l'entier correspondant \`a $Hw$.
\item
Peut-on r\'ealiser un code lin\'eaire de param\`etres $n=7,k=4$
r\'ealisant la borne de Singleton, i.e. une distance de 4~?
\end{enumerate}

\end{document}

{\bf Exercice 7}
Soit $o_7,...,o_0$ l'\'ecriture en base 2 d'un octet $o$ et
$O(X)=o_7x^7+...+o_1x+o_0$.
D\'eterminer le reste de la division euclidienne de $O(X)$
par $X+1$ dans $\Z/2\Z$ pour un octet de parit\'e paire  et pour
un octet de parit\'e impaire.
\\
Soit $b$ un entier compris entre 0 et 127, $b_6,...,b_0$
son \'ecriture en base 2 et $B(X)=b_6X^6+...+b_1X+b_0$
le polyn\^ome associ\'e dans $\Z/2\Z$. 
\begin{enumerate}
\item Soit $P(X)=B(X)X$ et $R$ le reste de la division
euclidienne de $P$ par $X+1$, montrer que $P+R$
correspond \`a un octet $\tilde{o}$ de parit\'e paire. 
\item Comment retrouve-t-on $b_6,...,b_0$ \`a
partir de $\tilde{o}_7,...,\tilde{o}_0$~?
\item
Montrer que $O(X)=B(X)(X+1)$
correspond \`a un octet $o$ de parit\'e paire. V\'erifiez
avec $o=$\verb|0x45|.
\item Comment retrouve-t-on $b_6,...,b_0$ \`a
partir de $o_7,...,o_0$~?
\item \'Ecrire les matrices des 2 codages ci-dessus.
\end{enumerate}

{\bf Exercice 11}
Code polynomial de polynome g\'en\'erateur $G(x)=x^4+x+1$
et param\`etres $m=4, n=2^4-1=15, k=n-m=11$.\\
On code 11 bits de donn\'ees par un polyn\^ome $P$ ayant $k=11$ coefficients
dans $\Z/2\Z$ (donc de degr\'e 10), on multiplie $P$ par $x^4$ et on
ajoute le reste de la division de $Px^4$ par $G$, le polynome
obtenu $Q$ a $n=15$ coefficients.
\begin{enumerate}
\item Montrer que $Q$ est divisible par $G$\\
On transmet $Q$. Le destinataire v\'erifie alors que le polyn\^ome re\c{c}u 
$\tilde{Q}$ est divisible par $G$, si oui il l'accepte, sinon il le
corrige en tenant compte du reste $R$ de la division de 
$\tilde{Q}$ par $G$.
\item D\'eterminer la liste des restes de division de $x^0$ \`a $x^{14}$
par $x^4+x+1$ dans $\Z/2\Z[X]$, v\'erifiez qu'ils sont distincts 2 \`a
2. En d\'eduire qu'un polynome multiple de $G$ a au moins 3
coefficients non nuls (indication~: consid\'erer le reste par $G$ de
la somme de 2 monomes).
\item Comment peut-on corriger au plus proche une erreur de transmission
sur un coefficient de $\tilde{Q}$~?
\end{enumerate}


{\bf Exercice 12: algorithmes (bonus)}
\'Ecrire et/ou programmer un ou plusieurs algorithmes r\'ealisant les
taches suivantes~:
\begin{enumerate}
\item le calcul d'un octet de parit\'e paire \'etant donn\'e un entier
  compris entre 0 et 127, le test de parit\'e d'un octet
\item le code de l'exercice 10 ou la cr\'eation d'un code de Hamming
binaire de param\`etres $m=7, n=2^{m}-1,k=2^m-m-1$
soit avec une matrice, soit en utilisant le polyn\^ome $x^7+x^3+1$,
et la correction d'un mot au plus proche.
\item la r\'eduction d'une matrice dans $\Z/2\Z$ par le pivot de
  Gauss, le calcul de l'inverse de matrice.
\end{enumerate}

\end{document}

