Ce nombre est-il premier ? Il y a un jeu pour ça.

Le mathématicien grec Euclide a peut-être très bien prouvé, vers 300 avant notre ère, qu’il existe une infinité de nombres premiers. Mais c’est le mathématicien britannique Christian Lawson-Perfect qui, plus récemment, a conçu le jeu informatique « Is this prime ?

Lancé il y a cinq ans, le jeu a dépassé les trois millions d’essais le 16 juillet – ou, plus précisément, il a atteint 2 999 999 – après qu’un article de Hacker News a généré une vague d’environ 100 000 tentatives.

Le but du jeu est de trier autant de nombres que possible en « premiers » ou « non premiers » en 60 secondes (comme Lawson-Perfect l’a initialement décrit sur The Aperiodical, un blog de mathématiques dont il est le fondateur et éditeur).

Un nombre premier est un nombre entier avec précisément deux diviseurs, 1 et lui-même.

« C’est très simple, mais extrêmement difficile », déclare Lawson-Perfect, qui travaille dans l’unité d’apprentissage en ligne de la School of Mathematics and Statistics de l’Université de Newcastle. Il a créé le jeu pendant son temps libre, mais il s’est avéré utile sur le tas : Lawson-Perfect écrit des logiciels d’évaluation électronique (systèmes qui évaluent l’apprentissage). « Le système que je crée est conçu pour générer au hasard une question de mathématiques et prendre une réponse de l’élève, qu’il note automatiquement et sur laquelle il donne des commentaires », dit-il. « Vous pourriez considérer le jeu des primes comme une sorte d’évaluation » – il l’a utilisé lors de séances de sensibilisation dans les écoles.

Il a rendu le jeu légèrement plus facile avec des raccourcis clavier – les touches y et n cliquent sur les boutons oui-non correspondants à l’écran – afin de gagner du temps de déplacement de la souris.

Essayer:

Algorithmes de contrôle de primalité

Les nombres premiers ont une utilité pratique en informatique, comme avec les codes de correction d’erreurs et le cryptage. Mais alors que la factorisation en nombres premiers est difficile (d’où sa valeur dans le cryptage), la vérification de la primalité est plus facile, si délicate. Le mathématicien allemand Alexander Grothendieck, lauréat de la médaille Fields, a tristement confondu 57 avec le premier (le « premier de Grothendieck »). Lorsque Lawson-Perfect a analysé les données du jeu, il a découvert que divers nombres présentaient une certaine «grothendieckyness». Le nombre le plus souvent confondu avec un nombre premier était 51, suivi de 57, 87, 91, 119 et 133 – l’ennemi juré de Lawson-Perfect (il a également conçu un service pratique de vérification de la primalité : https://istthisprime.com/2).

L’algorithme le plus minimaliste pour vérifier la primauté d’un nombre est la division d’essai – divisez le nombre par chaque nombre jusqu’à sa racine carrée (le produit de deux nombres supérieurs à la racine carrée serait supérieur au nombre en question).

Cependant, cette méthode naïve n’est pas très efficace, de même que d’autres techniques conçues au cours des siècles – comme le mathématicien allemand Carl Friedrich Gauss l’a observé en 1801, elles « exigent un travail intolérable même pour le calculateur le plus infatigable ».

L’algorithme Lawson-Perfect codé pour le jeu s’appelle le test de primalité de Miller-Rabin (qui s’appuie sur une méthode du 17ème siècle très efficace mais pas à toute épreuve, « le petit théorème de Fermat »). Le test de Miller-Rabin fonctionne étonnamment bien. En ce qui concerne Lawson-Perfect, c’est « fondamentalement magique » – « Je ne comprends pas vraiment comment cela fonctionne, mais je suis convaincu que je le pourrais si je passais le temps à l’examiner plus en profondeur », dit-il.

Étant donné que le test utilise le caractère aléatoire, il produit un résultat probabiliste. Ce qui signifie que parfois le test est faux. « Il y a une chance de découvrir un imposteur, un nombre composé qui essaie de passer pour premier », déclare Carl Pomerance, mathématicien au Dartmouth College et coauteur du livre. Nombres premiers : une perspective informatique. Les chances qu’un imposteur glisse à travers le mécanisme de vérification intelligent de l’algorithme sont peut-être d’un sur un billion, donc le test est « assez sûr ».

Mais en ce qui concerne les algorithmes intelligents de vérification de la primalité, le test de Miller-Rabin est «la pointe de l’iceberg», explique Pomerance. Notamment, il y a 19 ans, trois informaticiens – Manindra Agrawal, Neeraj Kayal et Nitin Saxena, tous de l’Indian Institute of Technology Kanpur – ont annoncé le test de primalité AKS (encore une fois basé sur la méthode de Fermat), qui a finalement fourni un test pour prouver sans équivoque qu’un nombre est premier, sans randomisation et (en théorie du moins) avec une vitesse impressionnante. Hélas, rapide en théorie ne se traduit pas toujours par rapide dans la vie réelle, le test AKS n’est donc pas utile à des fins pratiques.

Le record du monde officieux

Mais l’aspect pratique n’est pas toujours le but. Occasionnellement, Lawson-Perfect reçoit des e-mails de personnes désireuses de partager leurs meilleurs scores dans le jeu. Récemment, un joueur a signalé 60 nombres premiers en 60 secondes, mais le record est plus probable de 127. (Lawson-Perfect ne suit pas les scores élevés ; il sait qu’il y a des tricheurs, avec des tentatives assistées par ordinateur qui produisent des pics dans les données.)

Le score de 127 a été obtenu par Ravi Fernando, un étudiant diplômé en mathématiques de l’Université de Californie à Berkeley, qui a publié le résultat en juillet 2020. C’est toujours son record personnel et, selon lui, le « record du monde non officiel ».

Depuis l’été dernier, Fernando n’a pas beaucoup joué au jeu avec les paramètres par défaut, mais il a essayé avec des paramètres personnalisés, en sélectionnant des nombres plus importants et en permettant des délais plus longs – il a marqué 240 avec une limite de cinq minutes. « Ce qui a demandé beaucoup de conjectures, car les nombres sont entrés dans la fourchette haute à quatre chiffres et je n’ai mémorisé que des nombres premiers jusqu’à 3 000 », dit-il. « Je suppose que certains diraient même que c’est excessif. »

Les recherches de Fernando portent sur la géométrie algébrique, qui implique dans une certaine mesure les nombres premiers. Mais, dit-il, « mes recherches ont plus à voir avec pourquoi j’ai arrêté de jouer au jeu que pourquoi j’ai commencé » (il a commencé son doctorat en 2014). De plus, il pense que 127 serait très difficile à battre. Et, dit-il, « il semble juste de s’arrêter à un record de nombre premier. »