INFORMATIQUE ET VÉRITÉ MATHÉMATIQUE

Carte mentale

Élargissez votre recherche dans Universalis

« 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 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 [...]



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 07 décembre 2019. URL : http://www.universalis.fr/encyclopedie/informatique-et-verite-mathematique/