« Fumée | Le style Libé. envahit Le Monde »
2007-12-03 17:21+0100 (Orsay) — Mathématiques
En préparant un cours, je lis dans un livre l'énoncé suivant 1 de Research problem :
Find out whether prime numbers can be recognized in deterministic polynomial time. (According to Miller's result, it is sufficient to prove the ERH
;-).)
Ce problème ayant été résolu assez récemment, je me demande d'un air distrait pourquoi les trois indiens qui ont proposé un algorithme déterministe répondant à la question de savoir si un nombre entier est premier en un temps polynomial en le nombre de chiffres n'ont pas reçu conjointement un million de dollars pour avoir résolu au passage l'hypothèse de Riemann, un des problèmes du millénaire (selon l'institut Clay).
L'explication est évidemment qu'il suffit de démontrer l'hypothèse de Riemann généralisée pour obtenir un test de primalité déterministe en temps polynomial, et non le contraire, ce que je savais avant de feuilleter ce livre, mais la formulation ambiguë (parce que elliptique et lue par moi sans le contexte) m'a fait bugger quelques secondes.
[1] Modern computer algebra de Joachim von zur Gathen et Jürgen Gerhard, Deuxième édition, page 528.
Damaide ! Autant Riemann me dit encore quelque chose autant je suis désormais bien incapable (l'ai-je vraiment un jour été ?) de comprendre "un test de primalité déterministe en temps polynomial" au delà de sa beauté poétique.
N'empêche, c'est beau.
D'ailleurs le jour où ERH sera démontrée, le résultat de Manindra Agrawal, Neeraj Kayal et Nitin Saxena n'aura plus grand intérêt, celui de Miller étant plus léger (et antérieur).
gilda : cela signifie qu'il existe un programme informatique qui détermine si un nombre n est un nombre premier, et dont on puisse démontrer qu'il rend son résultat relativement vite (majoré par un polynôme en le nombre de chiffres de n).
C'est beaucoup plus simple à énoncer que l'hypothèse de Riemann qui exige un peu technique : il faut avoir fait un peu d'analyse complexe.
Koko : peut-être que oui, mais l'hypothèse de Riemann n'a pas encore été démontrée...
Vous pouvez poster un commentaire grâce au formulaire ci-dessous.
Date de génération : 2023-07-27 14:18+0530 ― Mentions légales.