En base $10$, un nombre s’écrit sous la forme d’une somme de puissances de $10$. Ainsi, $307$ s’écrit $7 \times 1 + 0 \times 10 + 3 \times 10^2.$ De la même manière, dans une base $N$ (que l’on suppose « grande »), un entier $A$ s’écrit

\begin{align*} A = a + b \times N + c \times N^2 +\dots \end{align*}

où $a, b, c\dots $ sont des nombres entiers compris entre $0$ et $N – 1$. Pour multiplier deux nombres à $n$ chiffres, en utilisant l’algorithme classique enseigné à l’école élémentaire, on effectue $n^2$ multiplications de nombres à un chiffre, puis environ $n$ additions (ce qui est, en pratique, « négligeable » devant les $n^2$ multiplications précédentes). En utilisant un ordinateur, le temps de calcul est ainsi proportionnel à $n^2$. Si vous doublez le nombre de chiffres, vous multipliez le temps de calcul par quatre. Bien entendu, ceci n’est « visible » que pour les nombres de plusieurs milliers de chiffres.

On peut cependant considérablement améliorer cette performance au moyen de la transformée de Fourier, dont la définition passe par le domaine complexe.

La transformation de Fourier discrète

Un nombre $A$ à $n$ chiffres étant donné, on lui associe le n-uplet $T(A)$ de nombres complexes suivant : $A(1), A(\omega ), A(\omega ^2),\dots, A(\omega ^{n-1}),$ où $A(X) = a + bX + cX^2 +\cdots$ et
$\omega  = \cos(2\pi / n) + i \sin(2\pi/ n)$ (voir l’encadré sur les racines de l’unité à la fin de cet article).

Ce calcul demande a priori $n^2$ multiplications, donc un temps de calcul proportionnel à $n^2$, mais en fait une méthode subtile permet de l’effectuer dans un temps proportionnel à $n \ln n$ (où $\ln n$ désigne le logarithme népérien de $n$), ce qui est beaucoup plus rapide ! Par exemple, cela fait passer d’un million d’opérations à sept mille, ou encore d’un milliard d’opérations à trois cent mille, ce qui est considérable. Dans la pratique (c’est-à-dire pour les ordinateurs), on préfère parler de complexité de calcul plutôt que de « temps de calcul », ce qui correspond à une modélisation pertinente de ce temps de calcul. On l’effectue en comptant le nombre d’opérations nécessaires, en se restreignant aux plus gourmandes en temps, ici les multiplications ordinaires.

L’intérêt de la transformation $T$, appelée transformation de Fourier discrète de $A$, est d’être inversible, c’est-à-dire que la connaissance de $T(A)$ permet de reconstituer $A.$ Le calcul consiste simplement à résoudre le système d’équations suivant :

\begin{align*}
a + b + c + \dots  &= A(1),\\
a + b \omega  + c \omega^ 2 + \dots  &= A(\omega ),\\
\vdots \\
a + b \omega ^{n-1} + c \omega ^{2(n-1)} + \dots  &= A(\omega ^{n-1}),\end{align*}

dans lequel les inconnues sont $a, b, c\dots $

Comme la somme des racines n-ième de l’unité est nulle (voir l’encadré dessous), il suffit d’ajouter toutes les équations pour obtenir $a = [A(1) + A(\omega ) + \dots  + A(\omega^{n-1})] / n.$

De même, on obtient $b$ en multipliant la dernière équation par $\omega ,$ l’avant-dernière par $\omega^ 2,$ etc. : $b = [A(1) + \omega^{n-1} A(\omega ) + \dots  + \omega A(\omega ^{n-1})] / n,$ et ainsi de suite. Le passage de $T(A)$ à $A$ est de même nature que celui de $A$ à $T(A),$ la seule différence est la division finale par $n$. La méthode rapide permet de l’effectuer dans un temps proportionnel à $n \ln n.$

Étant donnés deux nombres $A$ et $B,$ on peut calculer leurs transformées de Fourier discrètes $T(A)$ et $T(B)$ dans un temps proportionnel à $n \ln n.$ On les multiplie alors entre elles, pour obtenir $C(1) = A(1) B(1),$ $C(\omega ) = A(\omega ) B(\omega ),$ etc., ce qui demande $n$ multiplications.

Il est alors facile de reconstituer $C$ en un temps proportionnel à $n \ln n.$ On obtient donc le produit $C = A B$ en un temps proportionnel à $n \ln n$ au lieu de $n^2.$ Voila un intérêt de la transformée de Fourier discrète, et donc des nombres complexes : gagner du temps, donc de l’argent, dans les calculs arithmétiques ! Ceux-ci sont indispensables en cryptographie, d’utilisation constante (en particulier sur Internet).

Toujours plus vite

Supposons que $A$ possède $2n$ chiffres (ce que l’on peut toujours supposer en ajoutant un zéro en tête) : $A = a + b N + c N^2 + d N^3 + e N^4 + \dots$ On sépare les termes d’ordre pair de ceux d’ordre impair : $A_0 = a + c N + e N^2 + \dots$ et $A_1 = b + d N + \dots$ En considérant les polynômes associés, cela donne $A(X) = A_0(X^2) + X A_1(X^2)$. Si $\omega  = \cos(2\pi / 2n) + i \sin(2\pi/ 2n)$ , alors $\omega^2  = \cos(2\pi / n) + i \sin(2\pi/ n)$, donc les formules

\begin{align*}
A(1) &= A_0(1) + A_1(1),\\
A(\omega ) &= A_0(\omega ^2) + \omega A_1(\omega ^2​​),\\
\vdots \\
A(\omega ^{n-1}) &= A_0(\omega ^{2(n-1)}) + \omega ^{n-1} A_1(\omega ^{2(n-1)}), \end{align*}

montrent que, pour calculer une transformée de Fourier discrète d’un nombre à $2n$ chiffres, il suffit d’en calculer deux à $n$ chiffres, puis d’effectuer $n$ multiplications et $n$ additions. Si l’on note $c(n)$ le nombre de multiplications nécessaires pour calculer la transformée de Fourier discrète d’un nombre de $n$ chiffres, $c$ vérifie $c(2n) = 2 c(n) + n$. En résolvant cette relation de récurrence, on montre que $c(n)$ est de l’ordre de grandeur de $n \ln n$ (voir le calcul en encadré). Cela implique que les calculs de la transformée doivent se faire de façon récursive, en divisant successivement le nombre de chiffres par 2. Vous êtes alors en mesure de multiplier rapidement deux nombres, et le gain de temps, considérable, dans l’exécution de vos programmes vous offre un avantage certain sur ceux qui utilisent des algorithmes naïfs.