INFORMATIQUE ET VÉRITÉ MATHÉMATIQUE

« Tel nombre est premier », « tels graphes sont isomorphes », « telle classification est complète », etc. Traditionnellement, en mathématiques, la certitude concernant de telles affirmations formelles ne peut résulter que d'une démonstration. La pratique, cependant, semble remettre en question certaines des idées communément admises en la matière. L'informatique n'introduit-elle pas une nouvelle conception de la vérité mathématique, conception incompatible avec celle, défendue depuis plus de deux millénaires, qui se fonde sur la seule intelligence humaine ?

Pour aborder ces questions, détaillons deux situations où clairement l'ordinateur joue un rôle central dans l'étude d'énoncés mathématiques. Dans chaque cas, nous verrons que l'idée de la démonstration hilbertienne – des axiomes et des règles de raisonnement, codifiés une fois pour toutes, fixant ce que l'on considère comme vrai – est remise en cause comme seul moyen d'atteindre la certitude mathématique.

Preuves probabilistes de primalité

La cryptographie a fréquemment besoin de grands nombres premiers (de cent chiffres décimaux et plus) et aucune méthode sûre ne permet aujourd'hui d'en produire dans un délai raisonnable. On utilise donc ce qu'on appelle des algorithmes probabilistes. Le test probabiliste de primalité de Fermat en fournit un exemple élémentaire : choisir un nombre entier a au hasard entre 2 et n–1 ; si a^n—1 est congru à 1 modulo n, c'est-à-dire si la division de a^n—1 par n a pour reste 1, déclarer que n est premier ; sinon, déclarer que n est composé. Ce test n'est pas un algorithme sûr, en ce sens qu'il est possible qu'il déclare premier un nombre qui ne l'est pas (l'inverse ne peut se produire d'après le petit théorème de Fermat). Cependant, le risque que le test se trompe est faible. En effet, si n est un nombre choisi aléatoirement parmi les nombres de cent chiffres, ce risque est inférieur à 2,8 × 10^—8 ; autrement dit, si le test probabiliste de Fermat déclare n premier, alors la probabilité pour que celui-ci soit véritablement premier est supérieure à 99,9 999 972 p. 100. Pour les nombres de deux cents chiffres, le risque d'erreur est inférieur à 3,9 × 10^—27. Pour mille chiffres, il devient inférieur à 1,2 × 10^—123.

D'autres méthodes – test de Solovay-Strassen, test de Rabin-Miller – permettent, pour un nombre donné n et selon le temps qu'on fixe pour le calcul, d'affirmer que n est premier, avec un risque d'erreur inférieur à ε, où ε est choisi comme on l'entend, ε = 10^—10 000 par exemple. Aussi exigeant que l'on soit, l'application d'une telle méthode conduit rapidement à la quasi-certitude cherchée – la décroissance du risque est exponentielle en fonction du temps de calcul accordé.

Aux yeux du mathématicien traditionnel, les nombres premiers que l'on obtient ainsi ne le sont pas du tout, car aucune démonstration au sens hilbertien n'est déductible du test. Cependant, peut-on avoir des doutes sérieux sur la nature première des nombres proposés lorsque le risque d'erreur est très petit, par exemple inférieur à la probabilité de gagner cent fois consécutivement au LOTO^® ? Sur un plan pratique, d'ailleurs, l'industrie et la banque, dont on connaît les exigences en matière de sécurité, utilisent ces algorithmes en toute confiance : chaque jour, des milliers de nombres premiers sont produits par ces méthodes et servent à faire fonctionner les protocoles cryptographiques utilisés pour sécuriser les échanges de données sur les réseaux informatiques. Aucun cas d'erreur n'a jamais été rapporté provenant d'un nombre qui n'aurait pas été premier et résultat de l'utilisation de ces méthodes probabilistes.[...]