\documentclass[11pt]{amsart}
\usepackage[theo]{kbexo}
\def\Q{{\mathbb Q}}
\def\C{{\mathbb C}}
\def\R{{\mathbb R}}
\def\Z{{\mathbb Z}}
\def\w{\omega}

\begin{document}
\agregtitle{Multiplication rapide : Karatsuba et FFT} 

\section{Introduction}
La multiplication est une opération élémentaire qu'on utilise évidemment très
souvent, et la rapidité des nombreux algorithmes qui l'utilisent dépend
fortement de la rapidité de la multiplication.

Si l'on utilise la méthode classique, pour des polynômes, ou des entiers, le
coût en temps est quadratique. Nous présentons ici deux méthodes de
multiplication rapide sur les polynômes: l'algorithme de Karatsuba, puis un
algorithme utilisant la transformée de Fourier rapide, dite \emph{FFT}. Ce
dernier algorithme est particulièrement efficace, puisqu'il rend le coût en
temps de la multiplication quasi-linéaire. Plus précisément, ce coût, pour
des polynômes à coefficients dans $\C$ de degré inférieur à $n>1$, est en
$O(n\log n )$ opérations sur $\C$. Pour des polynômes de $A[x]$, où $A$
est un anneau quelconque, il est en $O(n\log n\log \log n))$ opérations dans
$A$.

Nous nous limitons ici aux polynômes, mais ces méthodes conduisent également
à des algorithmes de multiplication rapide des entiers.

L'algorithme de Karatsuba n'utilise que des notions élémentaires. La FFT
utilise la notion d'anneau quotient, et la notion de racine primitive de
l'unité dans $\C$, et plus généralement dans un anneau quelconque (cette
dernière notion est définie dans le texte).

\section{Algorithme de multiplication de Karatsuba}
 
Soit $A$ un anneau commutatif unitaire. Soient $f(x)=\sum f_ix^i$ et
$g(x)=\sum g_ix^i$ deux polynômes de $A[x]$ de degré inférieur à $n$. Le
calcul classique  du produit demande au plus $n^2$ multiplications pour les
$f_ig_j$, et $(n-1)^2$ additions pour les $\sum_{i+j=k}f_ig_j$. Par exemple,
le produit $(ax+b)(cx+d)=acx^2+(ad+bc)x+bd$ utilise quatre multiplications et
une addition. Il y a une méthode simple pour faire mieux. On calcule $ac$,
$bd$, $u=(a+b)(c+d)$, et $ad+bc=u-ac-bd$, avec trois multiplications et
quatre additions. Le total des opérations est porté à sept, mais une
application récursive de la méthode va diminuer le coût total quand $n$ est
grand.

\medskip

On suppose que $n$ est une puissance de $2$. Soit $m= n/2$. On écrit
$f=F_1x^m+F_0$ et $g=G_1x^m+G_0$. Suivant l'idée expliquée ci-dessus pour
$n=1$, on écrit:
$$fg=F_1G_1x^n+((F_0+F_1)(G_0+G_1)-F_0G_0-F_1G_1)x^m+F_0G_0.$$
Donc la multiplication de $f$ et $g$ utilise trois multiplications
de polynômes de degré inférieur strictement à $m$ et quelques
additions de polynômes.

Ainsi, si $C(n)$ est le coût en nombre d'opérations sur $A$ de l'algorithme,
on a:
$$C(n)\leq 3C(n/2)+O(n).$$
On en déduit par récurrence que $C(n)$ est en
$O(n^{\log_2 3})$, donc en $O(n^{1.59})$.
C'est donc, au moins asymptotiquement, une bonne amélioration par rapport à
la méthode classique.

\medskip

Pour implémenter cet algorithme, on peut utiliser des tableaux pour
représenter des polynômes, ou bien utiliser les fonctions sur les polynômes
de Maple, et donc rentrer les polynômes en tant que tels. Alors, pour obtenir
$F_0$ et $F_1$, on peut par exemple utiliser \texttt{F1=quo(f,x\^{}m,'F0')}.

\section{Transformée de Fourier discrète sur $\C$}

Nous allons discuter un algorithme de multiplication de polynômes de $\mathbb
C[x]$ dans lequel le nombre d'opérations sur $\C$ est quasi-linéaire.

Soit $n$ un entier $>1$ et $\w\in\mathbb C$ une racine primitive
$n$-ème de l'unité. Nous allons identifier un polynôme
$f=\sum_{j=0}^{n-1}f_jx^j$ de degré strictement inférieur à $n$ avec le
vecteur $(f_0,\dots,f_{n-1})\in\mathbb C^n$ de ses coefficients. Au lieu de
travailler dans $\C[x]$, on travaille donc dans $\C^n$.

\begin{defi}
\begin{enumerate}
\item L'application linéaire
\begin{align*}
DFT_\w \colon \mathbb C^n &\to \mathbb C^n\\
f&\mapsto \hat f=\left(
\sum_{k=0}^{n-1}f_k,\sum_{k=0}^{n-1}f_k\w^k,\dots,\sum_{k=0}^{n-1}f_k\w^{(n-1)k}\right)
\end{align*}
est appelée la \emph{transformée de Fourier discrète}.

\item Le produit de \emph{convolution} de
$f=(f_0,\dots,f_{n-1})$ et $g=(g_0,\dots,g_{n-1})$ dans
$\C^n$ est le vecteur de $\C^n$
$$f*_ng=\left(\sum_{j+k\equiv l\mod n }f_jg_k\right)_{l\in\{0,\dots,n-1\}}.$$
On notera $f*_ng=f*g$ si aucune confusion n'est possible dans
le contexte.
\end{enumerate}
\end{defi}
\noindent Si $f=(f_0,\dots, f_{n-1})$ et $F=\sum_{k=0}^{n-1}f_kx^k$, alors
$\hat f=(F(1),F(\w),\dots,F(\w^{n-1})$.

Remarquons aussi que cette notion de convolution correspond à la
multiplication dans $\mathbb C[x]/(x^n-1)\mathbb C[x]$. En effet, si
$f=(f_0,\dots, f_{n-1})$,  $g=(g_0,\dots, g_{n-1})$
$F=\sum_{k=0}^{n-1}f_kx^k$, $G=\sum_{k=0}^{n-1}g_kx^k$, $h=f*_ng=(h_0,\dots
h_{n-1})$ et $H=\sum_{k=0}^{n-1}h_kx^k$, alors
$$H\equiv FG\mod x^n-1.$$

On peut démontrer que ce produit de convolution est compatible
avec $DFT_\w$, c'est-à-dire que
$$DFT_\w(f*g)=DFT_\w(f) \cdot DFT_\w(g),$$
où le produit $\cdot$ sur $\mathbb C^n$ est effectué composante par
composante. En fait, $DFT_\w$ définit un isomorphisme d'algèbres de
$(\mathbb C^n,+,*_n)$ dans $(\mathbb C^n,+,\cdot)$. La matrice de cet
isomorphisme est la matrice de Vandermonde $V_\w$ de $(1,\w,\dots ,
\w^{n-1})$
$$V_\w=\begin{pmatrix}
1 & 1 & 1 & \dots & 1 \\
1 & \w & \w^2 & \dots & \w^{n-1} \\
1 & \w^2 & \w^4 & \dots & \w^{2(n-1)} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
1 & \w^{n-1} & \w^{2(n-1)} & \dots & \w^{(n-1)^2} \end{pmatrix}.$$
Comme $1$, $\w, \dots, \w^{n-1}$ sont deux à deux distincts, la
matrice $V_\w$ est inversible. Son inverse donne la matrice permettant de
calculer le polynôme d'interpolation en les points $1$, $\w, \dots,
\w^{n-1}$, c'est-à-dire, les valeurs $a_i$ étant fixées pour
$i\in\{0,\dots n-1\}$, de calculer l'unique polynôme $f$ de degré inférieur
ou égal à $n-1$ tel que $f(\w^i)=a_i$ pour tout $i$. Le théorème suivant
donne l'inverse de $V_\w$.

\begin{theo}
Si $\w\in\mathbb C$ est une racine primitive $n^{\hbox{ème}}$ de l'unité,
alors $\w^{-1}$ est aussi une racine primitive $n$-ème de
l'unité et $V_\w V_{\w^{-1}}=n\Id$, où $\Id$ est la matrice identité
de taille $n$.
\end{theo}
Revenons à notre problème, qui est de multiplier deux polynômes $F$ et $G$.
On suppose que deg$(FG)\leq n-1$. La transformée de Fourier discrète revient
à évaluer $F$ et $G$ sur $n$ points, ce qui suffit pour les définir. Dans
cette représentation, la multiplication est rapide à calculer, puisque pour
tout $i$ dans $\{0\dots n-1\}$, $FG(\w^i)=F(\w^i)G(\w^i)$. Cela
nous ramène à $n$ multiplications dans $\mathbb C$. Ensuite, comme on connaît
le produit $FG$ sur $n$ points, et comme deg$(FG)\leq n-1$, on peut
reconstituer $FG$. Ici, on peut utiliser l'application inverse de
$DFT_\w$, c'est-à-dire $\frac1nDFT_{\w^{-1}}$.

\bigskip

Voyons maintenant comment calculer rapidement la transformée de Fourier
discrète. On peut utiliser pour cela l'algorithme \emph{transformée de
Fourier rapide}, ou \emph{FFT}.

On suppose que $n=2^k$, où $n\in\NM$. Pour évaluer $F$ en $1, \dots ,
\w^{n-1}$, on divise d'abord $F$ par $x^{n/2}-1$ et $x^{n/2}+1$:
$$F=q_0(x^{n/2}-1)+r_0=q_1(x^{n/2}+1)+r_1,$$
pour $q_0$, $r_0$, $q_1$, $r_1$ dans $\C[x]$ de degré
inférieur strictement à $n/2$. Nous n'avons besoin que de calculer
$r_0$ et $r_1$. Pour cela, on remarque que si $F=F_1x^{n/2}+F_0$,
alors $x^{n/2}-1$ divise $F-F_0-F_1$, et donc $r_0=F_0+F_1$.
De même, $r_1=F_0-F_1$. On n'a donc besoin que de $n$ opérations
dans $\C$ pour le calcul de $r_0$ et de $r_1$.
De plus,
$$F(\w^{2l})=r_0(\w^{2l})\hbox{ et
}F(\w^{2l+1})=r_1(\w^{2l+1})$$
pour tout $l\in\{0,\dots,n/2\}$. Il reste à évaluer $r_0$ en
les puissances paires de $\w$ et $r_1$ en les puissances
impaires de $\w$. Or, $\w^2$ est une racine primitive
$(n/2)^{\hbox{ème}}$ de l'unité. Soit $r_1'=r_1(\w x)$,
on est ramené à calculer $DFT_{\w^2}$ sur $r_0$ et
$r_1'$. Cette remarque permet un traitement récursif du
problème.

\medskip

Soit maintenant $T(n)$ le nombre d'opérations nécessaires
à l'algorithme FFT. Alors $T(n)=2T(n/2)+O(n)$. Ce qui mène
à $T(n)=O(nlog(n))$.

Soit $S$ est le nombre d'opérations nécessaires à la
multiplication, on trouve également que $S(n)=O(nlog(n))$.

\section{Transformée de Fourier discrète sur un anneau quelconque}
La FFT permet d'accélérer notablement
la multiplication dans $\C[x]$. La seule propriété de
$\C$ que nous avons utilisée pour cela est que $\C$
contient pour tout $n$ les racines $n$-ème
de l'unité. Nous voudrions utiliser le même procédé
dans le cas de $A[x]$, dans le cas où $A$ est un anneau
quelconque.

Si $A$ contient les racines $n$-ème de l'unité, et si $n$ est
inversible dans $A$, la même méthode s'applique. Sinon, il est possible
d'ajouter à l'anneau des racines de l'unité. Dans ce qui suit, $A$ est un
anneau commutatif et unitaire dans lequel $n$ est inversible.


\begin{defi}
On dit que $A$ contient une racine primitive $n$-ème de l'unité s'il
existe $\w$ dans $A$ tel que
\begin{enumerate}
\item $\w^n=1$
\item Pour tout diviseur premier $l$ de $n$, $\w^{n/l}-1$ n'est pas un
diviseur de $0$. C'est-à-dire, pour tout $a\in A\setminus\{0\}$,
$a\times (\w^{n/l}-1)\ne0$.
\end{enumerate}
\end{defi}

\misctitle{Exemples} $A=\C$, $A=\F_q$ où $q$ est une puissance d'un nombre
premier et où $n$ divise $q-1$. Si $A=\Z/(2^{2^k}+1)\Z$, et si $n=2^{k+1}$,
alors $2$ est une racine primitive $n$-ème de l'unité dans $A$.

\begin{prop}
Si $\w$ est une racine primitive $n$-ème de l'unité dans $A$, alors
pour tout $l\in\{1,\dots,n-1\}$, $\w^l-1$ n'est pas un diviseur de $0$. De
plus:
$$\sum_{j=0}^{n-1}\w^{lj}=0.$$
\end{prop}

Grâce à cette proposition, on peut montrer que l'algorithme décrit dans le
paragraphe précédent pour $\C$ s'applique également pour un anneau $A$
contenant une racine primitive $n$-ème de l'unité.

\bigskip

On ne suppose plus maintenant que $A$ contient des racines primitives
$n$-ème de l'unité, mais seulement que $2$ est inversible dans $A$.
On peut encore appliquer une méthode similaire. L'idée est de rajouter les
racines de l'unité qui manquent.

On suppose que $n$ est une puissance de $2$ et on pose $n=2^k$. On veut
multiplier entre eux deux polynômes $F$ et $G$ à coefficients dans $A$ tels
que deg$(FG\leq n)$. Soient $m=2^{\floor{k/2}}$ et $t=2^{\ceil{k/2}}$. On
définit les polynômes $F_0, \dots, F_{t-1}$, $G_0, \dots, G_{t-1}$ de degrés
strictement inférieur à $m$ tels que
$$F=\sum_{j=0}^{t-1}F_jx^{mj}\quad\text{et}\quad
  G=\sum_{j=0}^{t-1}G_jx^{mj}.$$
On pose alors:
$$F'=\sum_{j=0}^{t-1}F_j(x)y^j\quad\hbox{et}\quad
  G'=\sum_{j=0}^{t-1}G_j(x)y^j,$$
de sorte que $F(x)=F'(x,x^m)$ et $G(x)=G'(x,x^m)$. Le degré en $y$ de $F'G'$
est strictement inférieur à $2t\leq4m$. De plus, les coefficients de $F'G'$
sont des polynômes en $x$ de degré strictement inférieur à $2m$, de telle
sorte qu'il suffit de connaître leur image dans $D=A[x]/(x^{2m}+1)A[x]$.

On peut démontrer que l'image $\w$ de $x$ dans $D$ est une racine primitive
$4m^{\hbox{ème}}$ de l'unité dans $D$. On se retrouve donc dans la situation
précédente. Une analyse de l'algorithme montrerait que le coût en nombre
d'opérations est en $O(n\log n \log\log n)$ opérations dans $A$ (mais il est
déconseillé de se lancer dans cette analyse).

\section{Suggestions}

\begin{itemize}
\item Plusieurs affirmations sont données sans preuve. Le candidat est invité
à les démontrer.

\item Il pourra illuster sur des exemples certains des algorithmes proposés,
puis les implémenter et les commenter.

\item On peut aussi réfléchir à des applications
de ces algorithmes.
\end{itemize}
\end{document}
