\documentclass[a4paper,12pt]{amsart}
\usepackage{kbexo}


%%%%%%%%%%%%%%%%%%%%%
%% Alice's packages
%%%%%%%%%%%%%%%%%%%%%
\usepackage{xcolor}

%%%%%%%%%%%%%%%%%%%
%% Alice's macros
%%%%%%%%%%%%%%%%%%%
\newcommand{\comment}[1]{{\color{gray}#1}}

\def\pow{\^{}\hskip0pt}
\def\gets{\leftarrow}

\course{Algèbre et calcul formel -- Agrégation}
\num{7}

\begin{document}
\exotitle[Algorithme d'Euclide et applications]

\exo[Algorithme d'Euclide]
Programmer l'algorithme d'Euclide {\tt AE} et l'algorithme d'Euclide étendu
{\tt AEE}. À l'aide de votre fonction AEE, programmer la fonction {\tt
Inverse(k,n)} qui pour deux entiers $k$ et $n$ premiers entre eux calcule
l'inverse de $k$ modulo $n$. Quelle est la complexité (en nombre d'opérations sur les bits) de votre fonction {\tt Inverse}? (On aura le droit de supposer que la fonction {\tt AEE} a la même complexité que celle vue dans le cours.)

Bien sûr, ce n'est qu'un exercice : sur sage, on peut par exemple
utiliser la commande
{\tt mod(k,n)**(-1)}, ou bien
{\tt mod(k,n)**(-1).lift} si l'on veut le résultat dans $\ZM$.

\exo[Autour de Bézout]

\Q Le logiciel sage permet de calculer le pgcd de deux entiers à l'aide de la
commande {\tt gcd}. La commande {\tt xgcd} donne en plus les coefficients de
Bézout. En utilisant cette commande, écrire un algorithme qui prend en entrée
une liste d'entiers $[a_1,\dots,a_n]$ et donne en sortie $[u_1, \dots,
u_n]\in\ZM^n$ tel que
$$\sum_{i=1}^n a_i u_i = \pgcd(a_1,\dots,a_n).$$
Quelle est la complexité de cet algorithme (en nombre d'opérations binaires, en supposant que tous les $a_i$ sont en valeur absolue $\leq N$ pour un un certain entier $N> 0$ dont on se servira pour exprimer la complexité) ?


\Q À partir du résultat donné par l'algorithme d'Euclide étendu,
trouver une matrice $U$ entière de déterminant $\pm 1$ telle que $(a,b)U =
(\pgcd(a,b), 0)$.
Quelle est la complexité de cet algorithme (en nombre d'opérations binaires) ?

\Q En s'inspirant de la question précédente, montrer qu'il existe une
matrice $U$ dans $\Gl(n,\ZM)$ (entière, de déterminant $\pm 1$) telle que
$$(a_1,\dots,a_n)U = (\pgcd(a_1,\dots,a_n), 0, \dots, 0),$$
et programmer le calcul de cette matrice.\\
\noindent\comment{(Indice: ne traiter que 2 coordonnées à la fois)}\\
Quelle est la complexité de cet algorithme (en nombre d'opérations binaires) ?


\begin{mynote} Cette question est une version ``concrète'' (d'un cas
particulier) du théorème des diviseurs élémentaires pour les modules de
type fini sur les anneaux principaux \hint{appliqué au dual $(\ZM^n)^*$ et
au sous $\ZM$-module engendré par la forme linéaire $(a_1,\dots,a_n)$}. Les
diviseurs élémentaires sont donnés par le membre de droite.
\end{mynote}


\Q Si $b$ et $(a_1,\dots,a_n)$ sont
des entiers fixés, expliquer comment résoudre l'équation $\sum a_i x_i = b$
en nombre entiers $(x_i)$ en utilisant l'algorithme de la question précédente (on veut trouver toutes les solutions). Résoudre les
équations $1009x + 345 y + 56z = 1$ et $143 x + 195 y + 165 z = 3$. 

%\Q Comment résoudre un système de plusieurs équations sur $\ZM^n$ ?
%\hint{la question précédente permet de se ramener à un système triangulaire}

\exo[Restes Chinois]

%\Q Donner un algorithme permettant de décider si un entier $x$ est inversible
%dans $(\ZM/n\ZM)^*$, et le cas échéant de déterminer son inverse.
%Quelle est la complexité de votre algorithme en nombre d'opérations binaires (en fonction de $n$, en supposant $|x| < n$) ? \comment{(S'il est exponentiel, essayez d'obtenir un algorithme polynomial)}

\Q Résoudre les systèmes
$$
\left\{
\begin{aligned}
x&\equiv-1\mod21\\
x&\equiv11\mod15\\
x&\equiv1\mod10
\end{aligned}
\right.
\hbox{ et }
\left\{
\begin{aligned}
x&\equiv-1\mod21\\
x&\equiv10\mod15\\
x&\equiv1\mod10
\end{aligned}
\right.
$$
(on pourra utiliser la commande {\tt crt}).

\begin{mynote}
Cette commande {\tt crt} s'applique à tout anneau où l'algorithme des restes
chinois s'applique, par exemple à $k[x]$, où $k$ est un corps.
\end{mynote}

On connaît bien l'algorithme correspondant dans le cas où les modules sont deux
à deux premiers entre eux. Il ne s'applique pas tel quel aux exemples
précédents. Les questions suivantes portent sur le cas général.

\Q Soient $a$ et $b$ deux entiers $>0$. On considère le système d'inconnue $N$
$$\left\{
\begin{array}{rcl}
N & \equiv & \alpha \pmod{a}\\
N & \equiv & \beta  \pmod{b}
\end{array}
\right.$$
et on pose $\delta = \pgcd(a,b)$, puis $u$ et $v$ deux entiers tels que $au+bv =
\delta$.
\qq Montrer que le système n'a pas de solution si $\alpha \not\equiv \beta
\pmod{\delta}$.
\qq Sinon, montrer que  
$$N := \alpha + u \frac{a}{\delta} (\beta-\alpha)
     = \beta + v \frac{b}{\delta}(\alpha-\beta)
     = u \frac{a}{\delta}\beta + v \frac{b}{\delta}\alpha $$
convient. Montrer que cette solution est unique modulo $ab / \delta$.

\begin{mynote} c'est une généralisation du ``théorème chinois'' au cas ou
les modules ne sont pas nécessairement premiers entre eux. Si $\delta =
\pgcd(a,b) = 1$, on trouve bien un isomorphisme (explicite) entre $\ZM/a\ZM
\times \ZM/b\ZM$ et $\ZM/ab\ZM$ (qui à $(\alpha,\beta)$ associe $N$).
\end{mynote}

\Q En déduire un algorithme pour résoudre un nombre quelconque de congruences
simultanées, et le programmer. Il s'agit là d'un exercice. Pour ce calcul, il
faudra ensuite utiliser la commande {\tt crt} (comme dans la première question de l'exercice).\\
Quelle est la complexité binaire de l'algorithme ? \comment{(Comme d'habitude, on suppose que tous les entiers donnés en entrée sont $\leq N$.)}

\Q Après une série de rapines, une troupe de 14 pirates partage
(équitablement) le butin et laisse le reliquat, 3 écus, au cuisinier chinois,
le $15^{\text{ème}}$ homme d'équipage. Le lendemain, un flibustier tombe à la
mer et n'est pas repéché à temps; après avoir envisagé le versement de sa
part à des \oe uvres, les pirates refont le partage en incluant sa part; le
cuistot reçoit 2 écus. La semaine se passe sans encombres, mais trois pirates
ivres se disputent sur leurs parts respectives et deux d'entre eux sont tués.
Notre cuisinier récupère 5 écus. La fin du mois est mauvaise et 3 pirates
périssent dans une embuscade; mais le cuistot est content~: il garde ses 5
écus.

Quel magot peut-il espérer empocher quand il décide d'empoisonner le reste
de la bande ?

\exo[Déterminant modulaire]
\noindent Soit $A\in M_n(\ZM)$. On se propose de calculer $\det A$ de façon
modulaire, c'est-à-dire de calculer $\det A\pmod p$ à partir des $a_{i,j} \pmod
p$, pour des $p$ premiers et petits, et d'en déduire la valeur de $\det A$.
Pour cela il faudra prendre des $p$ dont le produit est plus grand que
$2 \cdot \vert\text{det}A\vert$ et se servir du lemme chinois. On rappelle l'inégalité
de Hadamard : 
$$\abs{\det A}^2 \leq \prod_{j=1}^n \Big(\sum_{i=1}^{n} a_{i,j}^2\Big),$$
qui aidera à déterminer une famille de $p$ adaptée.

\Q Écrire une procédure admettant en entrée $A$ et qui détermine
successivement une famille appropriée de premiers, les déterminants
modulaires puis le déterminant de $A$. Faire attention aux fonctions
\kbd{mod}$(*,d)$ ou $*\%d$ qui renvoient un entier de l'intervalle
$[0,d\,[$ et non de $]-\frac{d}{2},\frac{d}{2}]$. Quelle est la complexité binaire de votre algorithme (en fonction de $\max_{i,j} |a_{i,j}|$ et de $n$ ?)

\medskip
\textbf{Remarque :} L'intérêt de calculer le déterminant modulo des premiers, c'est qu'on n'a pas besoin de s'inquiéter de l'explosion de la taille des coefficients. Cela rend le calcul de la complexité binaire plus facile.

\Q Tester sur $A\in M_{10}(\ZM)$ où les $a_{i,j}$ sont aléatoires et
vérifient $\abs{a_{i,j}} < 100$. Étendre les tests.

\exo[Faire des expériences pour mesurer le temps]
On a vu en cours un algorithme pour calculer pgcd de deux entiers $a$ et $b$ $\leq N$ avec une complexité binaire $O(\log(N)^2)$. L'objectif de cet exercice est de déterminer si l'algorithme implémenté par Sage se comporte asymptotiquement en $\log(N)^2$, ou s'il fait mieux.

\Q Écrire une fonction qui prend en entrée deux entiers $N$ et $k$. L'algorithme répète $k$ fois : tirer $a$ et $b$ au hasard inférieurs à $N$, puis mesurer le temps pour calculer leur pgcd. À la fin, l'algorithme renvoie le temps moyen pour le calcul d'un pgcd (en moyennant sur les $k$ essais).

Pour mesurer le temps, on pourra utiliser la commande {\tt import time} (à utiliser une seule fois), puis la commande {\tt t = time.time()}, qui donne le temps à un moment de l'execution. En faisant
\begin{verbatim}
 t1 = time.time()
 bla
 blo
 t2 = time.time()
 print(t2-t1)
\end{verbatim}
on affiche le temps qu'il s'est écoulé entre le début et la fin des commandes {\tt blablo}.

\Q Se servir de la fonction précédente pour faire des expériences avec $N$ de plus en plus grand et mesurer le temps $T$ correspondant. 

On veut ensuite tracer les résultats, quelle échelle vaut-il mieux utiliser pour vérifier que la complexité est quadratique ? (I.e., est-ce qu'il faut afficher $T$, $\log T$, $\log \log T$, $\dots$ en fonction de $N$, $\log(N)$, $\log \log N$,$\dots$ ?)

Pour tracer des points, on peut définir un objet graphique {\tt g = Graphics()}. Ensuite on peut ajouter des points à cet objet graphique en faisant {\tt g = g+Point([x,y])} (on peut rajouter un argument {\tt color = 'red'} ou autre). Et enfin, on peut afficher {\tt g} en faisant {\tt plot(g)}. On peut aussi tracer des lignes avec la commande {\tt line}.

\Q Conclure: l'algorithme de Sage est-il quadratique?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Exercice de l'année dernière
%% (je pense que le TP est assez long)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\iffalse
\exo[Approximants de Padé]

On rappelle ici l'algorithme d'Euclide étendu appliqué à deux polynômes $F$
et $G\in K[X]$ où $K$ est un corps commutatif.
\begin{algorithm}[H]
\caption{Algorithme d'Euclide étendu}
\begin{algorithmic}[1]
\REQUIRE $F$, $G\in K[X]$
\ENSURE $\pgcd(F,G)$ et $A$, $B\in K[X]$ tels que $AF+BG=\pgcd(F,G)$
\STATE $A_0\gets1$, $B_0\gets0$, $R_0\gets F$ 
\STATE $A_1\gets0$, $B_1\gets1$, $R_1\gets G$
\STATE $i\gets1$
\COMMENT{initialisations}
\WHILE{$R_i\neq 0$} 
\STATE Soient $Q$ et $R_{i+1}$ le quotient et le reste de la division
euclidienne de $R_{i-1}$ par $R_i$.
\STATE $A_{i+1} \gets A_{i-1} - QA_i$ 
\STATE $B_{i+1} \gets B_{i-1} - QB_i$ 
\STATE $i \gets i+1$
\ENDWHILE 
\STATE Retourner le dernier $R_i$ non nul ainsi que les $A_i$ et $B_i$
correspondants.
\end{algorithmic}
\end{algorithm}
\noindent On rappelle également qu'à chaque étape de l'algorithme, si
$n_k = \deg R_k$, on a 
\begin{enumerate}
\item $A_iF+B_iG = R_i$
\item $\deg A_i = n_1-n_{i-1}$ (pour $i>1$)
\item $\deg B_i = n_0-n_{i-1}$ (pour $i>0$)
\end{enumerate} 
\smallskip
\noindent
\def\F{\mathcal{F}}
\Q Soient $\F = f_0+f_1X+f_2X^2+\cdots\in K[[X]]\quad
\text{et}\quad m,n\in \NM$.\\[1mm] 
On appelle \emph{approximant de Padé de type} $(m,n)$ de $\F$
un élément $(U,V)\in K[X]^2$ vérifiant
$$\left\{\begin{array}{l}V\neq 0,\,
\deg U\leq m\text{ et } \deg V\leq n\\[2mm]
V\F - U = X^{m+n+1}R,\text{ où } R\in K[[X]].
\end{array}\right.$$
\smallskip
\qq En posant $F=f_0+\cdots+f_{m+n}X^{m+n}$ et en appliquant l'algorithme
d'Euclide étendu à $F$ et $X^{m+n+1}$, montrer qu'un tel approximant existe.
\qq Soient $(U_0,V_0)$ et $(U,V)$ deux approximants de Padé de type $(m,n)$
de $\F$ tels que $V_0 U - U_0 V \neq 0$.
Que peut on dire sur le degré de ce déterminant ?
\qq En déduire que le quotient $U/V$ d'un tel approximant de Padé
est uniquement déterminé.
\Q Soit $\F$ une fraction rationnelle de $K(X)$ quotient de deux polynômes
$U$ et $V$ de $K[X]$ de degrés $\leq n$ et premiers entre eux mais que l'on
ne connaît pas. Supposons que l'on connaisse en revanche un développement en
série formelle de $\F$ en $0$ :
$$\F=f_0+f_1X+f_2X^2+\cdots$$
Comment à partir de ce développement retrouver $U$ et $V$ à une constante
multiplicative près ? Ce problème est appelé le problème de la reconstruction
rationnelle.
\Q Programmer une fonction qui résout ce problème et la tester sur des
exemples de quotients.
\Q On considère le problème suivant. On connaît un certain nombre $s$ de
termes consécutifs d'une suite $(u_n)$ satisfaisant une relation de
récurrence d'ordre $k$ :
$$u_{n+k}=a_{1}u_{n+k-1}+\cdots+a_ku_n.$$
On suppose que $s=2k$. 
\qq Soient
$$
A=1-\sum_{i=1}^ka_iX^i\quad\text{et}\quad \F = \sum_{i\geq0}u_iX^i
$$
Montrer que $A\F$ est un polynôme de degré inférieur ou égal à $k-1$.
\qq En déduire un algorithme permettant de calculer $A$ et programmer cet
algorithme.

\Q Essayer avec :
\begin{itemize}
\item 1, 1,\,\ldots ;
\item 3, 5, 8, 13,\,\ldots ;
\item 8, 13, 21, 34, 55, 89, 114\, \ldots ;
\item 1, 1, 1, 1, 10, 19, 46, 118,\, \ldots
\end{itemize}
\fi
\end{document}
