Nombres premiers

Les blocs par lesquels sont construits les autres nombres (du moins, les entiers). Ils sont importants dans une multitude de sphères de l'informatique et des mathématiques (en particulier tout ce qui touche au chiffrement de données).

La quête de nouveaux nombres premiers occupe plusieurs projets scientifiques; de même, un grand nombre de problèmes fondamentaux qui occupent les chercheurs en mathématiques et en informatique portent sur les nombres premiers ou leur distribution.

Quelques liens vers des articles sur le sujet, avec penchant pour la programmation :

• Une démonstration du fait qu'il existe une infinité de premiers, relatée par Jeremy Kun mais originalement suggérée par Paul Erdős : http://jeremykun.wordpress.com/2012/11/10/there-are-infinitely-many-primes-erdos/
• Un peu de pédagogie sur les nombres premiers : ce qu'ils sont, pourquoi ils sont si importants, quelques conjectures, etc.
  • http://fr.wikipedia.org/wiki/Nombre_premier
  • une page tenant à jour une liste de records sur les nombres premiers : http://primes.utm.edu/
  • l'American Institute of Mathematics signale publiquement l'atteinte de résultats significatifs dans ce domaine : http://aimath.org/primegaps/
  • pour celles et ceux qui se demandent pour quelle raison $1$ n'est pas premier...
  • http://mathworld.wolfram.com/topics/PrimeNumbers.html
  • http://fr.wikipedia.org/wiki/Premiers_entre_eux
  • http://mathworld.wolfram.com/TwinPrimes.html
  • hypothèse de Riemann
  • conjecture de Goldbach
  • http://mathworld.wolfram.com/TwinPrimeConjecture.html
  • la spirale d'Ulam, une manière de visualier les nombres premiers :
  • http://en.wikipedia.org/wiki/Ulam_spiral
  • article de 2010 par Mark C. Chu-Carroll sur le sujet : http://scienceblogs.com/goodmath/2010/06/the_surprises_never_eend_the_u.php?...
  • connexions entre nombres premiers et physique quantique, article de 2012 par Marcus du Sautoy : http://www.seedmagazine.com/.../prime_numbers_get_hitched...
  • à propos de la distribution de la première décimale des nombres premiers, qui suivrait une loi particulière, un article de Christian S. Perone en 2009 : http://pyevolve.sourceforge.net/wordpress/?p=527
  • bizarrerie légale : il existe des nombres premiers « illégaux », qu'on ne peut diffuser aux États-Unis d'Amérique sous peine de poursuites légales (en lien avec la complètement ridicule loi entourant la protection des médias numériques) : http://en.wikipedia.org/wiki/Illegal_prime
  • texte de 2003 par Philippe Ball qui suggère que la distribution des nombres premiers ne soit pas aléatoire : http://www.nature.com/news/1998/030317/full/news030317-13.html
• À propos de la distribution des nombres premiers :
  • à propos de la conjecture ABC, qui accompagne en quelque sorte les travaux de recherche sur la distribution des premiers :
    • un Wiki sur le sujet : http://en.wikipedia.org/wiki/Abc_conjecture
    • en 2012, Shinichi Mochizuki aurait proposé une preuve de cette conjecture (http://www.kurims.kyoto-u.ac.jp/~motizuki/Inter-universal Teichmuller Theory I.pdf) ... Reste à voir si cette proposition de preuve survivra à l'examen par les pairs : http://www.nature.com/news/proof-claimed-for-deep-connection-between-primes-1.11378 (c'est le premier de quatre textes)
    • une réflexion de Richard Lipton sur le sujet : http://rjlipton.wordpress.com/2012/09/12/the-abc-conjecture-and-cryptography/
  • démonstration de Yitang Zhang en 2013 à l'effet que l'écart entre deux premiers consécutifs est toujours inférieur à $7 \times 10^7$ : http://annals.math.princeton.edu/articles/7954
  • semblerait que les nombres premiers ne soient pas équitables en ce qui a trait à leur dernière unité, du moins lorsqu'ils sont exprimés sous forme décimale, comme le rapporte Erica Klarreich en 2016 : https://www.quantamagazine.org/20160313-mathematicians-discover-prime-conspiracy/
    • sur le même sujet, voir ce texte de Ken Regan en 2016 : https://rjlipton.wordpress.com/2016/03/26/bias-in-the-primes/
• Trouver des nombres premiers, différents algorithmes :
  • http://www.troubleshooters.com/.../primenumbers/primenumbers.htm
  • http://davidkendal.net/articles/2011/12/lehmann-primality-test
  • http://jeremykun.com/2013/06/16/miller-rabin-primality-test/
  • http://mathworld.wolfram.com/AKSPrimalityTest.html
  • produire des nombres premiers avec... LaTeX! http://tex.stackexchange.com/questions/134305/how-to-produce-a-list-of-prime-numbers-in-latex
  • une expression régulière pour reconnaître des nombres premiers, proposée par Avinash Meetoo en 2007 : http://www.noulakaz.net/weblog/2007/03/18/a-regular-expression-to-check-for-prime-numbers/
  • texte de Brian Raiter expliquant comment fonctionne le RSA Cipher, dont la force repose sur des nombres relativement premiers entre eux : http://www.muppetlabs.com/~breadbox/txt/rsa.html
• Découvrir des nombres premiers de plus en plus gros est une épopée mathématique en soi :
  • The Great Mersenne Prime Search
  • une chronologie de leur découverte, colligée par Chris Caldwell : http://primes.utm.edu/notes/by_year.html
  • http://actualites.epfl.ch/presseinfo-com?id=441
  • petit défi : construire un carré magique fait de nombres premiers consécutifs. Texte de John D. Cook  en 2013 : http://www.johndcook.com/blog/2013/09/02/a-magic-square-filled-with-consecutive-primes/
• Un très joli site sur la distribution des nombres premiers, par Jason Davies : http://www.jasondavies.com/primos/
• Factoriser des entiers pour retrouver leurs facteurs premiers, une tâche difficile mais importante (en particulier pour tout ce qui a trait au chiffrement et au déchiffrement de données) :
  • http://en.wikipedia.org/wiki/Integer_factorization
  • visualiser la factorisation des entiers, une animation fort réussie : http://www.datapointed.net/visualizations/math/factorization/animated-diagrams/#
  • la factorisation en nombres premiers n'est pas nécessairement unique en général, comme le rappelle Richard J. Lipton en 2016 sur la base des travaux d'Ernst Kummer : https://rjlipton.wordpress.com/2016/01/30/failure-of-unique-factorization/
• Le jeu Fractran, proposé par John Conway et relaté par Mark C. Chu-Carroll en 2009, qui demande d'avoir recours aux facteurs premiers de nombres : http://scienceblogs.com/goodmath/2009/09/03/pathological-programming-with/
• Générer des nombres premiers à l'aide du « Jeu de la vie », par Nathaniel Johnston en 2009 : http://www.nathanieljohnston.com/2009/08/generating-sequences-of-primes-in-conways-game-of-life/
• Fait amusant : $2^{31}-1$ est premier : http://en.wikipedia.org/wiki/2147483647
• Texte anecdotique mais amusant de John D. Cook en 2013, qui laisse entendre que, parfois, avoir un outil spécialisé, ça rapporte: http://www.johndcook.com/blog/2013/01/17/narcissus-prime-in-python/
• Texte de John D. Cook en 2013 sur les Suffix Primes : http://www.johndcook.com/blog/2013/03/12/a-suffix-prime/
  • en 2013, John D. Cook explique comment il est possible de visualiser les Suffix Primes : http://www.johndcook.com/blog/2013/10/03/visualizing-suffix-primes/
• En 2013, John D. Cook décrit les jours premiers internationaux : http://www.johndcook.com/blog/2013/11/29/todays-a-prime-day/
• Texte de John D. Cook en 2013 expliquant comment générer des premiers à partir de fractions : http://www.johndcook.com/blog/2013/10/12/prime-generating-fractions/
• Les nombres de Carmichael, qui ont une forte relation avec les nombres premiers et la factorisation des entiers, expliqués par Richard Lipton et Ken Regan en 2013 : http://rjlipton.wordpress.com/2013/07/18/ghostbusting-old-factoring-ideas/
• Calculer des nombres premiers... avec CSS, texte de Ned Batchelder en 2016 : http://nedbatchelder.com//blog/201609/computing_primes_with_css.html