Comment construire un grand nombre premier | Quanta Magazine

Les nombres premiers sont des choses délicates. On apprend à l'école que ce sont des nombres sans facteurs autres que 1 et eux-mêmes, et que les mathématiciens savent depuis des milliers d'années qu'il en existe un nombre infini. En produire un sur commande ne semble pas être difficile.

Mais il est. Construire des nombres premiers arbitrairement grands est remarquablement compliqué. Vous avez essentiellement deux options de calcul, toutes deux avec des inconvénients. Vous pouvez utiliser le hasard et en trouver un en devinant, mais la méthode est incohérente - vous courez le risque de générer un nombre premier différent à chaque fois. Ou vous pouvez utiliser un algorithme déterministe plus fiable, mais à un coût de calcul élevé.

En mai, une équipe d'informaticiens montré qu'une sorte d'approche hybride pourrait également fonctionner. Ils ont publié un algorithme qui combine efficacement les approches aléatoire et déterministe pour produire un nombre premier d'une longueur spécifique, avec une forte probabilité de fournir le même même si l'algorithme est exécuté plusieurs fois. L'algorithme relie le hasard et la complexité de manière intéressante, et il pourrait également être utile pour la cryptographie, où certains schémas de codage reposent sur la construction de grands nombres premiers.

"Ils ont présenté une séquence de tentatives, chacune essayant de construire un nombre premier d'une longueur différente, et ont montré que l'une des tentatives fonctionnait", a déclaré Roi Tell, un informaticien théoricien de l'Institute for Advanced Study qui n'a pas participé aux travaux. "C'est une construction qui produit un nombre premier choisi de manière déterministe, mais vous permet de lancer des pièces et de faire des choix aléatoires dans le processus."

Le défi de créer une recette efficace pour les nombres premiers a des racines profondes. "Nous ne savons vraiment pas grand-chose sur la façon dont les nombres premiers sont distribués, ou sur les écarts entre les nombres premiers", a déclaré Ofer Grossman, qui étudie les algorithmes pseudo-aléatoires. Et si nous ne savons pas où les trouver, il n'y a pas de moyen facile de générer un nombre premier à partir de zéro.

Au fil du temps, les chercheurs ont développé les approches susmentionnées. Le moyen le plus simple est de deviner. Si vous voulez un nombre premier à 1,000 1,000 chiffres, par exemple, vous pouvez choisir un nombre à XNUMX XNUMX chiffres au hasard, puis le vérifier. "Si ce n'est pas le premier, vous en essayez juste un autre, et un autre, et ainsi de suite jusqu'à ce que vous en trouviez un", a déclaré Rahul Santhanam, informaticien à l'Université d'Oxford et co-auteur du nouvel article. "Parce qu'il existe de nombreux nombres premiers, cet algorithme vous donnera un nombre qui est premier avec une probabilité élevée, après un nombre relativement faible d'itérations." Mais utiliser le hasard signifie que vous obtiendrez probablement un nombre différent à chaque fois, a-t-il déclaré. Cela pourrait être un problème si vous avez besoin de cohérence - si, par exemple, vous utilisez une méthode de sécurité cryptographique qui dépend de la disponibilité de grands nombres premiers.

L'autre approche consiste à utiliser un algorithme déterministe. Vous pouvez choisir un point de départ et commencer à tester les nombres, de manière séquentielle, pour la primalité. Finalement, vous êtes destiné à en trouver un, et votre algorithme produira systématiquement le premier que vous trouverez. Mais cela peut prendre un certain temps : si vous cherchez un nombre premier avec 1,000 2 chiffres, même un calcul avec XNUMX⁵⁰⁰ étapes — qui prendraient beaucoup plus de temps que l'âge de l'univers — ne suffisent pas à garantir le succès.

En 2009, le mathématicien et médaillé Fields Terence Tao voulait faire mieux. Il a mis les mathématiciens au défi de proposer un algorithme déterministe pour trouver un nombre premier d'une taille donnée dans un temps de calcul limité.

Cette limite de temps est connue sous le nom de temps polynomial. Un algorithme résout un problème en temps polynomial si le nombre d'étapes qu'il prend n'est pas supérieur à une fonction polynomiale de n, la taille de l'entrée. (Une fonction polynomiale comprend des termes dont les variables sont élevées à des puissances entières positives, comme n² ou 4n³.) Dans le contexte de la construction des nombres premiers, n fait référence au nombre de chiffres dans le nombre premier que vous voulez. En termes de calcul, cela ne coûte pas cher : les informaticiens décrivent les problèmes qui peuvent être résolus par des algorithmes en temps polynomial comme étant faciles. Un problème difficile, en revanche, prend un temps exponentiel, ce qui signifie qu'il nécessite un certain nombre d'étapes approximées par une fonction exponentielle (qui comprend des termes tels que 2ⁿ).

Pendant des décennies, les chercheurs ont étudié le lien entre le hasard et la dureté. Le problème de la construction des nombres premiers était considéré comme facile si vous autorisiez le hasard - et que vous vous contentiez de recevoir un nombre différent à chaque fois - et difficile si vous insistiez sur le déterminisme.

Personne n'a encore réussi à relever le défi de Tao, mais le nouveau travail s'en rapproche. Il s'inspire fortement d'une approche introduite en 2011 par Shafi Goldwasser et Eran Gat, informaticiens au Massachusetts Institute of Technology. Ils ont décrit des algorithmes "pseudodéterministes" - des recettes mathématiques pour les problèmes de recherche, comme la recherche de grands nombres premiers, qui pourraient exploiter les avantages du hasard et, avec une probabilité élevée, toujours produire la même réponse à chaque fois. Ils utiliseraient l'efficacité des bits aléatoires dans la recette, qui seraient dé-randomisés dans le résultat, apparaissant déterministes.

Depuis, les chercheurs explorent des algorithmes pseudo-déterministes. En 2017, Santhanam et Igor Oliveira de l'Université de Warwick (qui ont également contribué au nouveau travail) décrit une approche pseudo-déterministe de la construction de nombres premiers qui utilisait le caractère aléatoire et semblait déterministe de manière convaincante, mais cela fonctionnait en temps «sous-exponentiel» - plus rapide que le temps exponentiel, mais plus lent que le temps polynomial. Puis en 2021, Tell et Lijie Chen, informaticien à l'Université de Californie à Berkeley, exploré comment utiliser un problème difficile pour construire un générateur de nombres pseudo-aléatoires (un algorithme qui génère une chaîne de nombres indiscernables d'une sortie aléatoire). "[Nous] avons trouvé un nouveau lien entre la dureté et le pseudo-aléatoire", a déclaré Chen.

Les pièces se sont finalement réunies au printemps 2023, lors de un bootcamp sur la complexité computationnelle au Simons Institute for the Theory of Computing à Berkeley, lorsque les chercheurs ont commencé à travailler ensemble sur le problème, tissant ensemble les résultats antérieurs. Pour le nouveau travail, a déclaré Chen, Hanlin Ren – un informaticien à Oxford et co-auteur – a eu les idées initiales pour combiner le résultat de Chen-Tell avec l'approche de Santhanam-Oliveira d'une manière nouvelle. Ensuite, toute l'équipe a développé les idées plus complètement pour produire le nouveau papier.

L'algorithme pseudo-déterministe résultant, a déclaré Santhanam, a utilisé de nouvelles façons de regarder le travail passé pour produire des nombres premiers en temps polynomial. Il a prouvé qu'il a utilisé le caractère aléatoire pour produire un nombre premier d'une longueur spécifique, et l'outil est plus précis que la supposition aléatoire et plus efficace en termes de calcul que le calcul déterministe.

Le nouvel algorithme est également remarquablement simple, a déclaré Santhanam, et il peut être appliqué à un large éventail de problèmes de recherche – en réalité, à tout sous-ensemble dense de nombres, comme les nombres premiers, pour lesquels l'appartenance peut être déterminée en temps polynomial. Mais ce n'est pas parfait. L'algorithme fonctionne pour une infinité de longueurs d'entrée, mais il ne couvre pas toutes les longueurs de chiffres. Il peut encore y avoir des valeurs de n là-bas pour lequel l'algorithme ne produit pas de manière déterministe un nombre premier.

"Ce serait cool de se débarrasser de cette petite mise en garde", a déclaré Grossman.

Le but ultime, a déclaré Santhanam, est de trouver un algorithme qui ne nécessite pas du tout d'aléatoire. Mais cette quête reste ouverte. "Le déterminisme est ce que nous aimerions utiliser", a-t-il déclaré.

Mais il a également souligné que les processus pseudo-aléatoires sont des outils puissants et que des projets tels que la construction de nombres premiers ne sont qu'un moyen de les utiliser pour relier des idées issues des mathématiques, de l'informatique, de la théorie de l'information et d'autres domaines.

"C'est excitant d'essayer de penser à quoi d'autre ces brillantes observations mèneront", a déclaré Tell.