[MATHS] Voies alternatives pour générer de grands nombres premiers

Voies alternatives pour générer de grands nombres premiers [MATHS] - Sciences - Discussions

Marsh Posté le 18-03-2005 à 08:25:48    

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.


Message édité par initial le 18-03-2005 à 08:26:29
Reply

Marsh Posté le 18-03-2005 à 08:25:48   

Reply

Marsh Posté le 18-03-2005 à 10:11:18    


 
p = 7
 
q = 13
 
pq = 91
 
pq + 1 = 92  [:chriscool007]


---------------
Marre de perdre du temps à chercher vos sous titres ? | HFR4droid
Reply

Marsh Posté le 18-03-2005 à 10:17:41    

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.

Reply

Marsh Posté le 18-03-2005 à 10:22:08    

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...
 

Spoiler :

PROGRAM premiers;
 USES WINCRT;
 LABEL premier;
 VAR n, i, k, j : INTEGER;
     p : ARRAY[1..200] OF INTEGER;
     fic : TEXT;
 BEGIN
  n := 200;
  p[1] := 2;
  k := 3;
  FOR i := 2 TO n DO
   BEGIN
    premier :
     j := 1;
     WHILE SQR(p[j]) <= k DO
      BEGIN
       IF (k mod p[j]) = 0
        THEN BEGIN
              k := k + 2;
              GOTO premier
             END;
       j := j + 1
      END;
     p[i] := k;
     k := k + 2
   END;
 FOR i := 1 TO 200 DO
  BEGIN
   WRITE(p[i] : 6);
   IF (i MOD 10) = 0 THEN WRITELN
  END
END.


 
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


Message édité par Profil supprimé le 18-03-2005 à 10:40:15
Reply

Marsh Posté le 18-03-2005 à 10:25:34    


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


Message édité par leFab le 18-03-2005 à 10:26:19

---------------
L'ennemi est con : il croit que c'est nous l'ennemi, alors que c'est lui ! (Desproges)
Reply

Marsh Posté le 18-03-2005 à 10:27:46    

ToYonos a écrit :

p = 7
 
q = 13
 
pq = 91
 
pq + 1 = 92  [:chriscool007]


 
 

leFab a écrit :

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


 
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... :D

Reply

Marsh Posté le 18-03-2005 à 10:29:56    

barnabe a écrit :

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.


:D.
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 :D
 
(bon, je suppose que c'etait du second degre ton post et que j'ai pas compris)

Reply

Marsh Posté le 18-03-2005 à 10:44:22    

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. [:hara_kiri]


Message édité par Profil supprimé le 18-03-2005 à 11:42:18
Reply

Marsh Posté le 18-03-2005 à 10:46:43    

barnabe a écrit :

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.

la somme de nombres impairs est paire, forcément  :lol:  

Reply

Marsh Posté le 18-03-2005 à 10:50:28    

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 :)
 

Reply

Marsh Posté le 18-03-2005 à 10:50:28   

Reply

Marsh Posté le 18-03-2005 à 10:52:19    

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

Reply

Marsh Posté le 18-03-2005 à 11:09:38    

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).

Reply

Marsh Posté le 18-03-2005 à 11:10:17    

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

Reply

Marsh Posté le 18-03-2005 à 11:10:20    

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

Reply

Marsh Posté le 18-03-2005 à 15:56:07    

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?


Message édité par initial le 18-03-2005 à 15:56:57
Reply

Marsh Posté le 18-03-2005 à 16:42:49    

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...


---------------
Ddr555: y'a pas à argumenter, si tu avais ma conviction tu comprendrais pourquoi. mais non c'est tellement mieux de garder ton idée qui n'a aucun sens...
Reply

Marsh Posté le 18-03-2005 à 17:57:32    

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

Reply

Marsh Posté le 18-03-2005 à 18:01:06    

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

Reply

Marsh Posté le 18-03-2005 à 18:01:29    

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

Reply

Marsh Posté le 18-03-2005 à 20:14:20    

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.

Reply

Marsh Posté le 18-03-2005 à 21:16:22    

up!

Reply

Marsh Posté le 19-03-2005 à 09:01:06    

le grec s'appelle Euclide...

Reply

Marsh Posté le 19-03-2005 à 09:56:31    

initial a écrit :

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.


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


Message édité par art_dupond le 19-03-2005 à 14:18:14
Reply

Marsh Posté le 19-03-2005 à 10:03:29    

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.

Reply

Marsh Posté le 19-03-2005 à 16:52:58    

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

Reply

Marsh Posté le 20-03-2005 à 00:37:22    


 
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).
 

initial a écrit :

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)?


 
À 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.
 
++


---------------
b.net Harkhih#2255 // mtga Harkhih#25596
Reply

Marsh Posté le 22-03-2005 à 09:51:14    

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...

Reply

Marsh Posté le 22-03-2005 à 12:17:20    


 
Pas d'accord avec ça :p
 
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é ?)


---------------
J'ai un pseudo à numéro, et alors ? Des gens célèbres ont un pseudo à numéro, regarde Louis14 !
Reply

Marsh Posté le 22-03-2005 à 13:03:12    

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

Reply

Marsh Posté le 22-03-2005 à 16:05:10    

nathan_g a écrit :

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é :D 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).


---------------
J'ai un pseudo à numéro, et alors ? Des gens célèbres ont un pseudo à numéro, regarde Louis14 !
Reply

Marsh Posté le 22-03-2005 à 16:44:45    

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

Reply

Marsh Posté le 22-03-2005 à 16:46:04    


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

Reply

Marsh Posté le 25-03-2005 à 08:47:33    

up!

Reply

Marsh Posté le 25-03-2005 à 09:32:06    

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) ?


---------------
oui oui
Reply

Marsh Posté le 25-03-2005 à 10:55:37    


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.

Reply

Marsh Posté le 25-03-2005 à 15:22:02    

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.

Reply

Marsh Posté le    

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed