Comment trouver des nombres premiers 30


« the centrality of prime numbers » par barabeke sur Flickr

Les nombres premiers ont beau être étudiés depuis au moins 2300 ans, ils n’ont jamais été aussi mystérieux ni utiles qu’aujourd’hui.

Mystérieux, car la démonstration de l'hypothèse de Riemann, qui permettrait de définir la répartition des nombres premiers, attend toujours son  futur millionnaire.

Utiles, car nos cartes à puces, téléphones et ordinateurs consomment des quantités industrielles de « grands » nombres premiers, en particulier pour le cryptage RSA. La sécurité de cette méthode « asymétrique » repose sur le fait que la factorisation entière en nombres premiers de grands nombres demande un temps prohibitivement long, alors qu’il est très rapide de trouver de grands nombres premiers.

Comment trouver de petits nombres premiers

Ceci parait surprenant de prime abord, puisqu’on apprend à l’école à déterminer si n est premier en tentant de le diviser par les nombres premiers déjà connus inférieurs à √n, ce qui n’est autre qu’une factorisation. On découvre à l’école aussi le crible d’Eratosthène, qui fournit depuis 2000 ans les nombres premiers les uns après les autres à tous les heureux possesseurs de feuilles quadrillées ou de mémoires informatiques:

Animation du Crible d’Erathosthène (Wikipédia)

 

Cette méthode n’a été légèrement améliorée qu’en 1999 avec le crible d’Atkin et reste excellente pour créer des listes de nombres premiers consécutifs. Ainsi le site www.bigprimes.net les fournit tous jusqu’à  32 416 187 567 *

Mais alors, comment le célèbre Pierre de Fermat a-t-il pu répondre en 1643 à un certain Marin Mersenne (dont nous reparlerons plus bas):

Vous me demandez si le nombre 100 895 598 169 est premier ou non, et une méthode pour découvrir, dans l’espace d’un jour, s’il est premier ou composé. À cette question, je réponds que ce nombre est composé et se fait du produit de ces deux : 898423 et 112303, qui sont premiers.

Et bien parce que 3 ans plus tôt il avait pondu et démontré lui-même son « petit » théorème, qui constitue en même temps le premier test de primalité probabiliste. Grâce à cela,  il a su « rapidement » que 100895598169 n’est pas premier. Par contre, comment il a effectué les opérations et factorisé le nombre avec un papier et un crayon en un seul jour, ça je n’en ai avais aucune idée **

Et je ne sais pas non plus comment Mersenne a généré 898423 et 112303 parce que bizarrement, ce ne sont pas des nombres de Mersenne, dont nous parlerons plus bas… En fait, ô surprise, 898423 = 112303 x 23-1, donc Mersenne a généré le grand premier à partir du petit, lequel a d’ailleurs la même forme : 112303 = 7019 x 24-1.

Comment trouver de très grands nombres premiers

Il existe donc des méthodes pour générer des nombres premiers. Aucune ne produit des nombres premiers « à tous les coups » ( ce serait le Graal que certains recherchent encore mais qui n’existe probablement pas ), mais ces méthodes fournissent des grands nombres qui ont une probabilité d’être premiers nettement plus élevée que des nombres de même taille choisis au hasard.

Au IXème siècle déjà, Thābit ibn Qurra avait remarqué que pas mal de petits nombres premiers ont la forme « 321 » p = 3×2n-1 . Les nombres de Thebit sont listés dans A002235. Le plus grand connu actuellement est 3×24235414−1 mais aussi 3×27033641+1 qui n’est pas strictement un Thabit à cause du +1 au lieu du -1 final.

Les  nombres de Mersenne ont une forme encore plus simple : p = 2n-1 où n est premier. Et Mersenne ne les a pas découverts : Euclide connaissait déjà les plus petits ( 3, 7, 31 et 127 ) en 300 avant J.C. Mersenne en a juste fait une liste en ajoutant 8191 découvert par Ibn Fallus au XIIIème siècle et 131071 et 524287 découverts par Pietro Cataldi en 1588. Et puis il s’est planté magistralement : sa liste incluait les nombres  267-1 et 2257-1 qui ne sont pas premiers et omettait 231-1, 261-1, 289-1 et 2107-1 qui le sont. C’est dommage, car Mersenne n’a ainsi jamais détenu le record du plus grand nombre premier qui a presque toujours été un nombre de Mersenne. Depuis 2009, le record est 243112609-1 , qui compte 12 837 064 chiffres, trouvé grâce au programme GIMPS. Le rôle de ce logiciel est surtout de faire passer le génial test de primalité de Lucas-Lehmer qui est déterministe (non probabiliste) mais ne marche qu’avec les Mersenne.

Bref, aucun nombre de Mersenne n’est de Mersenne et si je n’avais pas autant de lecteurs en République Française, je proposerais de les rebaptiser « repunits premiers » pour souligner leur beauté en binaire. En effet, 2n-1 s’écrit simplement avec une suite de n « 1 » en binaire. Par exemple 127= 27-1 s’écrit 1111111 en binaire.

Il existe plusieurs autres formules fournissant des candidats premiers :

  • Les nombres de Fermat de la forme 22n + 1. Fermat pensait qu’ils étaient tous premiers, mais c’est faux : seuls les 5 premiers le sont, les 28 suivants ne le sont pas, et les autres sont trop grands pour être testés.
  • Les premiers de Proth sont de la forme k·2n+1 ( A080075 , record 659×2617815+1 )
  • Ceux de Woodall : n·2n--1 ( A003261, 3752948 × 23752948 − 1)
  • Ceux de Cullen : n·2n+1 ( A005849, 6679881 · 26679881 + 1)
  • les « Cullen généralisés » : n·bn+1,où n+2 > b ( record 427194 × 113427194 + 1)

on voit qu’elles sont toutes des généralisations ou cas particuliers des autres, et que les repunits y jouent un  rôle important. Les nombres premiers de Sophie Germain (PSG) sont des nombres p tels que 2p+1 est aussi premier (A005384). Ce « générateur » fournit des nombres moins grands que les autres, mais soulève plein de questions intéressantes : quelle est la longueur maximale d’une chaîne de Cunningham formée par des PSG, y’a-t-il une infinité de PSG etc. Et de plus, le théorème de Sophie Germain établit un lien entre le « petit  » théorème de Fermat susmentionné et le grand qui a obsédé les matheux jusqu’en 1994. Et comme je n’ai pas compris grand chose à sa démonstration, je suis plein d’admiration pour cette dame autodidacte qui étonna les mâlethématiciens d’il y a 200 ans.

Si vous voulez vous aussi devenir célèbre, mais facilement, participez à PrimeGrid, une application de la plateforme de calcul distribuée BOINC qui chasse les records de grands nombres premiers. Avec un peu de chance le prochain grand nombre premier sera découvert sur votre ordinateur tout en vous chauffant pous la science.

Comment trouver des nombres premiers d’une longueur donnée

Fin 2009, une équipe internationale a cracké un code RSA-768, en factorisant le produit de deux nombres premiers de 120 chiffres à l’aide de l'algorithme de factorisation par crible sur les corps de nombres et de beaucoup d’ordinateurs. Cet exploit signifie qu’une clé RSA nécessite aujourd’hui des nombres premiers d’au moins 512 bits, soit 154 chiffres décimaux pour être indécryptable.

Nous avons vu plus haut comment obtenir tous les nombres premiers nettement plus courts, ou quelques nombres premiers nettement plus longs, mais pour RSA, nous avons besoin d’obtenir en quelques secondes des nombres premiers de 154 chiffres, avec un seul petit processeur enfermé dans le boitier d’un routeur par exemple, et sans que le nombre transite par un réseau où il pourrait être intercepté. De plus, le nombre ne doit pas être stocké dans une table dont un pirate pourrait essayer les combinaisons : il doit être généré aléatoirement.

Mais au fait, existe-t-il beaucoup de nombres premiers de 154 chiffres ? Oh que oui : la densité des nombres premiers autour de n est de 1/ln(n), or 1/ln(10154) donne environ 0.3% : environ 3 nombres de 154 chiffres sur 1000 sont premiers, donc il y en a des giga milliards de floppées. Donc tout ce que notre petit routeur a à faire de temps en temps c’est:

  1. générer un nombre aléatoire de 154 chiffres en tirant au hasard 511 bits à pile ou face, et en ajoutant un 512ème bit = 1 pour faire un nombre impair. facile et ultra rapide.
  2. vérifier si le nombre est premier à l’aide d’un  test de primalité probabiliste plus  moderne que celui de Fermat comme celui de Miller-Rabin.
  3. si le test dit que le nombre n’est pas premier, ajouter 2 au nombre aléatoire pour obtenir le nombre impair suivant et recommencer l’opération 2. Il faudra  répéter ceci en moyenne 300 fois avant que Miller et Rabin disent « probablement premier »

Pour vous faire une idée de la vitesse de ceci, allez au milieu de cette page et cliquez le bouton « auto generate prime number p and q » : vous obtiendrez 2 nombres premier de 512 bits pour le prix d’un seul click.

cliquez sur l’image et scrollez vers le milieu de la page

Oui mais, me direz vous, les tests probabilistes ne garantissent pas absolument que les nombres soient premiers. Il y a un risque qu’on encode le message avec une clé foireuse, et donc qu’il soit « facile » à décoder.
Effectivement, mais on admet généralement que la probabilité qu’un nombre de cette taille soit pseudopremier est de l’ordre d’une sur 1030. Et si votre message est si précieux que vous n’êtes pas prêt à courir ce risque, réfléchissez à ceci : le risque qu’un rayon cosmique change un bit du nombre pendant un test de primalité déterministe est un million de fois plus élevé ! J’aime bien cette idée qu’un algorithme probabiliste soit plus fiable qu’une machine considérée comme déterministe, pas vous ?

Notes :

* 32’416’187’567 est tellement proche de 8*2^32 que j’ai une petite idée de la mémoire utilisée par le crible…

** ajout du 18 mai 2014 : Blogdemaths a éclairé ma lanterne à ce sujet dans cet article : http://blogdemaths.wordpress.com/2014/05/18/savez-vous-factoriser-a-la-mode-de-fermat/

Pour en savoir plus

  1. L’algorithme RSA sur le Site du Zéro
  2. Jean-Paul Delahaye "Merveilleux nombres premiers" (2000) Pour la Science ISBN:9782842450175 WorldCat Goodreads Google Books  
  3. nzmath.prime : une librairie Python avec les fonctions qu’il faut

Laissez un commentaire

30 Commentaires on "Comment trouver des nombres premiers"


Invité
paul lamour
12 jours 4 heures plus tôt

J’ai mis au point un logiciel de calcul des nombres premiers Gypse.
Dans les petits nombres il peux calculer 120 np par seconde, soit environ 8 000 np par minutes. Pour les np de 7 chiffres 20 np par seconde. Il fonctionne sans interruption, je l’ai testé sur 5 minutes pour l’instant.

Invité
Blogdemaths
1 an 7 jours plus tôt

Bonjour Dr. Goulu,

Vous demandiez comment Fermat a factorisé le nombre 100 895 598 169. J’ai justement écrit un article à ce propos et l’explication se trouve ici:

http://blogdemaths.files.wordpress.com/2014/05/factorisation_de_100895598169_par_fermat.pdf

Si vous voulez lire l’article complet (dans lequel j’explique la méthode de factorisation de Fermat, méthode qu’il n’a probablement pas utilisée pour factoriser 100 895 598 169), c’est ici:

http://blogdemaths.wordpress.com/2014/05/18/savez-vous-factoriser-a-la-mode-de-fermat/

Enfin, il semble que le petit théorème de Fermat n’a pas été utilisé pour montrer que 100895598169 est composé, car le nombre de calculs est assez long… et même en admettant que Fermat connaissait la méthode d’exponentiation rapide (modulaire), voici les calculs qu’il aurait dû faire pour montrer que 2^{100895598169} = 21283103109 ≠ 1 mod[100895598169]:

Bon, on peut toujours penser que c’est possible à la main, mais en un jour ça paraît short ! :)

Invité
1 an 7 jours plus tôt

Merci beaucoup et bravo pour vos article + pdf + code Python ( http://pastebin.com/CKDq8Ts4 ) expliquant très clairement ces algorithmes.

Je suis toujours épaté par l’ingéniosité des cerveaux humains lorsqu’ils ne pouvaient utiliser que du papier et un crayon en lieu et place d’ordinateur…

Invité
HEREDIA Serge
1 an 10 mois plus tôt

Bonjour Dr,
Vous Pithonez pus vite que votre ombre, merci pour cette rapidité. Je me réexplique
Question 1
La question n’est pas « y a t il une infinité de jumeaux » (bravo aux conjectureurs et démontreurs) mais  » chaque fois que l’on rencontre un premier il est la somme d’un premier précédent et d’un nombre qui est lui même le produit d’un certain nombre de fois 2 ; pourquoi alors ne s’intéresser qu’aux jumeaux »
Question 2 (la plus intéressante pour ma quête) « les jumeaux ? il y en a plein (variante locale du beaucoup zinzinien)- une infinité – mais jamais entre ce bon quart de premiers finissant par 3 et ce bon quart de premiers finissants par 7 ; Ils sont tous entre des premiers finissant par : gémellité 1 et 3 gémellité 7 et 9 gémellité 9 et 1
A vous.

Invité
HEREDIA Serge
1 an 10 mois plus tôt

Bonjour Dr,
J’ai un petit problème de formulation, dans la littérature je rencontre beaucoup d’articles sur les « couples » de nombres premiers, notamment les p +2 ; eux même premiers.
Mais tous les premiers (sans exception) sont de la forme p’ = p +2.n , pourquoi l’insistance dans les revues sur le 2.1 qui n’est d’ailleurs pas parfait (grande affection entre eux des finissant par 1 et 3 car 1+2=3; entre finissant par 7 et 9 entre 9 et le 1 MAIS, une tendance lourde, confinant à l’exclusivité : xénophobie entre finissant par 3 et 7 )
Est ce que ma formulation p’ premier suivant = p premier connu + 2.n est correcte ? est elle écrite autrement pour … un matheux?
Vous avez compris que j’explore toujours la particularité des premiers à se regrouper exhaustivement en 4 familles chacune caractérisée par, selon votre formulation (03-07-2013), « la dernière décimale ».
Bonne journée à vous et le bonjour aux infirmières.

Invité
HEREDIA Serge
1 an 10 mois plus tôt

Bonjour Dr,
Intéressant, il ne faut pas désespérer, enfin une régularité, imparfaite il est vrai, les séries doivent « tendre vers » 25 % pour chacun de la bande des 4. Mais pas sûr, « l’excédent » – très relatif il est vrai – de 7 apparaît très vite dans les factorisations* et aussi longtemps que durent les calculs, pleins de premiers finissant par 7 (4 ou 5, parfois plus) peuplent – et exclusivement eux – le peloton de tête des plus grands premiers obtenus, flippant ! Comme si le 2 et le 5 trop tôt ravis à notre affection « perturbaient » les suites.
* factorisations des nombres issus des progressions r=100 vues plus haut.
Enchanté ravi de votre patience et de votre sens pédagogique, je ne ferai retour vers vous que dans quelques jours ou semaines (ici la mer est chaude) car les liens que vous m’avez suggéré donnent du grain à moudre – leçons de formalisation … – et comme les r=100 génèrent des séries comportant 30 % de premiers, et qu’il me faut 4 séries une de 1, une de 3 une de … mais je ne suis pas pressé.
Sincèrement merci encore.

Invité
HEREDIA Serge
1 an 10 mois plus tôt

Bonjour Dr,
Je m’étais habitué à l’idée – qui me plaisait bien – du caractère parfaitement aléatoire de la survenance des premiers.
Or il se trouve que si l’on construit une liste du genre n+100
(et de l’autre côté n-100) (mais ça marche avec d’autres choix- moi j’aime bien 82+100 et 82-100 ; les 41,91 et 8 générés sont plus rigolos-).
Apparaît alors une régularité gênante dans l’apparition du premier premier dans la factorisation
Oublions le 2 et le 5, on a :
82 = 2.41
182 = 2.7.13 °
282 = 2.3.47 *
382 = 2.191
482 = 2.241
582 = 2.3.97 * * –> le 3 apparaît dans la factorisation tout les deux espaces
682 = 2.11.31
782 = 2.17.23
882 = 2.3.3.7.7* ° ° –> le 7  » tout les six
etc. le 11 tout les 10
le 13 tout les 12
le 17 tout les 16
J’arrête là, ça fait un joli dessin sur l’ordi.
Cette régularité gênante a telle un sens ? ou plus humblement puisque l’on est dans l’aléatoire où ai je commis une erreur ? votre site ( si ! si !) m’a paru plus didactique que d’autres.
En un mot est ce grave docteur ?

Invité
Amaury
1 an 11 mois plus tôt

Bonjour,

Il y a quelque chose qui me laisse perplexe dans cette course aux très grands nombres premiers. Pour obtenir un très très très grand nombre premier et battre le record actuel, ne suffit-il pas de calculer le produit de tous les premiers nombres premiers que l’on connaît et d’ajouter une unité ?
D’après Euclide, on est sûr qu’un tel nombre est premier. Et il sera plus grand que le nombre de Mersenne 2^57,885,161 − 1.

Je me doute bien que mon raisonnement doit être faux car, sans ça, d’autres y auraient pensé avant moi. Mais je suis curieux que l’on m’aide à trouver par où mon raisonnement pêche.

D’avance merci pour vos explications !

Invité
2 ans 8 mois plus tôt

salut j’ai trouvé un autre grand nombre premier (plus grand que 1700milliards et quelc.)
svp.aider moi, quesque je doit faire pour contacter les responsables de prime.

Invité
Erwann
3 ans 1 mois plus tôt

Pas besoin de passer 300 fois Miller-Rabin pour un premier de 512 bits. La probabilité qu’un composé passe le test non détecté est de 1/4 à chaque fois.

Pour du RSA, avec 2 premiers de 512 bits, on obtient une clé de 1024 bits, offrant environ 80 bits de sécurité. 40 itérations pour chacun des candidats premiers est donc suffisant. En pratique, on se contente de moins que ça.

Autre remarque, pour obtenir un premier de n bits, on choisit n-2 bits aléatoires, et on « ajoute » 2 bits à 1 de chaque côté. Votre méthode permettrait d’avoir un premier plus petit que souhaité.

Invité
Vincent Gautier
3 ans 1 mois plus tôt

bonsoir.
Certains de vos chiffres e sont plus d’actualitée : pour les riesel ( forme k*b^n-1) avec k=3, le plus haut connu est 3 * 2^6090515 – 1
les proth? 19249* 2^13018586 + 1
Si la recherche de record interesse des visiteurs, je vous conseille de faire un tour sur le forum mersenneforum.org (en anglais)