Est-ce intéressant d'un point de vue pratique de "fabriquer" à coup sûr un nombre premier inférieur à une primorielle donnée ? Genre pour la cryptographie ou je ne sais quoi ?
Bon, alors de fabriquer au moins $ 2^{k-2} $ nombres premiers inférieurs à $ P_{k} $ où $ P_{k} $ désigne le produit des $ k $ premiers nombres premiers pour un $ k $ assez grand quelconque.
Si $k$ est grand ($k=38$ suffit déjà largement) alors tes $2^{k-2}$ nombres premiers ne rentrent même pas en RAM. De toute manière aucun algo de crypto que je connaisse ne suppose un nombre premier inférieur à une certaine primorielle.
On n'a aucun problème pratique à générer des nombres premiers de cent chiffres très rapidement, et donc évidemment de moins de cent chiffres si besoin.
Bien sûr que si (on est quand même limité par la mémoire bien sûr), depuis 2000 ans au moins. Le crible d'Eratosthène en est un, même si pas le plus efficace. Si on ne savait pas générer très rapidement de très grands nombres premiers, alors RSA serait par terre. Évidemment en pratique ce n'est donc pas Eratosthène qui est utilisé ... On a trouvé beaucoup mieux depuis, surtout si on s'autorise des tests probabilistes (qui donnent un nombre premier avec moins de $10^{-100}$ de proba d'erreur en pratique ou un truc du genre, donc tout à fait négligeable). De toute manière il existe un algorithme polynômial en le nombre de chiffres pour vérifier que le nombre est premier, si besoin.
Si on va par là, sous certaines conjectures communément acceptées comme étant très probablement vraies, les constantes deviennent très honorables, et probablement applicables pour des nombres premiers de cent chiffres (je n'ai pas vérifié ceci dit).
Je ne suis pas expert, mais si en plus on tombe sur le pire cas en complexité, on retire un autre nombre et on le reteste. Mais c'est théorique, si les conjectures sont vraies même le degré du pire cas devient raisonnable, donc en pratique dans ce test exact on n'arrive jamais à la complexité théorique démontré du pire cas, ça va bien plus vite.
Et en pratique dans RSA on ne teste pas que le nombre est vraiment premier, une proba plus faible que l'inverse du nombre de particules dans l'univers nous suffit bien assez.
Euh shah d'ock, les grands nombres premiers qu'on découvre sont très très très loin de faire seulement quelques centaines de chiffres, le standard dans RSA :-D
Pour l'honneur de l'esprit humain ? :-P Mais sûrement pas pour la crypto où des nombres aussi gigantesques n'ont aucune utilité. Et en crypto c'est hyper important de générer des nombres premiers à la volée et de ne surtout pas piocher dans une table prédéfinie.
Ah d'accord. Autant la recherche "pour l'honneur de l'esprit humain" je peux comprendre, autant, dans ce cas précis, la recherche de nombre premiers gigantesques à coups de gros ordinateurs, je ne vois pas trop. Mais chacun ses passions.
L'aspect pratique me passe au-dessus de la tête mais en définissant la configuration naturelle d'un entier $ n $ comme la suite des restes de la division de $ n $ par les $ f(n) $ premiers nombres premiers avec $ f(n) $ (cf ma question intitulée About Goldbach's conjecture sur Mathoverflow) définie comme le nombre de premiers inférieurs à $ \sqrt{2n-3} $, on peut considérer le $ f(P_k) $-uplet formé de la suite des parties entières des $ p_{i}/2 +h_i$ où $ h_i \in\{0,1\} $ pour $ i>1 $ et $ h_0=0 $. C'est la configuration naturelle d'un entier $ n' $ dont le reste dans la division par $ P_k $ est un entier premier. Si de plus on remplace les deux premières composantes (restes modulo 2 et 3 ) par des 0, on devrait obtenir un entier $ N $ tel que $ N-1 $ et $ N+1 $ sont premiers. Comme il y a 2 choix pour la valeur de $ h_i $ pour chaque $ i >2 $ , on obtient au moins $ 2^{k-2 }$ couples de premiers jumeaux inférieurs à $ P_k $ .
Bien sûr les modérateurs peuvent déplacer ce message en shtam.
En fait pour $ k=4 $ seules les 4 premières composantes sont déterminantes. On obtient donc 18, 102, 108 et192. Soit les $ 2^{4-2}=4 $ couples de premiers jumeaux $ (17,19), (101,103), (107,109), (191,193) $ .
C'est le théorème des restes chinois : à un système de congruences modulo des nombres premiers $ p_{1},\cdots, p_{k }$ correspond une unique classe de congruence modulo le produit des $ p_i $. Je considère le représentant de cette classe entre 0 et ledit produit.
Je n'ai pas encore bien saisi ta démonstration (que tu n'as pas d'ailleurs écrite). Mais si ça tient, ça aurait démontré l'infinitude des nombres premiers jumeaux non ?
Intéressant ? c'est possible, mais il me semble que ce serait encore plus intéressant de pouvoir trouver à coup sûr des nombres premiers supérieurs à une primorielle donnée et notamment le premier d'entre eux...
C'est d'ailleurs une des pistes que je poursuis avec mon étude sur la primalité de P(n)2 + 4k dans l'un de mes posts récents sur le forum.
Emphyrio
Bon, vu que je n'ai toujours pas obtenu de réponse pour $k=5$, j'en déduis qu'en faisant les calculs Sylvain s'est aperçu que sa conjecture est fausse.
Réponses
Je ne suis pas expert, mais si en plus on tombe sur le pire cas en complexité, on retire un autre nombre et on le reteste. Mais c'est théorique, si les conjectures sont vraies même le degré du pire cas devient raisonnable, donc en pratique dans ce test exact on n'arrive jamais à la complexité théorique démontré du pire cas, ça va bien plus vite.
Et en pratique dans RSA on ne teste pas que le nombre est vraiment premier, une proba plus faible que l'inverse du nombre de particules dans l'univers nous suffit bien assez.
Bien sûr les modérateurs peuvent déplacer ce message en shtam.
Pour le reste c'est conforme à ce qu'on lit d'habitude venant de toi ...
On obtient ainsi les $ 4 $-uplets suivants :
$ (0,0,2,3) $ correspondant à $ N=192 $ qui modulo $ 30 $ donne $ 12 $ ,
$ (0,0,2,4) $ correspondant à $ N=102 $ qui moduli $ 30 $ donne $ 12 $ .
$ (0,0,3,3) $ correspondant à $ N=108 $ qui modulo $ 30 $ donne $ 18 $ .
$ (0,0,3,4) $ correspondant à $ N=18 $ qui modulo $ 30 $ donne $ 18 $ .
On a donc bien $ 2^{3-2}=2 $ couples de nombres premiers jumeaux distincts, à savoir $ (11,13) $ et $ (17,19) $ .
Je ferai les calculs plus tard pour $ k=4 $ (comme $ \pi(\sqrt{2\times 210-3})=8 $ ca fait 64 $ 8 $ -uplets à examiner).
Je n'ai pas encore bien saisi ta démonstration (que tu n'as pas d'ailleurs écrite). Mais si ça tient, ça aurait démontré l'infinitude des nombres premiers jumeaux non ?
Cordialement.
C'est d'ailleurs une des pistes que je poursuis avec mon étude sur la primalité de P(n)2 + 4k dans l'un de mes posts récents sur le forum.
Emphyrio
pour le cas k = 5 ça merdoie pas un peu ?
S