Comment multiplier les très grands nombres entiers ?

JR : Vous venez de vous faire remar­quer par la com­mu­nauté sci­en­tifique inter­na­tionale pour votre pub­li­ca­tion, avec David Har­vey de l’Uni­ver­sité de Nou­velle-Galles du Sud, d’une méth­ode révo­lu­tion­naire pour mul­ti­pli­er de très grands nom­bres entiers. Mais où est la nou­veauté ? On ne savait pas faire de multiplications ?

Des algorithmes en progrès continus

Si, bien sûr ! Mais les algo­rithmes de mul­ti­pli­ca­tion n’ont pas cessé de pro­gress­er. Il y a eu d’abord la méth­ode que nous apprenons tous à l’école pri­maire, qui remonte aux Baby­loniens. Cet algo­rithme sim­ple a une com­plex­ité en N² : c’est-à-dire que si vous prenez un très grand nom­bre, met­tons avec 1 mil­liard de chiffres (vous pou­vez tout à fait stock­er un nom­bre aus­si grand que ça dans votre smart­phone !), et que vous le mul­ti­pliez par lui-même, cela fera 10¹⁸ opéra­tions. Même avec un cal­cu­la­teur hyper­rapi­de, à rai­son d’une nanosec­onde par opéra­tion, cela fera tout de même 10⁹ sec­on­des, soit env­i­ron trente ans… On voit tout de suite qu’il faut s’y pren­dre autrement.

C’est dans les années 50 qu’un Russe, Ana­toli Karat­sou­ba, a mis au point un algo­rithme beau­coup plus rapi­de, qui per­met de mul­ti­pli­er des nom­bres assez grands. Cet algo­rithme est encore couram­ment util­isé aujourd’hui pour des nom­bres entre 100 et 1 000 chiffres, par exem­ple dans les opéra­tions de cryp­tolo­gie. Sa com­plex­ité est de N^log3/log2, soit N^1,58….

Traiter des nombres au-delà du millier de chiffres

Puis sont venues les méth­odes mod­ernes, basées sur la trans­for­ma­tion de Fouri­er rapi­de (FFT), inven­tées indépen­dam­ment par Pol­lard et Schön­hage-Strassen en 1971, qui per­me­t­tent de traiter des nom­bres au-delà du mil­li­er de chiffres. À l’époque, Schön­hage et Strassen ont con­jec­turé qu’on pour­rait trou­ver un algo­rithme encore plus rapi­de, avec une com­plex­ité en N Log N. C’est de cet algo­rithme que nous venons de prou­ver l’existence, avec mon col­lègue David Har­vey. Nous en avons prou­vé l’existence, et nous en avons don­né une descrip­tion explicite. Peut-on encore faire mieux et aller plus vite ? À vrai dire, on ne sait pas, mais je pense qu’on ne pour­ra pas. J’en serais en tout cas très éton­né, même si je ne peux pas prou­ver que c’est pos­si­ble. Mais il serait tout aus­si dif­fi­cile de prou­ver que ce n’est pas pos­si­ble !… C’est une vieille dif­fi­culté bien con­nue des math­é­mati­ciens : dans un prob­lème don­né, on prou­ve facile­ment qu’on a une borne supérieure, mais il est tou­jours beau­coup plus dif­fi­cile de prou­ver qu’il existe une borne inférieure.

A multiplication complexe algorithme complexe

On voit bien que la ques­tion sous-jacente est celle de la com­plex­ité des algo­rithmes : beau­coup de ces com­plex­ités d’algorithmes s’expriment en fonc­tion de la com­plex­ité de la mul­ti­pli­ca­tion. Par exem­ple, la com­plex­ité d’un algo­rithme pour cal­culer la N^ème déci­male de π est log N fois la com­plex­ité de la mul­ti­pli­ca­tion, c’est-à-dire
N (Log N)², avec notre nou­v­el algo­rithme. La mul­ti­pli­ca­tion des entiers joue un peu en infor­ma­tique le rôle de la vitesse de la lumière en physique.

Pour­ra-t-on appli­quer cet algo­rithme ? Ce ne sera pas chose facile, en tout cas pas avec la descrip­tion que nous en avons don­née. Mais nous avons util­isé pour notre recherche tout un tas de tech­niques intéres­santes en soi, qui pour­ront être utile­ment réu­til­isées pour amélior­er les algo­rithmes exis­tants, y com­pris pour des nom­bres de quelques mil­liards de chiffres. Au-delà, il existe encore beau­coup d’autres types d’algorithmes sur lesquels il y a des choses à trou­ver, ceux qui inter­vi­en­nent par exem­ple dans les cal­culs de la divi­sion, de PGCD, de cal­cul sur les polynômes, etc.

Pro­pos recueil­lis par Robert Ran­quet (72)

---

Articles similaires :

Struc­ture en ten­ségrité : con­struc­tion d’une passerelle Des bac­téries et des tholins, ou le secret de la vie révélé par Titan ? Thrustme : La start-up de l’X qui révo­lu­tionne le spatial “ Fibres de stress ” et anisotropie : cause ou effet Ma COP 25 Du Set pack­ing au taxi aérien autonome, ren­con­tre avec une jeune chercheuse en recherche opérationnelle