>> Sécurité de l'état / Nombres premiers

[SPH]

En fait, la dimention "temps" compte t'elle vraiment ? Un peu quand meme. Le principal est de trouver un NP de mersenne en un temps raisonnable.
Juste une question sur le logiciel "mathematica", est-il fait pour donner des nombres premiers ? Si oui, jusqu'a combien de chiffres ?
Sait-il multiplier plusieurs NP entre eux ?
Si ce logiciel ne le fait pas, y a t'il un autre logiciel qui le fait ?

J'ai etudié a mort pendant que mon ordi calculait un truc et j'ai trouvé que rien que les NP 2;3;5 et 7 eliminaient exactement 2/3 des possibles NP de mersenne. Quand je dis que j'ai etudié, je veux dire que j'ai trouvé et que je sais expliquer !!
-----

[invite3d7be5ae]

Mathematica peut aller jusqu'à des nombres très grands.

[SPH]

Bon, pour ne pas que je me plante, qui peux me confirmer que le produit des NP compris entre 0 et 320 commence par 19361.... et fini par 6570 ???
THX

[Le_boulet]

Bonsoir,

En cherchant à répondre aux différentes questions que vous posez, j'ai trouvé ça:

http://www.bibmath.net/crypto/comple...spremiers.php3

Et ce qui a retenu mon attention, c'est la phrase:

"Ainsi, si l'on choisit un nombre de 500 chiffres au hasard, on a environ un chance sur ln(10500) de tomber sur un premier, c'est-à-dire environ une chance sur 1150. Tout cela reste très raisonnable!"

Autrement dit: plus de chance qu'en travaillant uniquement avec des Mersenne. Et ça rejoint mon post n° 85. He he !!!

Autrement dit, si on cherche un grand premier, mais pas forcemment une loi de répartition, on a plus de chance de tirer le "jack pot" en procédant au hasard, en générant des grands nombres.

Bon d'accord, ça ne résoud pas le problème du test de primalité à la vitesse de la lumière ... Mais lisez quand-même tout le lien, il est court mais intéressant.

[SPH]

"Ainsi, si l'on choisit un nombre de 500 chiffres au hasard, on a environ un chance sur ln(10500) de tomber sur un premier, c'est-à-dire environ une chance sur 1150. Tout cela reste très raisonnable!"

1/1150 = raisonnable ???
Je ne trouve pas !
Sache que les nombres de mersenne se trouvent TOUS (sauf 3 et 7) dans ma derniere colonne :

01 03 05 07 09 11 13 15
17 19 21 23 25 27 29 31
33 35 37 39 41 43 45 47
etc.........

Ca reduit deja par 8 la malchance !!

Ensuite, je sais trier 2 nombres de mersenne qui ne peuvent pas etre premiers sur 3 !
Ca reduit encore ma malchance...

[Le_boulet]

Aie aie aie !! J'aurais du dire : "à peu près autant de chances". Tu as raison.

Mais l'économie du temps de calcul d'un nombre de Mersenne n'est pas négligeable.

[leg]

sph.ou je fait une érreur ou ton program est trop "lourd"

J'ai etudié a mort pendant que mon ordi calculait un truc et j'ai trouvé que rien que les NP 2;3;5 et 7 eliminaient exactement 2/3 des possibles NP de mersenne. Quand je dis que j'ai etudié, je veux dire que j'ai trouvé et que je sais expliquer !!

un nP de mersenne ne peut être premier ,si il n'est pas congrue 1(120); 31(510) ou 7(120)c'est à dire: 1 ou 7 modulo 30 implique dans ton program Mn -1 ou 7, /30 tu élimines plus des 2/3 ..
regarde sur les premiers Mn..je regarde quelque chose et je revient

[leg]

re bonjour à tous, sph je viens de regarder:
Mn^p , se termine par 2 ou 8 , 2 ou 8 ..2 , 8 ,etc c'est un cycle
par ex pour Mn qui se termine par 8, alors Mn-8 se divise par 120 il est congrue 7(120) ou 30. si il se termine par 2 , alors Mn-2 se divise par 30 il est congrue 1(30) mais certain sont congrue 31(510) cela ne t'apporte rient de plus, donc tu garde Mn-2/30 car faire Mn-32/510 risque de te faire faire un test de plus .
Par contre il faudrait regarder si il y a plus de Mn-31/510 qui sont premier par rapport au Mn-1/30 il faut prendre les Mn dans l'ordre de progression jusqu'a Mn 42 et controler la proportion . Mn-1/30;Mn-31/510 et Mn-7/120..A+

pole : qu'entends tu par des nombres tres tres grands avec mathematica, et : est ce le nombre exact ou une estimation en utiliasant une constante ? par ex que donne mathematica pour 10^19, 20 , et 21 (combien de nombre P jusqu'a ces lim) ou
450 milliards .

[invite3d7be5ae]

sph : ton calul est juste.

leg : quand Mathematica marchait, il pouvait utiliser des grands nombres (je n'ai pas tester la limite).
A mon avis, cette limite doit être dans le million de chiffres

[SPH]

Plus de la moitié des Mx ne sont pas premiers (j'avais dis 2/3 mais je ne peux plus l'affirmer). Par contre, j'ai trouvé que tous les nombres (2^"nombre pair > 2")-1 eliminent 1/2 des mersennes.

ps: j'ai la tete qui bouillonne

[invite3d7be5ae]

Mx est premier -> x est premier. Essayes tous les cas où x est premier.

Pour x pair, il est facile de la factoriser : Mx=2^(2*y)-1=(2^y)^2-1^2=((2^y)^2-1)*((2^y)^2+1)
Pour d'autres x non premiers on peut faire une identité y^3-1=Mx et en déduire des facteurs.

Ce qui va t'avancer beaucoup SPH.

[invite3d7be5ae]

Voilà, j'ai fait le crible d'Erathosthène ici

Note : il faut le renommer en .exe pour l'éxécuter.

[SPH]

J'ai commis l'erreur de tout faire en base 10. Alors, c'est tres long. Donc, je vais tout recommencer mais en base 2. Ce sera plus rapide et plus facile. Mais comment je n'ai pas pu y penser plus tot !!!?!!?

[invite4793db90]

Voilà, j'ai fait le crible d'Erathosthène ici

Note : il faut le renommer en .exe pour l'éxécuter.

Salut,

ça ne fonctionne pas chez moi (WXP): lorsque je clique sur Calculer, le programme se ferme.

Cordialement.

[invite4793db90]

J'ai commis l'erreur de tout faire en base 10. Alors, c'est tres long. Donc, je vais tout recommencer mais en base 2. Ce sera plus rapide et plus facile. Mais comment je n'ai pas pu y penser plus tot !!!?!!?

Salut,

moi je calcule les nombres de Mersenne en base 2 de tête!

[g_h]

J'ai commis l'erreur de tout faire en base 10. Alors, c'est tres long. Donc, je vais tout recommencer mais en base 2. Ce sera plus rapide et plus facile. Mais comment je n'ai pas pu y penser plus tot !!!?!!?

T'abuses !

Extrait des messages de ce fil :

[...] je ne vois vraiment pas ce qu'il y a de sorcier à mettre un 1 avec 500 000 000 zéros derrière [...]

En java, en faisant des décalages, j'arrive à 2^(2^26). [...]

Et extrait d'un MP que je t'ai envoyé :

[...] Pour reprendre le sujet du fil sur les nombres premiers, je voudrais insister sur le fait que calculer 2^n avec un ordi est quelque chose d'extrêmement rapide, pour la simple et bonne raison que 2^n est codé en mémoire par un 1 suivi de n zéros (en binaire donc). Je sais pas en quel langage tu programmes, mais en C, ce "calcul" se résume à l'allocation d'un gros bloc mémoire, de sa mise à zéro, et à la modification du premier octet du bloc (ça dépend aussi de si on est en big endian ou en little endian, mais il n'y a pas plus de difficulté) [...]

On ne peut pas dire que tu n'as pas été prévenu... !

[SPH]

On ne peut pas dire que tu n'as pas été prévenu... !

Je sais mais j'avais commencé (et j'ai tjr travaillé) avec des nombres découpé en bout de 2 ou 4 chiffres. Egalement, je me bornais a croire que tot ou tard, je devrais reconvertir la base 2 en base 10. Mais finalement, non !! Je peux travailler de bout en bout avec de la base 2. !!
Quand a martini, oui, moi aussi, je sais citer tous les mersennes de tete en base 2

[leg]

bonjour , Martini- bird je clic sur : ici ; j'ouvre wanadoo mais je n'ai pas trouvé , le crible d'E.. qu'elle est la suite SVP merci
sph je pense que maintenant, tu devrait un peu nous éclairer sur ton algo, comment ton program test un Premier, dans les grandes lignes...
si j'avais au moins pu charger celui que tu viens de mettre a dispo, je pourrais faire une comparaison avec le mien malgrés qu'il ne me sert pas à celà, puisque pour cribler un grand Mn et en supposant qu'ilsoit Composé avec un facteur congrue 19(30) en n'utilisant que les facteurs premiers de cette série qui ne représent 30% de 3,3% des entiers naturels, je ne pourrais pas extraire suffisament de facteurs premiers de cette série ou il me faut 1h 20 pour les extraitre jusqu'à 500 000 000 000 , ce qui ne représente qu'une infime partie du nombres de facteur P 19(30) qu'il me faudrait pour le criblage il faudrait plusieur PC ..

[invite4793db90]

bonjour , Martini- bird je clic sur : ici ; j'ouvre wanadoo mais je n'ai pas trouvé , le crible d'E.. qu'elle est la suite SVP merci

Salut,

pardonne-moi, mais je n'ai pas compris ce que tu demandes.
A ce propos un petit effort de rédaction de ta part serait le bienvenue.

Cordialement.

[invite3d7be5ae]

Mon prog ne marche pas? Je l'ai fait en Delphi4.

Mais finalement, non !! Je peux travailler de bout en bout avec de la base 2. !!

Et pour l'affichage, c'est quand même plus lisible en base 10 pour des humains normalement constitué.

[invite4793db90]

Mon prog ne marche pas? Je l'ai fait en Delphi4.

Pas chez moi en tout cas, à moins que le bouton Calculer serve à fermer le programme.

[leg]

Salut,

ça ne fonctionne pas chez moi (WXP): lorsque je clique sur Calculer, le programme se ferme.

Cordialement.

martini-bird , sur le post de pole, pour le crible d Erathosthène lorsque je clic sur le lien ici
[Posté par Pole
Voilà, j'ai fait le crible d'Erathosthène ici ]
cela m'ouvre une page d'érreur sur wanadoo (ne trouve pas le site) ?
merci A +

[invite4793db90]

martini-bird , sur le post de pole, pour le crible d Erathosthène lorsque je clic sur le lien ici
[Posté par Pole
Voilà, j'ai fait le crible d'Erathosthène ici ]
cela m'ouvre une page d'érreur sur wanadoo (ne trouve pas le site) ?
merci A +

OK,

l'adresse est la suivante: http://perso.wanadoo.fr/polek/Erathosth%E8ne

Avec Firefox, ça marche: tu utilises quel brouteur?

[leg]

merci Martini çà marche,je lai téléchargé. Pour ta question:

là je suis à ma sté, le logiciel que j'ai est celui du réseau pour lequel je bosse, je sais uniquement que je passe par cégétel..on n'a pas de méssagerie je n'en sais pas plus.
pour G-h:
mon algo est en C++, peut'il être amélioré afin qu'il écrive sous dos car dans windos je suis bloqué a 2 giga de ram mon pc dispose de 4 giga de ram est un processeur de 3,6 gh; ce qui ne me sert a rient sous XP pro car windos n'alloue que 2 giga par instance de program.
lorsque j'énumère tous les Premiers jusqu'à 500 000 000 000; j'arrive a 2047 méga de ram, donc je ne peux pas augmenter la taille de mon tableau afin d'extraire le double de Prem.
j'ai les fichiers sources. serais tu interressé pour me donner ton avis..A+

[g_h]

leg> Windows permet à chaque programme de disposer de 4 go de mémoire (depuis Windows 95)

Si tu passes sous DOS (drôle d'idée !), tu seras obligé de travailler en 16 bits... donc pour travailler sur des grands nombres, c'est pas le must.
De plus, DOS fait tourner ton proc en mode réel ou en virtuel 8086 (si tu es sous windows) et ne permet pas de profiter de ton processeur à 100%... de plus cela te permet de disposer de 1 Mo de mémoire au maximum, avec des adresses codées sur 20 bits, et avec en prime une mémoire segmentée en blocs de 64 ko... que du bonheur !
Donc reste sous windows !

Sinon, vérifie qu'il te reste de la mémoire disponible quand ton programme a déjà alloué 2 Go...
Si il en reste, essaye de faire tes allocations avec des routines de l'API Windows comme LocalAlloc ou GlobalAlloc (il me semble que c'est la même chose) ça peut peut-être te permettre de disposer de plus de mémoire... mais je ne garantis rien.
(attention, penser à inclure Windows.h)

Si tu veux mettre les sources, vas-y, ça peut intéresser du monde (si c'est à caractère mathématique bien sûr)

[leg]

Pas chez moi en tout cas, à moins que le bouton Calculer serve à fermer le programme.

je n'arrive pas a faire marcher le programme, il ne s'ouvre même pas

[leg]

merci de ta réponse G-H, mais ce n'est pas moi qui est écrit le program en c++,c'est un ami , je n 'y connais strictemenr rient dans ce domaine.j'ai juste donné les instructions et le fonctionnement de l'algop(30)
j'ai envoyé l' executeur à" toufou "mais il faudrait faire une comparaison avec le crible d'Erathosthène en sortant tous les premiers par ex jusqu'a 10 mds pour comparer les temps, ou si on peu l'ameliorer.(attention, penser à inclure Windows.h)que veux dire cette phrase. ?
quand je lance l'algo je regarde dans les performances du gestionnaires de tâches de windows, des que j'arrive à 2047 mo, le programme ferme, alors que j'ai en tout: 4 giga de ram??? et un informaticien m'a dit : windows n'alloue que 2000 mo par instance de programe , autrement dit mon program pour aller au delà de 500mds, ilfaudrait qu'il utilise 4000 mo de charge dédiée .peut être qu'il y a une érreur dans l'ecriture du program ?? d'où windows me bloquerait lorsque j'arrive à 2047 mo de charge dédiée..

si tu veux faire un essais je peux te l'envoyer , avec les fichiers sources il y en a huit je ne sais pas ci c'est a carractère mathématique, mais je peux te laisser le soin de les mettre sur le fil cela est une bonne idée et effectivement cela peut intéresser du monde au moins pour le fonctionnement de l'algo etc.. a+

[invite3d7be5ae]

Bizarre : chez moi, il marche. Normalement, il calcule les nombres premiers jusqu'à la valeur qu'on met, les mets dans premier.txt et les nombres jumeau dans jumeau.txt.
Il peut aller jusqu'à 10^6 (en 1 seconde).
Donc pour 10^9(en modifiant un peu le prog)->16min40

Les voici pour 10^6 : premier et jumeau.
Si le lien ne marche pas (pour moi, il marche) merci de le corriger.
Il y a 2 fois 5 dans jumeau.txt.

S'il se ferme, il ne faut pas mettre plus de 10^6 dans la case de droite.

[leg]

pole :
je viens de controler avec tes données jusqu'a 999999000 en 7secondes par série p(30) ce qui me fait 56'' pour les huit séries, il y a:
6354572 premiers série 1(30) jusqu'au P = 999899911 merci de ton renseignement A+

[g_h]

Oui, en fait c'est bien 2 Go de mémoire par application sous Windows XP (curieux comme limitation...), je crois qu'il te faut aller voir vers une distrib linux !

Pour ma part, ce n'est pas la peine de faire un essai avec mon ordi qui date de la guerre (du feu)...