Premier inférieur à une primorielle
Réponses
-
Non, vu que $2$ a de grandes chances de marcher ..
-
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.
-
Si on veut un nombre premier d'au plus 100 chiffres, il suffit de prendre une primorielle plus grande que $ 10^{100} $ .
-
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.
-
Je croyais qu'on ne connaissait pas de moyen de fabriquer un nombre premier arbitrairement grand.
-
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.
-
Oui enfin AKS est un résultat théorique : c'est polynomial, certes, mais en pratique les constantes sont immondes !
-
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 connais pas le résultat dont tu parles. Ce que je sais c'est que sous RH, le test de Miller-Rabin devient déterministe et polynomial.
-
Alors pourquoi font-ils tout un foin à chaque plus grand nombre premier découvert?
-
C'est expliqué ici : https://en.m.wikipedia.org/wiki/AKS_primality_test
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
-
Ah. Mais alors pourquoi en recherche-on?
-
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. -
Je n'ai pas tout saisi, mais as-tu essayé sur des petites valeurs de k?
-
Pour $ k=3 $ on obtient le $ n=P_{3}=30 $ et $ f(n)=\pi(\sqrt{2n-3})=4 $.
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 compris comment tu fais correspondre un entier à un uplet.
-
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) $ .
-
Je n'ai toujours pas compris comment tu procèdes.
-
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.
-
Ah ok.
-
Salut
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. -
Effectivement.
-
Et pour $k=5$?
-
Je me permets de relancer ma question.
-
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.
-
Je reformule, si tu permets sieur Shah d'Ock :
pour le cas k = 5 ça merdoie pas un peu ?
S
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.8K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 52 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
Qui est en ligne 21
+16 Invités