INFORMATIQUE ET VÉRITÉ MATHÉMATIQUE

Carte mentale

Élargissez votre recherche dans Universalis

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 an—1 est congru à 1 modulo n, c'est-à-dire si la division de an—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.

Une telle situation montre qu'en dehors des preuves hilbertiennes classiques, il est possible d'atteindre une certitude quasi parfaite concernant des affirmations mathématiques et que ces méthodes, même dans des applications industrielles ou économiques cruciales, sont considérées comme fiables.

L'idée que le risque d'erreur ne soit pas nul choque le mathématicien puriste. Cependant, celui-ci doit s'interroger sur la possibilité d'erreurs dans les résultats démontrés par les mathématiciens eux-mêmes. Que penser par exemple de la démonstration du théorème de classification des groupes simples (terminée dans la décennie 1980) qui, si on regroupait tous les articles qui y contribuent, occuperait plus de dix mille pages, dont une seule pourrait invalider définitivement la totalité de la démonstration ?

De nombreuses erreurs jalonnent l'histoire des mathématiques : elles furent commises par les plus grands mathématiciens, et parfois restèrent ignorées de longues années. Ces cas le font soupçonner : la probabilité que certaines preuves humaines (conformes à l'idée traditionnelle) soient fausses est bien supérieure à celle qu'un algorithme probabiliste utilisé avec prudence laisse penser à tort qu'un nombre est premier.

1  2  3  4  5
pour nos abonnés,
l’article se compose de 4 pages

Écrit par :

Classification

Voir aussi

Pour citer l’article

Jean-Paul DELAHAYE, « INFORMATIQUE ET VÉRITÉ MATHÉMATIQUE », Encyclopædia Universalis [en ligne], consulté le 28 avril 2022. URL : https://www.universalis.fr/encyclopedie/informatique-et-verite-mathematique/