\documentclass[12pt,a4paper]{article}
\usepackage{multicol}
\usepackage[french]{babel}
\newfont{\mini}{cmssi10 scaled 480}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\euro{\mbox{\textsf{C}\kern -2.33em{\raise0.24ex\vbox{\small\it =}}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\fin{\nolinebreak \raise-0.1em\hbox{$\Box$}}
\def\stackunder#1#2{\mathrel{\mathop{#2}\limits_{#1}}}
\def\dual{ ^{\rm v}}
\def\bidual{ ^{\rm vv}}
\def\primedual{ ^{\prime \rm v}}
\def\ideal{{\cal J}}
\def\LL{{\cal L}}
\def\max{{\cal M}}
\def\quot#1#2{\mbox{\raise 0.1cm\hbox{$#1$}{\big /}\raise -0.1cm\hbox{$#2$}}}
\def\danger{{\Large \bf
    $\bigtriangleup$}\kern-0.32cm\raise0.05cm\hbox{\small
    !}\kern0.32cm\lower0.05cm\hbox{}}
%%%%%%%
\newlength{\largeurtmp}
\def\rela{\settoheight{\largeurtmp}{Z}{\rm Z} \kern -0.6\largeurtmp
  \raise 0.05cm\hbox{\tiny{\it /}}\kern 0.6\largeurtmp}
\def\petitrela{\settoheight{\largeurtmp}{Z}{\rm Z} \kern -0.4\largeurtmp
  \raise 0.05cm\hbox{\tiny{\it /}}\kern 0.4\largeurtmp}
\def\petitcomplex{{
    \settoheight{\largeurtmp}{$_C$}{\rm C}\kern -\largeurtmp
    \rule{0.25pt}{1.3\largeurtmp}\kern \largeurtmp}}
\def\complex{{
    \settoheight{\largeurtmp}{Q}{\rm C}\kern -0.66\largeurtmp
    \rule{0.25pt}{0.9\largeurtmp}\kern 0.66\largeurtmp}}
\def\ratio{{
    \settoheight{\largeurtmp}{C}{\rm Q}\kern -0.75\largeurtmp
    \rule{0.25pt}{0.9\largeurtmp}\kern 0.75\largeurtmp}}
\def\petitratio{{
    \settoheight{\largeurtmp}{C}{\rm Q}\kern -0.6\largeurtmp
    \rule{0.25pt}{0.6\largeurtmp}\kern 0.6\largeurtmp}}
\newcommand{\proj}{{\rm I} \! {\rm P}}
\newcommand{\reel}{{\rm I} \! {\rm R}}
\newcommand{\Fp}{{\rm I} \! {\rm F}_p}
\newcommand{\nat}{{\rm I} \! {\rm N}}
%%%%%%%%%%%%%%%Debut de macros de fiches d'exos
%%les macros sont \exo, \qu, \quskip \squ \qusqu \qusquskip
\newcounter{exo}
\newcounter{question}
\newlength{\lng}
\newcounter{sousquestion}
\setcounter{exo}{1}
\def\exo{

  \bigskip
  \noindent{\bf Exercice
    \Roman{exo}:}\addtocounter{exo}{1}\setcounter{question}{0}\nopagebreak 

  }
\def\exotitre#1{

  \bigskip
  \noindent{\bf Exercice
    \Roman{exo}: #1}\addtocounter{exo}{1}\setcounter{question}{0}\nopagebreak 

  }
\def\qu{

  \addtocounter{question}{1}\arabic{question})
  \setcounter{sousquestion}{1} }
\def\quskip{

  \bigskip
  \qu}
\def\squ{

  \settowidth{\lng}{\arabic{question})
  }\hspace{\the\lng}\alph{sousquestion}) \addtocounter{sousquestion}{1}} 
\def\qusqu{\qu\nopagebreak \vskip -1\baselineskip \squ}
\def\qusquskip{\quskip\nopagebreak \vskip -1\baselineskip \squ}

%%reference pour exos,squ {\`a} placer avant la question, qu est a placer apres
\def\labelexo#1{\expandafter\edef\csname refexo#1\endcsname {\Roman{exo}}}
\def\refexo#1{\csname refexo#1\endcsname}
\def\labelqu#1{\expandafter\edef\csname refqu#1\endcsname {\arabic{question})}}
\def\refqu#1{\csname refqu#1\endcsname}
\def\labelsqu#1{\expandafter\edef\csname refsqu#1\endcsname
  {\arabic{question}\alph{sousquestion})}} 
\def\refsqu#1{\csname refsqu#1\endcsname}  

%%%%%%%%%%fin de macros fiche d'exos
%%macros taille page
\newlength{\elargir}
\setlength{\elargir}{2.5cm}
\addtolength{\leftmargin}{-\elargir}
%%\addtolength{\hoffset}{-\elargir}
\addtolength{\oddsidemargin}{-\elargir}
\addtolength{\evensidemargin}{-\elargir}
\addtolength{\elargir}{\elargir}
\addtolength{\textwidth}{\elargir}
\addtolength{\textheight}{13\baselineskip}
\topmargin=-5\baselineskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%        
\everymath={\displaystyle}
\begin{document}
\noindent{\bf Universit{\'e} de Paris 7 \hfill \framebox{\Large \bf
    \hspace{ 1cm} TP19 LLL; applications \hspace{1cm}}\hfill   agreg 2008 (F.Han)}\\
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\code#1{{\tt #1}}
\newtheorem{definition}{D{\'e}finition}
\newtheorem{proposition}{Proposition}
% restart;maple_mode(1);cas_setup(0,0,0,1,0,1e-10,25,[1,50,0,25],0,0,0);#radians,pas de cmplx, pas de  Sqrt
\section{Introduction}
On a souvent besoin de trouver rapidement un vecteur de "petite" norme
dans un r{\'e}seau. Par exemple, pour trouver un facteur d'un {\'e}l{\'e}ment de
$\rela[x]$ lorsqu'on en connait un dans $\rela/p^n\rela[x]$, mais
aussi pour briser le cryptosyst{\`e}me de type sac {\`a} dos. La m{\'e}thode
d{\'e}crite ci dessous ne donne pas forc{\'e}m{\'e}ment un vecteur de norme
minimale, mais elle donne en revanche rapidement un vecteur de petite
norme. Elle fut publi{\'e}e en 1982 par Lenstra-Lenstra-Lovasz pour
factoriser des polyn{\^o}mes {\`a} coefficients entiers, mais elle fut
appliqu{\'e}e ensuite dans bien d'autres situations. 
\section{Bases r{\'e}duites d'un r{\'e}seau}
   On dit que $L$ est un r{\'e}seau de $\reel^n$ s'il existe une base
   $b_1,\dots,b_n$ de $\reel^n$ telle que $L$ soit un $\rela$-module
   libre de base $(b_1,\dots,b_n)$. On appellera d{\'e}terminant de $L$
   le nombre\footnote{ind{\'e}pendant du choix de la base $(b)$ de $L$}
   $$d(L)=|\det(b_1,\dots,b_n)|$$
   Pour toute base $(b_1,\dots,b_n)$ de $\reel^n$, on notera
   $(b^*_1,\dots,b^*_n)$  la base obtenue {\`a} partir de $(b)$ par
   orthogonalisation de Gram-Schmidt (pour le produit scalaire usuel
   sur $\reel^n$). Autrement dit, les vecteurs
   $b_i^*$ sont d{\'e}finis par les formules de r{\'e}currence:
   $$b^*_1=b_1,\  \forall i>1,\ 
   b_i^*=b_i-\sum_{j=1}^{i-1}\mu_{i,j}b_j^*;\
   \mu_{i,j}=\frac{(b_i,b_j^*)}{(b_j^*,b_j^*)}$$ 
o{\`u} $(\ ,\ )$ d{\'e}signe le produit scalaire choisi sur $\reel^n$.
On remarquera que $b^*_i$ n'est rien d'autre que le projet{\'e} orthogonal
de $b_i$ sur l'orthogonal de l'espace vectoriel engendr{\'e} par
$b_1,\dots,b_{i-1}$.
\begin{definition}
  On dira d'une base $(b_1,\dots,b_n)$ d'un r{\'e}seau $L$ qu'elle est
  r{\'e}duite, si les deux conditions suivantes sont r{\'e}alis{\'e}es: 
  \begin{equation}
    \forall i,j,\  1\leq j<i\leq n,\  |\mu_{i,j}|\leq\frac{1}{2}
  \end{equation}
  \begin{equation}
  \forall i,\  1< i \leq n,\  ||b^*_i+\mu_{i,i-1}b^*_{i-1}||^2 \geq
  \frac{3}{4} ||b_{i-1}^*||^2
  \end{equation}
\end{definition}
On remarquera que $b^*_i+\mu_{i,i-1}b^*_{i-1}$ et $b^*_{i-1}$ sont les
projections de $b_i$ et $b_{i-1}$ sur l'orthogonal de l'espace
vectoriel engendr{\'e} par $(b_1,\dots,b_{i-2})$. De plus, on a les deux
propositons suivantes, qui "justifient" le fait qu'une base r{\'e}duite
donne un vecteur de "petite"  norme du r{\'e}seau:
\begin{proposition}
  Si $(b_1,\dots,b_n)$ est une base r{\'e}duite d'un r{\'e}seau $L$, alors on
  a:
  \begin{equation}
\label{p1}
    \forall (i,j)\in \nat^2,\ 1\leq j\leq i \leq n \Rightarrow ||b_j||^2 \leq 2^{i-1}. ||b_i^*||^2
  \end{equation}
  \begin{equation}
    \label{p2}
    d(L)\leq \prod_{i=1}^n ||b_i|| \leq 2^{\frac{n.(n-1)}{4}}.d(L)
  \end{equation}
  \begin{equation}
    \label{p3}
    ||b_1|| \leq 2^{\frac{n-1}{4}}d(L)^{\frac{1}{n}}
  \end{equation}
\end{proposition}
En effet, si $b$ est r{\'e}duite, alors pour $i,j$ tels que  $1\leq j\leq
i \leq n$, on a $||b_j^*||^2 \leq 2^{i-j} ||b_i^*||^2$, qui remplac{\'e}
dans les formules d'orthogonalisation donne (\ref{p1}). On remarque
ensuite que $d(L)$ est aussi {\'e}gal {\`a} $|\det(b_1^*,\dots,b_n^*)|$ qui
vaut $\prod_{i=1}^n||b_i^*||$ ce qui permet d'obtenir (\ref{p2}) en
utilisant\footnote{comparer $||b_i||$ et $||b_i^*||$} (\ref{p1}).
%% NB: ||bi|| >= ||bi*||
On d{\'e}duit  (\ref{p3}) de (\ref{p1}) et (\ref{p2}).

A t'on utilis{\'e} le fait que $b$ soit r{\'e}duite pour l'in{\'e}galit{\'e} $d(L)\leq
\prod_{i=1}^n ||b_i||$?

%!s!<c>
% non on n'a pas utilis{\'e} le fait que b soit reduite pour
%d(L)<=\prod_{i=1}^n ||b_i||, c'est l'in{\'e}alit{\'e} d'Hadamard
%!s!
\begin{proposition}
  Soit $L$ un r{\'e}seau de $\reel^n$, et $(b_1,\dots,b_n)$ une base
  r{\'e}duite de $L$, alors:
  \begin{equation}
    \forall x \in L, x \neq 0 \Rightarrow ||b_1||^2 \leq 2^{n-1}. ||x||^2
  \end{equation}
\end{proposition}
\section{L'algorithme de r{\'e}duction}
\def\.{

\noindent$\bullet$}
Soit $(b)$ une base d'un r{\'e}seau $L$ de $\reel^n$.
\. On initialise l'algorithme en calculant $(b^*)$. On stockera alors
pour la suite $(\mu_{i,j})$ et les nombres $||b_i^*||^2$,  les
vecteurs $(b^*)$ ne seront plus utilis{\'e}s. 

\smallskip
Nous allons effectuer une suite
d'{\'e}tape (qui modifie un {\'e}l{\'e}ment  $k$ de $\{1,\dots,n+1\}$) commen\c cant
et se terminant de telle sorte que les propri{\'e}t{\'e}s suivantes soient
vraies:
\begin{equation}
  \label{eq:k1}
    |\mu_{i,j}| \leq \frac{1}{2} \ \mbox{ pour } 1 \leq j <i<k 
\end{equation}
\begin{equation}
  \label{eq:k2}
  ||b_i^* + \mu_{i,i-1} b_{i-1}^*  ||^2 \geq
  \frac{3}{4}||b_{i-1}^*||^2 \ \mbox{ pour } 1<i<k
\end{equation}
On constate que pour $k=2$, il n'y a rien {\`a} v{\'e}rifier pour satisfaire
ces conditions. On peut donc
commencer l'algorithme avec $k=2$. Si les conditions pr{\'e}c{\'e}dentes sont
satisfaites pour $k=n+1$, alors la base est r{\'e}duite, et l'on a
termin{\'e}.
%%
\. On r{\'e}p{\`e}te alors les {\'e}tapes suivantes tant que $ k\leq n$:

\smallskip
$\diamond$ On aimerait avoir $|\mu_{k,k-1}| \leq \frac{1}{2}$. Si cette in{\'e}galit{\'e}
n'est pas v{\'e}rifi{\'e}e, alors on remplace $b_k$ par $b_k-rb_{k-1}$ o{\`u} $r$
est l'entier le plus proche de $\mu_{k,k-1}$. Ce changement impose
alors les transformations suivantes pour retrouver l'orthogonalis{\'e}:
pour $j<k-1$ on remplace $\mu_{k,j}$ par $\mu_{k,j}-r\mu_{k-1,j}$ et
$\mu_{k,k-1}$ par $\mu_{k,k-1} -r$ les autres $\mu_{i,j}$ {\'e}tant
inchang{\'e}s.

On distingue ensuite deux cas:

\bigskip
$\diamond$ {\sc Cas 1:} Si\footnote{On pourra trouver une condition {\'e}quivalente
  ne d{\'e}pendant que des normes des vecteurs de $b^*$. On remarquera que
dans tout l'algorithme on peut se contenter de n'utiliser que les normes des
vecteurs $b^*$, et que l'on n'a pas besoin des vecteurs $b^*$}
l'on est dans la (mauvaise) situation suivante: $||b^*_k+\mu_{k,k-1} b^*_{k-1}||^2 <\frac{3}{4}||b_{k-1}^*||^2$ 

Nous allons alors faire diminuer $||b^*_{k-1}||$. Etudions ce
qu'il se passe si l'on {\'e}change $b_k$ et $b_{k-1}$ 
sans toucher aux autres
$b_i$. Notons $c$ la base d{\'e}duite de $b$ o{\`u} l'on a {\'e}chang{\'e} $b_k$ et
$b_{k-1}$, $c^*$ son orthonorgonalis{\'e}e, et $\nu_{i,j}=\frac{(c_i,c_j^*)}{c_j^*,c_j^*}$. Puisque $c_{k-1}^*$ est la projection de $b_{k}$ sur
l'orthogonal de $\sum_{j=1}^{k-2} \reel b_j$, on a:
$$c_{k-1}^*=b_k^* +\mu_{k,k-1} b_{k-1}^*$$
ce qui donne  $||c_{k-1}^*||^2< \frac{3}{4}||b^*_{k-1}||^2$,
confirmant le fait que 
l'on a bien r{\'e}ussi {\`a} faire diminuer $||b^*_{k-1}||$.
On obtient ensuite $c^*_k$ en projetant $b_{k-1}^*$ sur l'orthogonal de
$c_{k-1}^*$, ce qui donne:
$$\nu_{k,k-1}=\frac{(b_{k-1}^*,c_{k-1}^*)}{(c_{k-1}^*,c_{k-1}^*)}=\mu_{k,k-1}\frac{||b_{k-1}^*||^2}{||c_{k-1}^*||^2}\mbox{\
  \ \ et \ \ }
c_{k}^*+\nu_{k,k-1}.c_{k-1}^*=b_{k-1}^*$$

Pour $i\neq k-1$, on a $c_i^*=b_i^*$, et en exprimant pour $i>k$ les
vecteurs $b^*_i$ en
fonction de $(c^*)$ dans l'{\'e}galit{\'e} $b_i=b_i^*+ \sum_{j=1}^{i-1}
\mu_{i,j}b_j^*$, on trouve que les transformations {\`a} faire sont:
$$\nu_{k,k-1}=\mu_{k,k-1}\frac{||b_{k-1}^*||^2}{||c_{k-1}^*||^2}$$
$$\mbox{pour } k+1\leq i\leq n\left\{
\begin{array}[c]{lll}
  \nu_{i,k-1} & = &\mu_{i,k-1}.\nu_{k,k-1}+\mu_{i,k}.\frac{||b_k^*||^2}{||c^*_{k-1}||^2} \\
  \nu_{i,k} & = & \mu_{i,k-1}-\mu_{i,k}.\mu_{k,k-1}
\end{array}\right.$$
$$\mbox{ pour } 1\leq j\leq k-2 \hspace{1cm} \nu_{k-1,j}=\mu_{k,j} \mbox{ et } \nu_{k,j}=\mu_{k-1,j}\hspace{1cm}$$
$$\nu_{i,j}=\mu_{i,j} \mbox{ pour } 1 \leq j<i\leq n \mbox{ et }
\{i,j\}\cap \{k-1,k\}=\emptyset$$ 
$$c_{k-1}=b_k;c_k=b_{k-1} \mbox{ et } \forall i\notin \{k-1,k\},\ 
c_i=b_i$$
$$||c^*_{k-1}||^2=||b_k^*||^2+(\mu_{k,k-1})^2||b^*_{k-1}||^2,\mbox{ et
} ||c_k^*||^2=\frac{||b_{k-1}^*||^2.||b_k^*||^2}{||c^*_{k-1}||^2}$$
Les vecteurs $(b_1,\dots,b_{k-2})$ n'ayant pas {\'e}t{\'e} chang{\'e}s, les
propri{\'e}t{\'e}s \ref{eq:k1} et \ref{eq:k2} restent vraies au rang
pr{\'e}c{\'e}dent, on peut alors remplacer $k$ par $\sup(2,k-1)$ et continuer
l'algorithme. 

\bigskip
$\diamond$ {\sc Cas 2:} Si $||b_k^*+\mu_{k,k-1}b_{k-1}^*||^2\geq
\frac{3}{4}||b_{k-1}^*||^2$

On aimerait maintenant avoir la propri{\'e}t{\'e} \ref{eq:k1}: $|\mu_{k,j}|\leq \frac{1}{2}$ pour $1\leq
j\leq k-1$. Comme c'est vrai pour $j=k-1$, on obtient les autres
in{\'e}galit{\'e}s en regardant pour $l$ variant de $k-2$ {\`a} $1$
si  $|\mu_{k,l}|>\frac{1}{2}$. Et si cette condition est v{\'e}rifi{\'e}e,
alors on consid{\`e}re  l'entier $r$ le plus proche de
$\mu_{k,l}$, et l'on remplace $b_k$ par $b_k-rb_l$. Pour $j<l$, les nombres
$\mu_{k,j}$ sont alors remplac{\'e}s par $\mu_{k,j}-r.\mu_{l,j}$ et
$\mu_{k,l}$ par $\mu_{k,l}-r$. Les autres $\mu$ et $b^*$ restent
inchang{\'e}s.

On a maintenant une bonne situation au niveau $k$ et l'on peut
remplacer $k$ par $k+1$ et continuer l'algorithme.
\section{Terminaison et co{\^u}t}
Il faut d'abord remarquer que l'algorithme pr{\'e}c{\'e}dent se termine. On
consid{\`e}re pour cel{\`a} les nombres\footnote{On pourra justifier cette
  {\'e}galit{\'e}} $d_i=\det((b_j,b_l)_{1\leq j,l\leq  i})=\prod_{j=1}^i
||b_j^*||^2$. On pose $D=\prod_{i=1}^{n-1} d_i$. Le nombre $D$ n'est
modifi{\'e} que si l'un des vecteurs de $b^*$ est chang{\'e}, ce qui n'arrive
que dans le cas  1. Dans ce cas, $d_{k-1}$ est r{\'e}duit d'un facteur
$\frac{3}{4}$, et les autres ne sont pas modifi{\'e}s.

D'autre part le nombre $D$ est minor{\'e}. On se limitera ici au cas o{\`u}
les $b_i$ sont {\`a} coefficients entiers. Dans ce cas, si $B$ est une
constante telle que $\forall i ||b_i||^2 \leq B$ alors $d_i\leq B^i$, et
%%En effet on peut montrer que le
%%parall{\'e}l{\'e}pip{\`e}de $b_1,\dots,b_i$ contient toujours un vecteur non nul
%%du r{\'e}seau: $x$ tel que $||x||^2 \leq (4/3)^{\frac{i-1}{2}}. d_i^{\frac{1}{i}}$,
%%et donc que $d_i \geq (3/4)^{i(i-1)/2} m(L)^i$ o{\`u} $m(L)$ est le carr{\'e}
%%de la norme minimale\footnote{Justifier l'existence du minimum} d'un
%%{\'e}l{\'e}ment non nul de $L$.

le nombre de fois o{\`u} l'on passe par le cas 1 est alors born{\'e} (et de
l'ordre de $O(n^2.\log B)$), donc
%%car D>(3/4)^(a.n^2)
celui o{\`u} l'on passe par le cas 2 est aussi born{\'e} en $O(n^2.\log B)$, et l'algorithme se termine en
$O(n^4.\log B)$ op{\'e}rations arithm{\'e}tiques sur le corps de base.
%!s!<c>
%C'est deja programme dans maple: l'instruction lattice existe deja
%dans maple7 et superieur. Dans maple9 il y a en plus le paquet with(IntegerRelations);
%qui contient l'instruction LLL. Pour xcas il y a l'instruction: lll, et
%l�instruction pari_qflll. (qui retourne la matrice de passage.)
%!s!
\section{Le probl{\`e}me du sac {\`a} dos; Cryptosyst{\`e}me de Merkle et Hellman}
Soit $(a_1,\dots,a_n,c)$ des entiers. Le probl{\`e}me du sac {\`a} dos est le
suivant: Quelles sont les $(\epsilon_1,\dots,\epsilon_n)\in \{0,1\}^n$
tels que $\sum_{i=1}^n \epsilon_i.a_i=c$. Autrement dit, quelles sont
les diff{\'e}rentes fa\c cons de remplir un sac {\`a} dos de hauteur $c$ avec des
batons de taille $a_i$? Sous cette g{\'e}n{\'e}ralit{\'e} ce probl{\`e}me est
consid{\'e}r{\'e} comme tr{\`e}s difficile, et l'on n'en connait pas de solution
polyn{\^o}miale en $n$. (On a en revanche une solution triviale
exponentielle en $n$). 

En revanche, dans le cas particulier d'une suite $(a_1,\dots,a_n)$
surpercroissante (ie telle que $\forall i \in [2,n], a_i>
\sum_{j=1}^{i-1} a_j$), alors le probl{\`e}me a une solution unique que
l'on trouve rapidement.

L'id{\'e}e de Merkle et Hellman {\'e}tait donc de prendre pour clef secr{\`e}te
une suite supercroissante $(a_i)$, de choisir des entiers
$M>\sum_{i=1}^n a_i$ et $w$
tels que $M\wedge w=1$, et de briser la supercroissance en posant:
$b_i=w*a_i [M]$. (NB pour simplifier le raisonnement ici, on ne
r{\'e}ordonne pas les $(b_i)$ dans l'ordre croissant). La clef publique
est alors la donn{\'e}e de $(b_i)$, et pour crypter un message {\'e}crit en
base 2 $\epsilon_1,\dots,\epsilon_n$, on transmet gr{\^a}ce {\`a} la clef
publique: $c=\sum_{i=1}^n \epsilon_i.b_i$. R{\'e}soudre ce probl{\`e}me
semblait difficile sans connaitre $M,w,(a)$ puisque $(b)$ n'est pas
supercroissante, alors que la connaissance de $M,w,(a)$ permet de
trouver facilement le message.

Shamir a cependant trouv{\'e} une faille au probl{\`e}me du sac {\`a} dos en $(b)$
reposant sur LLL. Consid{\'e}rons la matrice publique
$M=\left(
\begin{array}[c]{cccc}
  0 & 1 &0 & . \\
  \vdots& \ddots & \ddots & 0 \\
  0 & \dots & 0 & 1 \\
  c & b_1 & \dots & b_n
\end{array}\right)$. Alors le vecteur suivant caract{\'e}risant le message$
\left(\begin{array}[c]{c}
    \epsilon_1\\
    \vdots\\
    \epsilon_n\\
    0 
\end{array}\right)
$ est un vecteur du r{\'e}seau engendr{\'e} par les colonnes de $M$, de norme
petite puisqu'elle est major{\'e}e par $\sqrt{n}$. On a donc de bonnes
chances de le trouver par LLL.
\section{D{\'e}veloppements}
On donne ici une liste indicative de d{\'e}veloppements et d'illustrations que vous
pourrez utiliser ou non. Il s'agit d'un menu {\`a} la carte et non de passages
obligatoires. 
\qusqu On pourra impl{\'e}menter l'algorithme d'orthogonalisation, pour
obtenir $(b^*)$ et $(\mu)$.
%%pour giac xcas
% M:=matrix([[1,2,3],[-1,0,1],[0,1,1]]);
%!s!<m> 
% ortho:=proc(A)//On teste d'abord l'orthogonalisation des lignes.
% local b,bb,mu;
% b:=[seq((A)[i],i=1..rowdim(A))];
% n:=nops(b);//la dimension du reseau
% bb:=b;
% for i from 2 to n do
% bb[i]:=normal(b[i]-add((b[i]*bb[j])/(bb[j]*bb[j])*bb[j],j=1..i-1));
% od;
% mu:=matrix(n,n,(i,j)->(b[i]*bb[j])/(bb[j]*bb[j]));
% mu,bb;
% end proc;
%!s!
% v:=ortho(M)[2];v[1]*v[2],v[2]*v[3],v[3]*v[1];
\squ  On pourra {\'e}ventuellement impl{\'e}menter l'algorithme d{\'e}crit ci dessus. 
%!s!<p>
%  myLLL:=proc(A)//notre LLL pour les lignes;
%  local b,mu,bb,BB,k,r;
%  b:=A;//les vecteurs sont les lignes de A
%  n:=nops(b);//la dimension du reseau
%  bb:=b;
%  for i from 2 to n do
%  bb[i]:=normal(b[i]-add((b[i]*bb[j])/(bb[j]*bb[j])*bb[j],j=1..i-1));
%  od;
%  mu:=matrix(n,n,(i,j)->(b[i]*bb[j])/(bb[j]*bb[j]));
%  BB:=[seq(bb[i]*bb[i],i=1..n)];//BB= les carre des normes des b^*
%  k:=2;
%  while ( k<n+1)
%  do
%  if abs(mu[k,k-1])> 0.5 then
%         r:=round(mu[k,k-1]);
%         b[k]:=b[k]-r*b[k-1];
%         for j from 1 to k-2 do mu[k,j]:=mu[k,j]-r*mu[k-1,j];od;
%         mu[k,k-1]:=mu[k,k-1]-r;
%  fi;
%  if ( BB[k] < BB[k-1]*(3/4-mu[k,k-1]^2))
%  then
%  mk:=mu[k,k-1];//on sauve l'ancienne valeur de mu[k,k-1]
%   cc:=BB[k]+mk^2*BB[k-1];  //cc=norme de c^*_{k-1} au carre
%  mu[k,k-1]:=mk*BB[k-1]/cc;//on remplace mu[k,k-1] par la valeur de nu_{k,k-1} 
%  for i from k+1 to n do
%  mik:=mu[i,k-1];//on sauvegarde
%  mu[i,k-1]:=mu[i,k-1]*mu[k,k-1]+mu[i,k]*BB[k]/cc;
%  mu[i,k]:=mik-mu[i,k]*mk;
%  od;
%  for j from 1 to k-2 do
%  mkj:=mu[k,j];mu[k,j]:=mu[k-1,j];mu[k-1,j]:=mkj;
%  od;
%  //on echange b_k et b_{k-1}
%  c:=b[k];b[k]:=b[k-1];b[k-1]:=c;
%  BB[k]:=BB[k-1]*BB[k]/cc;BB[k-1]:=cc;//on corrige le carre des normes de b^*
%  k:=max(2,k-1);
%  else
%  l:=k-2;
%  while l>0 do
%     if abs(mu[k,l])>0.5 then
%     r:=round(mu[k,l]);b[k]:=b[k]-r*b[l];
%     for j from 1 to l-1 do mu[k,j]:=mu[k,j]-r*mu[l,j] od;
%     mu[k,l]:=mu[k,l]-r;
%     fi;
%     l:=l-1;
%     od;
%  k:=k+1;
%  fi;
%  od;
%  b;
%  end proc:
% !s!
\qu Expliquer pourquoi l'algorithme se termine, et le calcul du co{\^u}t.
\qusqu On pourra impl{\'e}menter le cryptosyst{\`e}me de Merkle-Hellmann. 
\squ Expliquer et illustrer la faille du sac {\`a} dos. Si l'on n'a pas programm{\'e}
l'algorithme, on pourra  regarder si l'algorithme LLL n'est pas d{\'e}j{\`a}
impl{\'e}ment{\'e} dans votre logiciel  favori\footnote{par exemple maple7, xcas, \dots
  (Attention maple7 n'a 
  pas le package   \code{IntegerRelations}). Pour xcas on utilisera la commande
  de pari pour l'instant  plus fiable que la commande native lll (Un bug a {\'e}t{\'e}
  corrig{\'e} le 20/5/2007)}  
% !s!<c>
% sac {\`a} dos:
% On cree la clef publique: A (suite supercroissante)
%!s!
% s:=rand(200):A:=[s]:for i from 1 to 6 do s:=s+rand(200):A:=[op(A),s]: od;
% add(A);#on prend superieur a la somme
% M:=3001;w:=1001;igcd(w,M);
% B:=[seq(w*i mod M,i=A)];
% E:=[1,0,1,0,0,0,1];// le message a transmettre.
% c:=E*B;//le message crypt{\'e}
% M:=matrix(nops(B)+1,nops(B)+1,(i,j)->if i=j-1 then 1 else 0 fi);
% M[nops(B)+1,1]:=c;for i from 1 to nops(B) do M[nops(B)+1,i+1]:=B[i] od:M;
% myLLL(transpose(M));// la premiere ligne est bien le message E
%!s!
% //un autre essai:
% s:=rand(200):A:=[s]:for i from 1 to 20 do s:=s+rand(200):A:=[op(A),s]: od:
%add(A);
% M:=40001;w:=2357;igcd(w,M);
% B:=[seq(w*i mod M,i=A)];
% E:=[seq(rand(2)*rand(2),i=0..nops(A))]:// le message a transmettre. On met un carre pour avoir pas mal de zeros
% c:=E*B://le message crypt{\'e}
% M:=matrix(nops(B)+1,nops(B)+1,(i,j)->if i=j-1 then 1 else 0 fi):
% M[nops(B)+1,1]:=c:for i from 1 to nops(B) do M[nops(B)+1,i+1]:=B[i] od:
%!s!
% myLLL(transpose(M));
% lll(transpose(M));
% pari();
% !s!<c>
% pari le fait sur les colonnes, et retourne la matrice de passage entre les 2
% bases
%!s!
% transpose(M*pari_qflll(M));
% !s!<c>
% On essaye un autre reseau qui contient aussi une solution. Attention, le sac a dos modulaire peut avoir plusieurs solutions,
% c'est le super croissant qui n'en a qu'une.
% !s!<m>
%r:=-floor(-sqrt(nops(B))/2);M[nops(B)+1]:=r*M[nops(B)+1]:
%for i from 1 to nops(B) do M[i,1]:=1/2 od:M;
%!s!
%myLLL(transpose(M))+matrix(nops(B)+1,nops(B)+1,(i,j)->if j=nops(B)+1 then 0 else 1/2 fi);
%
\qu Expliquer le lien entre les r{\'e}seaux et le probl{\`e}me de trouver  un diviseur
d'un {\'e}l{\'e}ment de $\rela[X]$ lorsque l'on en connait un diviseur dans
$\rela/p^k\rela[X]$.
\end{document}
#pour maple
with(LinearAlgebra):
M:=Matrix([[1,2,3],[-1,0,1],[0,1,1]]);
# lattice attend une liste et non une Matrix ni une matrix
lattice(convert(M,listlist));
#On teste d'abord l'orthogonalisation
ortho:=proc(A);
b:=convert(Transpose(A),listlist);
#la liste des vecteurs b, bb son orthogonalise.
b:=[seq(Vector(i),i=b)];
n:=nops(b);#la dimension du reseau
bb:=b;
for i from 2 to n do
bb[i]:=simplify(b[i]-add((b[i].bb[j])/(bb[j].bb[j])*bb[j],j=1..i-1));
od;
mu:=Matrix(n,n,(i,j)->(b[i].bb[j])/(bb[j].bb[j]));
mu,bb;
end proc;
v:=ortho(M)[2];v[1].v[2],v[2].v[3],v[3].v[1];
#########################################
myLLL:=proc(A);
#Attention pour convertir en des Vecteurs par cette intruction il faut transposer
b:=convert(Transpose(A),listlist);
#la liste des vecteurs b, bb son orthogonalise.
b:=[seq(Vector(i),i=b)];
n:=nops(b);#la dimension du reseau
bb:=b;
for i from 2 to n do
bb[i]:=simplify(b[i]-add((b[i].bb[j])/(bb[j].bb[j])*bb[j],j=1..i-1));
od;
mu:=Matrix(n,n,(i,j)->(b[i].bb[j])/(bb[j].bb[j]));
#BB= les carre des normes des b^*
BB:=[seq(bb[i].bb[i],i=1..n)];
k:=2;
#
while ( k<n+1)
do
if abs(mu[k,k-1])> 0.5 then
       r:=round(mu[k,k-1]);
       b[k]:=b[k]-r*b[k-1];
       for j from 1 to k-2 do mu[k,j]:=mu[k,j]-r*mu[k-1,j];od;
       mu[k,k-1]:=mu[k,k-1]-r;
fi;
if ( BB[k] < BB[k-1]*(3/4-mu[k,k-1]^2))
then
mk:=mu[k,k-1];#on sauve l'ancienne valeur de mu[k,k-1]
 #cc=norme de c^*_{k-1} au carre
 cc:=BB[k]+mk^2*BB[k-1];
#on remplace mu[k,k-1] par la valeur de nu_{k,k-1} 
mu[k,k-1]:=mk*BB[k-1]/cc;
for i from k+1 to n do
mik:=mu[i,k-1];#on sauvegarde
mu[i,k-1]:=mu[i,k-1]*mu[k,k-1]+mu[i,k]*BB[k]/cc;
mu[i,k]:=mik-mu[i,k]*mk;
od;
for j from 1 to k-2 do
mkj:=mu[k,j];mu[k,j]:=mu[k-1,j];mu[k-1,j]:=mkj;
od;
#on echange b_k et b_{k-1}
c:=b[k];b[k]:=b[k-1];b[k-1]:=c;
#on corrige le carre des normes de b^*
BB[k]:=BB[k-1]*BB[k]/cc;BB[k-1]:=cc;
k:=max(2,k-1);
else
for l from k-2 by -1 to 1
   do
   if abs(mu[k,l])>0.5 then
   r:=round(mu[k,l]);b[k]:=b[k]-r*b[l];
   for j from 1 to l-1 do mu[k,j]:=mu[k,j]-r*mu[l,j] od;
   mu[k,l]:=mu[k,l]-r;
   fi;
  od;
k:=k+1;
fi;
od;
b;
 end proc;
##############
 myLLL(M);
#verification. lattice travaille sur les lignes
 Transpose(Matrix(lattice(convert(Transpose(M),listlist))));
##########
#sac {\`a} dos
s:=rand(200)():A:=[s]:for i from 1 to 6 do
s:=s+rand(200)():A:=[op(A),s]: od;
M:=2001;w:=101;igcd(w,M);
B:=[seq(modp(w*i,M),i=A)];
e:=[1,0,1,0,0,0,1];# le message a transmettre.
c:=add(e[i]*B[i],i=1..nops(B));
M:=Matrix(nops(B)+1,nops(B)+1,(i,j)->if i=j-1 then 1 else 0 fi);
M[nops(B)+1,1]:=c;for i from 1 to nops(B) do M[nops(B)+1,i+1]:=B[i]
od:M;
myLLL(M);# la premiere colonne est bien le message e
#ou bien avec l'instruction maple: 
lattice(convert(Transpose(M),listlist));# la premiere ligne est le message
