\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 \hspace{1cm}}\hfill   agreg 2007 (F.Han)}\\
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\code#1{{\tt #1}}
% interface(screenwidth=120);
\newtheorem{definition}{D\'efinition}
\newtheorem{proposition}{Proposition}
\section{Introduction}
On a souvent besoin de trouver rapidement un vecteur de "petite" norme
dans un r\'eseau. Par exemple, pour trouver un facteur d'un \'el\'ement de
$\rela[x]$ lorsqu'on en connait un dans $\rela/p^n\rela[x]$, mais
aussi pour briser le cryptosyst\`eme de type sac \`a dos. La m\'ethode
d\'ecrite ci dessous ne donne pas forc\'em\'ement un vecteur de norme
minimale, mais elle donne en revanche rapidement un vecteur de petite
norme. Elle fut publi\'ee en 1982 par Lenstra-Lenstra-Lovasz pour
factoriser des polyn\^omes \`a coefficients entiers, mais elle fut
appliqu\'ee ensuite dans bien d'autres situations. 
\section{Bases r\'eduites d'un r\'eseau}
   On dit que $L$ est un r\'eseau 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\'eterminant de $L$
   le nombre\footnote{ind\'ependant 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\'efinis par les formules de r\'ecurrence:
   $$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\'esigne 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\'eseau $L$ qu'elle est
  r\'eduite, si les deux conditions suivantes sont r\'ealis\'ees: 
  \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\'eduite
donne un vecteur de "petite"  norme du r\'eseau:
\begin{proposition}
  Si $(b_1,\dots,b_n)$ est une base r\'eduite d'un r\'eseau $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||^2 \leq 2^{\frac{n-1}{4}}d(L)^{\frac{1}{n}}
  \end{equation}
\end{proposition}
En effet, si $b$ est r\'eduite, 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 \'egal \`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\'eduit  (\ref{p3}) de (\ref{p1}) et (\ref{p2}).

A t'on utilis\'e le fait que $b$ soit r\'eduite pour l'in\'egalit\'e $d(L)\leq
\prod_{i=1}^n ||b_i||$?
%#non on n'a pas utilis\'e le fait que b soit reduite, c'est l'in\'ealit\'e d'Hadamard
\begin{proposition}
  Soit $L$ un r\'eseau de $\reel^n$, et $(b_1,\dots,b_n)$ une base
  r\'eduite 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\'eduction}
\def\.{

\noindent$\bullet$}
Soit $(b)$ une base d'un r\'eseau $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\'es. 

\smallskip
Nous allons effectuer une suite
d'\'etape (qui modifie un \'el\'ement  $k$ de $\{1,\dots,n+1\}$) commen\c cant
et se terminant de telle sorte que les propri\'et\'es 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\'erifier pour satisfaire
ces conditions. On peut donc
commencer l'algorithme avec $k=2$. Si les conditions pr\'ec\'edentes sont
satisfaites pour $k=n+1$, alors la base est r\'eduite, et l'on a
termin\'e.
%%
\. On r\'ep\`ete alors les \'etapes suivantes tant que $ k\leq n$:

\smallskip
$\diamond$ On aimerait avoir $|\mu_{k,k-1}| \leq \frac{1}{2}$. Si cette in\'egalit\'e
n'est pas v\'erifi\'ee, 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}$ \'etant
inchang\'es.

On distingue ensuite deux cas:

\bigskip
$\diamond$ {\sc Cas 1:} Si\footnote{On pourra trouver une condition \'equivalente
  ne d\'ependant 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 \'echange $b_k$ et $b_{k-1}$ 
sans toucher aux autres
$b_i$. Notons $c$ la base d\'eduite de $b$ o\`u l'on a \'echang\'e $b_k$ et
$b_{k-1}$, $c^*$ son orthonorgonalis\'ee, 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\'eussi \`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'\'egalit\'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 \'et\'e chang\'es, les
propri\'et\'es \ref{eq:k1} et \ref{eq:k2} restent vraies au rang
pr\'ec\'edent, 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\'et\'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\'egalit\'es en regardant pour $l$ variant de $k-2$ \`a $1$
si  $|\mu_{k,l}|>\frac{1}{2}$. Et si cette condition est v\'erifi\'ee,
alors on consid\`ere  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\'es par $\mu_{k,j}-r.\mu_{l,j}$ et
$\mu_{k,l}$ par $\mu_{k,l}-r$. Les autres $\mu$ et $b^*$ restent
inchang\'es.

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\^ut}
Il faut d'abord remarquer que l'algorithme pr\'ec\'edent se termine. On
consid\`ere pour cel\`a les nombres\footnote{On pourra justifier cette
  \'egalit\'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\'eduit d'un facteur
$\frac{3}{4}$, et les autres ne sont pas modifi\'es.

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\'el\'epip\`ede $b_1,\dots,b_i$ contient toujours un vecteur non nul
%%du r\'eseau: $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
%%\'el\'ement 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\'erations arithm\'etiques.

%#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
\section{Le probl\`eme du sac \`a dos; Cryptosyst\`eme de Merkle et Hellman}
Soit $(a_1,\dots,a_n,c)$ des entiers. Le probl\`eme 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\'erentes fa\c cons de remplir un sac \`a dos de hauteur $c$ avec des
batons de taille $a_i$? Sous cette g\'en\'eralit\'e ce probl\`eme est
consid\'er\'e comme tr\`es difficile, et l'on n'en connait pas de solution
polyn\^omiale 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\`eme a une solution unique que
l'on trouve rapidement.

L'id\'ee de Merkle et Hellman \'etait donc de prendre pour clef secrete
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\'eordonne pas les $(b_i)$ dans l'ordre croissant). La clef publique
est alors la donn\'ee de $(b_i)$, et pour crypter un message ecrit en
base 2 $\epsilon_1,\dots,\epsilon_n$, on transmet gr\^ace \`a la clef
publique: $c=\sum_{i=1}^n \epsilon_i.b_i$. R\'esoudre ce probl\`eme
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\`eme du sac \`a dos en $(b)$
reposant sur LLL. Consid\'erons 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\'erisant le message$
\left(\begin{array}[c]{c}
    \epsilon_1\\
    \vdots\\
    \epsilon_n\\
    0 
\end{array}\right)
$ est un vecteur du r\'eseau engendr\'e par les colonnes de $M$, de norme
petite puisqu'elle est major\'ee par $\sqrt{n}$. On a donc de bonnes
chances de le trouver par LLL.
\section{D\'eveloppements}
\qusqu On pourra impl\'ementer l'algorithme d'orthogonalisation, pour
obtenir $(b^*)$ et $(\mu)$.
%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];
\squ On pourra impl\'ementer l'algorithme d\'ecrit ci dessus. On pourra
aussi regarder s'il n'est pas d\'ej\`a impl\'ement\'e dans votre logiciel 
favori\footnote{par exemple maple7, xcas, \dots (Attention maple7 n'a
  pas le package   \code{IntegerRelations})} et
v\'erifier sur des exemples.
% #########################################
% 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))));
\qu Expliquer pourquoi l'algorithme se termine, et le calcul du co\^ut.
\qu Expliquer et illustrer la faille du sac \`a dos.
% ##########
% #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
\qu Expliquer le lien entre trouver un diviseur d'un \'el\'ement dans
$\rela[X]$ lorsque l'on en connait un diviseur dans
$\rela/p^k\rela[X]$ et les r\'eseaux.
\end{document}
//pour giac xcas
M:=matrix([[1,2,3],[-1,0,1],[0,1,1]]);
//On teste d'abord l'orthogonalisation des lignes.
ortho:=proc(A)
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]:=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];
