Bonjour,  
 
Je cherche à me documenter sur les pistes possibles qui existent pour trouver de très grands nombres premiers (plus d'un million de chiffres), outre la voie des nombres de Mersenne (associés au très rapide test de Lucas-Lehmer).  
 
1°) Existe-t-il des formules qui donnent un fort pourcentage de nombres premiers? J'ai pensé à la formule d'Euler (http://membres.lycos.fr/villemingerard/Premier/formule.htm) par exemple.  
 
2°) Existe-t-il des formules qui - comme les nombres de Mersenne - donnent peu de nombres premiers mais se prêtent à des tests de primalité très rapides (du fait de la spécificité de la forme des nombres testés)?  
 
Merci.

 
p = 7
 
q = 13
 
pq = 91
 
pq + 1 = 92  

Je ne sais pas si ça peut aider mais la conjecture de Goldbach dit que si deux nombres sont premiers et non égaux à 2, alors leur somme est paire.

Fais tourner pascal avec ceci, je pense que ca devrait t'aider, change juste les 200 premiers premiers, par les 2000...ou encore plus si ca te tente...
 

 
Désolé pour la structure du programme...c'est un simple copier-coller.
J'espère aussi que le programme n'est pas trop mal monté, le type qui l'a fait n'est pas un pro de l'informatique.
 
Edit : je ne suis pas sur de mon programme, alors je le mets en spoiler, par contre ici il y a un renvoi à une logique mathématique pour trouver des nombres premiers :  
 
http://www.sig.egss.ulg.ac.be/serv [...] r/prem.htm

 
Si p et q sont premiers : p et q sont impairs, donc p*q est impair, donc "p*q + 1" est pair...  

 
En fait j'aurais plutot tendance a dire que a part pour 2, p,q premiers => p, q impair.
Donc pq impair, donc pq+1 pair.
 
Enfin moi je dis ca mais sinon on peut donner d'autres exemples...

.
C'est pas un peu l'inverse lol:lol:
Si un nombre est pair non egal a 2, alors il est la somme de deux nombres premiers.
 
Parce que sinon Goldbach il a vraiment fait fort ssur sa conjecture
 
(bon, je suppose que c'etait du second degre ton post et que j'ai pas compris)

Je pense que si on résume le tout :  
 

• Après "2", les premiers que l'on rencontre sont tous impairs.

• Le produit de deux impairs est un impair.(1)

• La somme de deux impairs donne un pair.(2)

Soient p,q deux impairs, on a :  
 
par (1), p*q + 1 = un pair.
par (2), p+q = un pair.
 
Edit : j'ai l'orthogaphe d'un chimpanzé trisomique parfois.

la somme de nombres impairs est paire, forcément    

Goldbach dit, en gros, que tout nombre pair superieur à 2 est la somme de deux nombres premiers.
 
La version alternative : tout nombre entier est la somme de trois nombres premiers
 

Pour répondre à la question initiale, jusque ici on n'a pas trouvé mieux que Mersenne :-/
 
Voir le projet GIMPS pour plus d'infos.

Par contre pour se rapprocher a la fois de la question et de ce qu'a dit Stephen, si (Pj)j est la suite des nombres premiers, la suite ([PI](j=1..n)Pj + 1)n doit donner, si ce n'est que des premiers, au moins un bon pourcentage de ceux-ci non? (mais c'est pas tres interessant parce que ca coute quasiment aussi cher a verifier qu'un candidat quelconque, vu qu'il n'y a que les premiers qu'on ne verifie pas, et c'est les moins chers, donc on gagne au niveau du taux de reussite, mais pas vraiment au niveau du cout de verif).

y a pas des projets en informatique quantique sur ce sujet ?

Heheee, j'ai grille a la fois casediscute et welkin

Bon alors, tout d'abord, je me réjouis de voir que ce topic a autant de succès.  
 
Je vais tâcher de répondre à tout le monde :
 
la conjecture de Goldbach n'est pas intéressante ici. Elle ne nous aide aucunement à trouver ou à sélectionner des nombres premiers. (ou alors montrez-moi comment vous procédez...)
 
l'informatique quantique, pour l'instant, n'existe qu'à l'état embryonnaire. et il est probable que l'on reste à ce stade encore quelques décennies. voir : http://fr.wikipedia.org/wiki/Calculateur_quantique
 
casediscute, merci pour ton code source. cependant, ton code source implémente le crible d'Eratosthène. cette méthode est la plus simple (et la plus lente) qui existe pour trouver des nombres premiers. ce test consiste à essayer de diviser n par tous les nombres premiers inférieurs à racine carré de n. si on ne parvient pas à trouver de diviseurs dans cet intervalle, alors n est premier.  
 
j'ai déjà vu le site du projet GIMPS. mais justement je cherche des voies "alternatives", qui ne font pas appel aux nombres de Mersenne et au test de Lucas-Lehmer. (par ailleurs, sur le site, aucune autre méthode n'est expliquée.)
 
GregTtr, je n'ai pas bien compris ta formule. tu fais le produit de tous les nombres premiers inférieurs à n et tu ajoutes 1, c'est ça?

Oui.
C'est un moyen comme un autre d'obtenir des nombres gigantesques, et ilsseront probablement premiers plus souvent qu'a leur tour.
Mais bon, je dis ca comme ca hein, ca sort de rigoureusement nulle part, mes souvenirs d'arithmetique ont bientot 10 ans comme ma prepa alors...

Oui, c'est pas mal hein, pour quelqu'un qui fait une these de maths .
C'est de la belle perf' niveau CE2
 
Note que tant qu'a dire une connerie, autant en dire une enorme, ca a plus de panache
 
Bon WE en tout cas.

Ah, ben ca c'est ce que j'ai dit

Mais moi c'etait un melange de vague souvenir et de conjecture.

essayons la formule de GregTtr...
prenons n = 3 et calculons : 2*3 + 1 = 7. PREMIER
prenons n = 4. 2*3*4 + 1 = 25. COMPOSE
prenons n = 5. 2*3*4*5 + 1 = 121. COMPOSE
prenons n = 6. 2*3*4*5*6 + 1 = 721. COMPOSE
prenons n = 7. 2*3*4*5*6*7 + 1 = 5041. COMPOSE
...
 
Il semble en fait que la formule de GregTtr ait un très faible rendement. Mais il a compris le principe de ma question. J'attends d'autres suggestions, d'autres formules, d'autres idées ou d'autres informations pouvant faire avancer notre problème.
 
PS : si vous voulez proposez une formule génératrice d'un fort taux de nombres premiers, veuillez la tester vous-même auparavant et voir ses résultats dans la pratique...
 
PPS : pour motiver la recherche, sachez que si vous trouvez une telle formule, vous pouvez gagner le Prime Prize (100.000 $ pour un nombre premier de plus de 10 millions de chiffres). sachez aussi que vous et toute votre famille aurez la joie de vous voir enlevés et séquestrés (gratuitement) par les services secrets français.

up!

le grec s'appelle Euclide...

 
 
euh, faut pas multiplier juste des nombres premiers ?
 
parce que 4 fois n'importe quoi ne donnera jamais un nombre premier

Autant pour moi!
 
Cependant, continuons la liste :
prenons n = 13. 2*3*5*7*11*13 + 1 = 30031. COMPOSE  
prenons n = 17. 2*3*5*7*11*13*17 + 1 = 510511. COMPOSE  
...  
il serait intéressant, toutefois, de réaliser des statistiques sur des plages plus étendues.

il n'y aurait pas un gentil programmeur pour nous faire ça?

 
Oui, c' est une démonstration classique, moi je préfère celle qui démontre que pour tout entien n, on trouve un premier p>n ... on fait aussi une preuve par l' absurde, mais un peu moins marquée et plus élégante (enfin, à mes yeux).
 

 
À la limite, je dis bien à la limite, le test de Miller-Rabin peut t' intéresser. Grosso modo, et pour le peu que je m' en souvienne, il s' agit d' un test de nature probabiliste basé sur la réciproque du "petit" théorème de Fermat ... quant à la rapidité du test, je ne peux pas me prononcer.
 
Pour une approche de ce test, tu peux consulter la partie IV de ce sujet, ainsi, bien sûr, que sa correction.
 
++

Je connais très bien le test de Miller-Rabin : je l'ai implémenté en C/C++ avec la librairie NTL (pour la manipulation des très grands nombres) et également avec GMP (pareil, théorie des nombres). Je connais les versions probabiliste et déterministe de ce test. Je sais aussi que le calcul de la puissance-modulo est un goulot d'étranglement qui rend le temps d'exécution assez long. Toutefois, il est vrai que ce test est et demeure LE test généraliste probabiliste le plus rapide du monde...

 
Pas d'accord avec ça
 
Si p_1 , ... , p_n sont les n premiers nombres premiers, alors :
- soit p_1 ... p_n + 1 est premier,
- soit p_1 ... p_n + 1 n'est pas premier et est le produit de nombres premiers plus grands que p_n
 
Ça sert seulement à démontrer que p_n n'est pas le dernier nombre premier, et que donc la liste des nombres premiers est infinie
 
(j'espère que je ne suis pas grillé ?)

Un excellent livre (parmis d'autres) pour vulgariser les nombres premiers (je crois d'ailleurs qu'on y trouve aussi une présentation assez clair du test de Miller-Rabin et des difficultées qui y sont attachées) :
 
http://www.amazon.fr/exec/obidos/A [...] 00-5907411

 
Excellent livre ! Je l'ai acheté et dévoré Par contre, certaines démonstrations sont un peu ardues... mais je le recommande à tous les matheux passionnés de nombres premiers (le même auteur a d'ailleurs fait un livre sur Pi, très intéressant lui aussi).

je confirme. j'ai lu ce livre également.

vas-y vas-y efface, personne a rien vu !

up!

youp,
 
des indiens n'avaient pas trouvé un "super" test il y a un an ou deux (j'ai vu un article mais pas lu) ?

Mais je ne comprend pas vraiment, c'est quoi le but ici ?
 
S'il s'agit de trouver des grands nombres premiers, tu ne trouveras pas mieux que Mersenne. Une méthode alternative, d'accord, mais pour quoi faire ? Oriente un peu la question.

Bon j'oriente la question : trouver des voies alternatives permettrait peut-être de dépasser les performances de la technique des nombres de Mersenne.  
 
Le test des 3 indiens s'appelle "AKS" (http://membres.lycos.fr/villemingerard/Premier/testprim.htm?#t2002) mais c'est un test déterministe, et non probabiliste. Utiliser des tests probabilistes (comme Miller-Rabin) est beaucoup plus rapide.