Suffisamment puissants, des ordinateurs quantiques permettraient un jour d'accélérer considérablement l'exploration de certaines questions de théorie des nombres. Si l'on parvient à les réaliser, un nouvel algorithme quantique pourrait alors montrer rapidement que la fameuse hypothèse de Riemann sur les nombres premiers est fausse.

au sommaire


    Dans leur célèbre ouvrage Mathematics and Logic publié en 1968, les mathématiciensmathématiciens Mark Kac et Stanislaw Ulam ont tenté de montrer l'extraordinaire variété et la force de la pensée mathématique depuis l'époque du miracle grec. Ayant participé à la montée en puissance des premiers ordinateursordinateurs en physique et en mathématique lorsqu'il a découvert avec Edward Teller les clés de la bombe à hydrogène, Ulam était particulièrement bien placé pour saisir le potentiel des travaux d'Alan Turing et de son ami John von Neumann. Les auteurs de Mathematics and Logic étaient donc parfaitement conscients de l'impact grandissant des ordinateurs : non seulement par l'intermédiaire des simulations numériquessimulations numériques, de la manipulation des systèmes formels anticipée par Leibniz, mais aussi sur ce que l'on pourrait appeler les mathématiques expérimentales, notamment en théorie des nombres.

    Sur ce dernier point en particulier, on aurait une fausse idée d'une partie de la dynamique de la pensée mathématique en tenant pour acquis que les découvertes se font toujours en développant des raisonnements selon le modèle légué par EuclideEuclide (celui communément enseigné à l'école en géométrie). Gauss lui-même, probablement l'un des plus grands théoriciens des nombres, a clairement affirmé que plusieurs de ses découvertes provenaient de jeux et d'expérimentations avec les nombres alors qu'il recherchait leurs propriétés remarquables. C'est en observant une table de nombres premiers vers l'âge de 15 ans environ que le jeune Gauss fut amené à conjecturer une formule permettant d'estimer la répartition des nombres premiers, et donc leur nombre entre 2 et un entier n donné.

    Georg Friedrich Bernhard Riemann (1826-1866) était un mathématicien de génie. Ses contributions en analyse, géométrie et théorie des nombres sont légendaires : des espaces courbes à n dimensions jusqu'à la topologie, en passant par l'analyse complexe et la théorie de l'intégration. Il a anticipé la théorie de la relativité générale. © DP

    Georg Friedrich Bernhard Riemann (1826-1866) était un mathématicien de génie. Ses contributions en analyse, géométrie et théorie des nombres sont légendaires : des espaces courbes à n dimensions jusqu'à la topologie, en passant par l'analyse complexe et la théorie de l'intégration. Il a anticipé la théorie de la relativité générale. © DP

    Un million de dollars pour l'hypothèse de Riemann

    La conjecture de Gauss conduisit à divers travaux remarquables, dont celui de la démonstration du fameux théorème des nombres premiers (démontré indépendamment par Hadamard et de la Vallée Poussin en 1896), et surtout à la célèbre hypothèse de Riemann. Ce dernier fut d'ailleurs l'élève de Gauss.

    Rappelons que Riemann a formulé son hypothèse éponyme en 1859, à l'occasion de ses travaux sur la répartition des nombres premiers et sur la formule exacte indiquant combien il y a de nombres premiers entre 2 et n. Elle ne traite pas directement de la détermination de cette fonction, mais sa validité est équivalente à celle d'une formule décrivant cette fonction pour de grandes valeurs de n.

    La démonstration de l'hypothèse de Riemann aurait des répercussions sur plusieurs résultats ou conjectures en mathématique. C'est pourquoi elle est l'un des fameux 23 problèmes de Hilbert proposés en 1900. Aujourd'hui encore, cette hypothèse reste l'un des problèmes mathématiques non résolus les plus importants du début du XXIe siècle. Ainsi, elle fait partie des sept défis mathématiques réputés insurmontables par le Clay Mathematics Institute en 2000, une récompense d'un million de dollars étant promise pour la résolutionrésolution de chacun d'eux. L'hypothèse de Riemann figure en tête de liste, devant la conjecture de Poincaré, un défi remporté et récompensé en 2010 par le Russe Gregoriy Perelman.

    L'informatique quantique adaptée à la cryptographie

    Mais quel est le rapport entre les ordinateurs et l'hypothèse de Riemann ? Il se trouve que l'on se sert des calculateurs depuis longtemps pour trouver de grands nombres premiers. L'utilisation des grands nombres premiers pour la cryptographiecryptographie, par exemple pour sécuriser les transactions bancaires, reflète l'importance des études sur ce sujet. Ainsi, pour factoriser en un produit de deux nombres premiers un nombre d'environ 300 chiffres, il faudra en général plus de 100.000 ans avec un ordinateur actuel et un algorithme classique. On comprend donc aisément pourquoi la cryptographie emploie souvent comme clé des grands nombres, qui se décomposent en produits de deux nombres premiers.

    Jacques Salomon Hadamard (1865-1963) est un mathématicien français, connu notamment pour ses travaux en théorie des nombres. On lui doit la transformée d'Hadamard, qui a de nombreuses applications ou conséquences en théorie de l'information quantique et en cryptologie. © DP

    Jacques Salomon Hadamard (1865-1963) est un mathématicien français, connu notamment pour ses travaux en théorie des nombres. On lui doit la transformée d'Hadamard, qui a de nombreuses applications ou conséquences en théorie de l'information quantique et en cryptologie. © DP

    Or, en 1994, le mathématicien américain Peter Shor a découvert un algorithme mathématique exploitant les propriétés du calcul quantique, qui peut déterminer la factorisation en nombres premiers d'un entier donné. Tournant sur un ordinateur quantique suffisamment puissant, il serait donc possible avec un tel algorithme de casser très rapidement certains codes utilisés en cryptographie. En effet, on sait, au moins sur la plan théorique, que l'algorithme de Shor devrait faire partie de ceux capables de largement surpasser leurs équivalents en informatique classique pour de grands nombres entiers. Sur la plan pratique, il faudrait que l'ordinateur dispose d'un nombre suffisant de qubits (unités de stockage de l'informatique quantique) et soit protégé de l'influence de la décohérence.

    Inspirés par la puissance du calcul quantique sur cette question d'arithmétique, deux chercheurs espagnols de l'université de Barcelone ont tenté de l'utiliser pour en savoir plus sur l'hypothèse de Riemann. L'explication de leur découverte a été publiée dans un article sur arxiv.

    Une invalidation indirecte de l'hypothèse de Riemann ?

    Il ne s'agit pas de démontrer l'hypothèse de Riemann, mais de tenter de l'infirmer indirectement en avançant un contre-exemple, c'est-à-dire en trouvant, si possible, un entier n conduisant à une violation de la formule donnant le nombre de nombres premiers entre 2 et n. La stratégie n'est pas complètement nouvelle, puisque d'autres ont exploré cette voie, allant jusqu'à n=1024. Au vu de l'état actuel de la puissance des ordinateurs, un calcul avec n=1025 prendrait neuf mois. 

    Pour contourner cet obstacle, les deux chercheurs ont trouvé un algorithme quantique qui permettrait de calculer le nombre de nombres premiers compris entre 2 et n. Ils supposent que cet algorithme quantique devrait être plus rapide que son analogue classique. S'ils ont raison, il faudrait malheureusement disposer d'une grande quantité de qubits intriqués (80). On est encore très loin d'une telle performance, et il n'est pas certain qu'on y parvienne un jour, tant l'obstacle de la décohérence semble redoutable. Le phénomène de décohérence est très complexe, et entraîne chez certains objets des comportements n'obéissant plus aux lois quantiques.