Abonnez-vous

Accélérer les multiplications d'entiers


Hervé Lehning

Les nombres complexes semblent très éloignés des questions de rentabilité du monde moderne. Pourtant, ils sont à l'origine de méthodes utilisées pour accélérer les multiplications de grands nombres entiers. Ils permettent de gagner du temps, beaucoup de temps… et donc de l'argent !


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

A = a + b x N + c x N2 + ...

a, b, c… 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 n2 multiplications de nombres à un chiffre, puis environ n additions (ce qui est, en pratique, «négligeable» devant les n2 multiplications précédentes). En utilisant un ordinateur, le temps de calcul est ainsi proportionnel à n2. 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(ω), A(ω2)… A(ωn-1), où A(X) = a + bX + cX2 +…   et

  ω = cos(2πn) + sin(2πn) (voir l’encadré sur les racines de l’unité).

Ce calcul demande a priori n2 multiplications, donc un temps de calcul proportionnel à n2, mais en fait une méthode subtile permet de l’effectuer dans un temps proportionnel à n ln (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 :

a + b + c + … = A(1),

a + bω + cω2 + … = A(ω),

a + bωn-1 + cω2(n-1) + … = A(ωn-1),

dans lequel les inconnues sont a, b, c

Comme la somme des racines nèmes de l’unité est nulle (voir l’encadré), il suffit d’ajouter toutes les équations pour obtenir a = [A(1) + A(ω) + … + A(ωn-1)] / n.

De même, on obtient b en multipliant la dernière équation par ω, l’avant-dernière par ω2, etc. : b = [A(1) + ωn-1 A(ω) + … + ω A(ω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(ω) = A(ω) B(ω), 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 n2. 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 N2 + d N3 + e N4 + ... On sépare les termes d’ordre pair de ceux d’ordre impair : A0 = a + c N + e N2 + ...  et  A1 = b + d N + ... En considérant les polynômes associés, cela donne A(X) = A0(X2) + X A1(X2). Si ω = cos (2π / 2n) + i sin (2π / 2n), alors ω2 = cos(2π / n) + i sin(2π / n), donc les formules 

A(1) = A0(1) + A1(1), 

A(ω) = A0(ω2) + ω A1(ω2)

... 

A(ωn-1) = A0(ω2(n-1)) + ωn-1 A1(ω2(n-1)

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.