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 sur ordinateur »Est-ce premier ?« 

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 un Message d’information sur les pirates informatiques 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’origine décrit il sur L’Apériodiquel, un blog de mathématiques dont il est 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 obtenir 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 première 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 lauréat de la médaille Fields Alexandre Grothendieck notoirement confondu 57 pour le premier (le « premier de Grothendieck »). Quand Lawson-Parfait analysé les données du jeu, il a constaté 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 de 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 », explique 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 en s’appuyant sur la méthode de Fermat), qui a finalement fourni un test pour prouver sans équivoque qu’un nombre est premier, sans randomisation et (théoriquement, au 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 à l’Université de Californie à Berkeley, qui 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 portent plus sur la raison pour laquelle j’ai arrêté de jouer au jeu que sur la raison pour laquelle 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. »