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

[SPH]

Je suis dégouté par vos rapidité de programmes !!
Moi, je code en basic alors, vous comprenez !!
-----

[leg]

merci de ta réponse G-h, (il me reste encore des silex...)
bon sphou tu en est.., avec le fonctionnement de ton prog?? explique nous un peu ton procédé, si tu ne comptes pas, tu repères "la signature binaire" d'un nombre et tu fais par comparaison avec les bits que tu as en mémoire dans ta base de donnée pour savoir si il est premier...? ou autre ? quel est l'astuce..apres je t'envoi mon executable au moin tu pourras faire des essais..sinon tu vas casser le fil cela serait dommage. A.bientôt

[leg]

les bons t'avaient prévenus, pourquoi ne pas leur expliquer ce que tu faisais la plupart sont de bon conseil, même si le résultat n'aurait rient changé il y a toujours un enseignement à en tirer et parfois de trés bonnes idées.
alors explique ton idée de base. A + leg

[SPH]

....jusqu'à 500 000 000 000

Bien, me revoila. Désolé pour cette petite absence mais dans la vie, je suis insomniac et j'étais pas trop bien ces derniers temps. Mais me revoila avec une bonne nouvelle. J'ai achevé mon avant derniere etape et l'etape prochaine sera du gateau. Ensuite, je pondrais ici le resultat de mes recherches qui ont (je pense) ete fructueuses et originales.
Mais avant de franchir cette derniere etape, je reviens sur le nombre cité plus haut. Est ce le nombre de NP trouvé par vos programme ?
Si oui, et pour affiner/verifier mes recherches, est ce que quelqu'un pourrait coder ces NP de cette matiere et les compresser en RAR et enfin, les mettre en telechargement ? :
octet 0 = %01101110 (ce qui veux dire que le bit le plus a droite est a 0 car "1" n'est pas un NP. Puis le bit suivant est a 1 car "3" est un NP... Etc), ceci codant tous les NP impairs. Cela laisse un large champ de "0" et la compression est geante.
Si personne ne peux, ce sera dommage mais ca ne m'empechera pas de revenir ici pour vous proposer mon programme qui crible tous les mersenne qui ne peuvent pas etre premier et ceux qui peuvent dans certain cas l'etre.

[invited6139184]

Je pense que tu voulais dire: "le bit le plus à gauche est à 0 ..."

Au fait, tu vas pas nous refaire le coup de la spirale d'Ulam quand-même ?

[SPH]

Je pense que tu voulais dire: "le bit le plus à gauche est à 0 ..."

Au fait, tu vas pas nous refaire le coup de la spirale d'Ulam quand-même ?

non, le bit le plus a droite; c'est a dire le bit de poid faible.

La spirale d'Ulam ?? C'est quoi ?

[invited6139184]

Pardon, j'ai rien dit !

La spirale d'Ulam, c'est ça:

http://fr.wikipedia.org/wiki/Spirale_d'Ulam

( rien ne vaut un bon dessin)

[SPH]

J'ai regardé sur le net et non, ca n'a rien a voir.
Bon, bin, pensez a vos 500 milliards de NP (?)
Moi, je reviendrais ici sous peu (demain je pense)

[leg]

J'ai regardé sur le net et non, ca n'a rien a voir.
Bon, bin, pensez a vos 500 milliards de NP (?)
Moi, je reviendrais ici sous peu (demain je pense)

bonjour SPH. 500 000 000 000 est la valeur de N donc le nombre de premier jusqu'à cette valeur est : par série p(30),
pour S.23(30): S23 : → 449999999753 = 2 181 059 605 nP + ou - 1ce quite donne environ 17 mds de nombres P cela fait un gros gros fichier...
ce que je te propose, c'est de te faire parvenir l'executable, avec les librairies de nombres qui vont avec, afin d'être sûr qu'il fonctionne sur ton pc.ce programme fonctione sous windows 2000, xp . j'attendt ta réponse, si ok ,je t'envoie par mp mon adresse E m et toi la tienne par retour, car moi il m'est impossible de faire ce que tu demandes . peut-être le boulet , A +.

[fragman]

SPH, ta demande est impossible à réaliser !
En ne codant que les nombres impairs, de 1 à 500 Milliards et chaque nombre sur 1 bit, ton fichier aurait une taille de 30 Go sans compression, soit 10 Go dans le meilleur des cas en RAR...

[SPH]

SPH, ta demande est impossible à réaliser !
En ne codant que les nombres impairs, de 1 à 500 Milliards et chaque nombre sur 1 bit, ton fichier aurait une taille de 30 Go sans compression, soit 10 Go dans le meilleur des cas en RAR...

Je sais, c'est impossible, je m'en suis appercu apres coup. Et en plus, ca ne ferait pas 30Go non compressé mais 500Go !!

[leg]

sph :
dans la commande sauve, je ne sauvegarde pas dans mon algo les nombres P mais leur position ainsi que leur quantité ce qui me prend moins de place.
un exemple Série 17(30): le fichier te donnera 2 4 5 6 ..cela veut dire que le sixième entier de cette série est premier = (6*30) +17 .
2 3 4 5 ..c'est le cinquième Prem de cette série. si cela t'interresse toujours fait le savoir, par contre l'ago te donne bien le "nième" premier en entier .
l'autre algo sous dos lui, il te donne les prem par fichier ;cela fera pas mal de fichiers a envoyer..

[invitebdaccd77]

Bonjour,

je viens de parcourir tout ce fil et c'était très interressant. C'est fou le temps que les gens passent sur les nombres premiers. Il y a tout de même un site où il y a tout ce qui est connu sur le sujet. Ca vaus le coup d'aller s'y perdre un peu:
http://primes.utm.edu/primes/home.php

Concernant le droit ou non de publier de grands nombres premiers, il y a sur ce site la liste des 5000 plus grands connus actuellement (mis à jour en temps réel).

Pour les cribles, les nombres de Mersenne sont criblé jusqu'a 2^69 (soit ~6*10^20) pour les plus grands testés par le projet GIMP cité dans le fil (M79299397 a même était criblé jusqu"à 2^73 et est actuellement en cours de test). On peut aussi trouver des programmes comme NewPGen qui permettent de cribler dans un temps raisonable jusqu'à 10^15 voir même plus.

Bon, on peut toujours rêver trouver mieux, mais lutter contre une armée de mathématiciens c'est innégal...

Courage, l'espoir fait vivre !!!

[fragman]

Je sais, c'est impossible, je m'en suis appercu apres coup. Et en plus, ca ne ferait pas 30Go non compressé mais 500Go !!

Je ne sais pas comment tu calcules 500 Go, mais moi j'ai :
500 Milliards / 2 (nb impairs seulement) / 8 (chaque nombre stocké sur 1 bit) = 31 250 000 000 octets, soit 30 Go

[SPH]

Voila voila, me revoila avec de bonnes nouvelles. Apres une super soirée au macdo, je suis rentré chez moi et je sais calculter ce que j'appelle l'ADN de Mersenne. C'est une suite de chiffres qui se répetent a l'infini et qui condamne d'office un tres grand nombre de nombre de mersenne qui ne peuvent en aucun cas etre premier !!
J'aurais voulu vous fournir le programme mais il fait reference a une base de donnée tres grosse donc, pas moyen. J'aurais aussi voulu vous montrer une capture d'ecran mais FREE est mort ce soir. Alors voici un morceau de chaine (sans que j'en ai encore trouvé la boucle mais ce sera facile) :
011111011101011111111111011111 1
(et la il manque la suite mais je m'en occuperais demain car la je vais dodo)
Comment lire cette chaine a propos ? Et bien elle commence par (2^x)-1; x etant a 7. On a un "0", ce qui veux dire qu'il est probable que ce soit un NP de mersenne. Apres, on a un "1" (pour 2^8-1) et la : aucune chance. etc etc, on ajoute 1 a X a chaque fois.
Alors, cette technique etait elle deja inventée ?

[invitebdaccd77]

SPH:
Alors, cette technique etait elle deja inventée ?

C'est toujours comme ça que ce représente le résultat d'une sécence de nombres à cribler. Chaque bit représente un nombre et chaque fois qu'il y a une bonne raison pour dire qu'un nombre ne peut pas être premier (un facteur premier a été trouvé), on bascule le bit qui le représente.

Mais bon, il faut d'abord refaire ce qui est déjà connu avant de découvrir quelque chose de nouveau !!!

[SPH]

C'est toujours comme ça que ce représente le résultat d'une sécence de nombres à cribler. Chaque bit représente un nombre et chaque fois qu'il y a une bonne raison pour dire qu'un nombre ne peut pas être premier (un facteur premier a été trouvé), on bascule le bit qui le représente.

Mais bon, il faut d'abord refaire ce qui est déjà connu avant de découvrir quelque chose de nouveau !!!

Il semble que tu n'ai pas compris que je peux maintenant voir a l'infini ! style 2^444588775454912541

[invitebdaccd77]

SPH:
Il semble que tu n'ai pas compris que je peux maintenant voir a l'infini ! style 2^444588775454912541

Effectivement je n'arrive pas à comprendre ce que tu veux dire par là. Manipuler de tels nombres n'est pas forcement un problème avec l'offset qui va bien, mais trouver un nombre premier dans son voisinage est une autre affaire. Si ça te permet de trouver un nombre premier de cette taille, alors oui tu as trouvé quelque chose de nouveau !!!

[invitedebe236f]

avant de voir l infini et au de las

011111011101011111111111011111 1
(et la il manque la suite mais je m'en occuperais demain car la je vais dodo)
Comment lire cette chaine a propos ? Et bien elle commence par (2^x)-1; x etant a 7. On a un "0", ce qui veux dire qu'il est probable que ce soit un NP de mersenne. Apres, on a un "1" (pour 2^8-1) et la : aucune chance. etc etc, on ajoute 1 a X a chaque fois.
Alors, cette technique etait elle deja inventée ?
__________________
pour 8 c est pas difficile vu que x doit etre premier obligatoirement
ca donne quoi ta chaine pour les connu
http://fr.wikipedia.org/wiki/Nombre_...rs_de_Mersenne

en sachant que de 1 a 39 il y a pas entre on les a tous passe
entre 39 et 42 il est possible qu il y en ai mais je pense pas

[SPH]

011111011101011111111111011111 1
Bin, ma chaine (qui est un morceau que je dois completer et en trouver la boucle pour qu'elle se répete a l'infini), je l'ai balancé hier soir sans meme verifier si elle disait vrai et en la mattant, elle ne se troupe pas :
0 (2^7-1)=127 (7 et 127 sont premier)
0111110 la, on est a 13 donc : 2^13-1 = 8191 (13 est premier, mais je C pas pour 8191 mais ma technique m'indique qu'il est tres probable que 8191 le soit)
on continue :
01111101110 la on est a la position 17 : bingo, 17 est premier et "peut etre " que 2^17-1 l'est aussi
ETC ETC ETC...
Je sais en codant mon algo qu'il est SUR A 100% que les "1" indique une impossibilité totale !
Mais pour les "0", c'est codé de facon a ce que ce soit extremement probable mais avec un declin de probabilité quand on avance. Style, a une position entre 7 (puisque ma chaine commence a 2^7-1) et 50, il y a possibilité a 95% puis, 92% puis 90 puis peut etre quand j'arrive a 2^10000000 il y a "seulement" 70%
Mais l'avantage ENORME, c'est que je peux me permettre de cribler seulement ce qui est "probablement un Mersenne PN !!
Fini le criblage inutile de mersenne qui NE PEUVENT PAS etre NP !

[invitedebe236f]

ok pour voir dis nous combien tu a de 0 entre 1 10000000 par exemple

[SPH]

ok pour voir dis nous combien tu a de 0 entre 1 10000000 par exemple

Pas de probleme, mais laissez moi le temps (ca prendra 1 jour) pour ne pas me tromper dans certains decallage et tester pour voir si tout ce passe bien.
ps : ce n'est pas une excuse (car vous pourrez me demander ce que vous voulez) mais en ce moment, j'ai passé beaucoup de nuits blanches. Je suis donc fatigué et déphasé avec la realité et j'ai aussi une amie qui a des problemes alors j'ai des "priorité". Mais ja semaine prochaine, je pense que ce sera bon (je ne V pas etre beaucoup chez moi la)

[invitebdaccd77]

SPH:
Mais l'avantage ENORME, c'est que je peux me permettre de cribler seulement ce qui est "probablement un Mersenne PN !!

C'est bien comme ça que fonctionne tous les programme de crible, dès qu'un nombre du lot testé est rejeté (on a trouvé un facteur premier) il est éjecté de la liste et plus aucun test n'est fait à son sujet.

SPH:
Bin, ma chaine (qui est un morceau que je dois completer et en trouver la boucle pour qu'elle se répete a l'infini)

Il n'y a pas de motif qui se répète à l'infini dans les nombres premiers, mais ça me permet de comprendre ce que tu fais (enfin peut-être).

En fait, les générateurs de nombre premiers fonctionnent sur ce principe. Tu fabriques un motif avec des 1 et de 0 où 1 indique un nombre composite et 0 un nombre premier (tu peux faire l'inverse). Puis tu répètes ce motif à l'infini. Les 0 seront toujours des composites mais les 1 ce n'est pas sûr et la probabilité diminue à chaque répétition.

Pour que ça marche il faut que la taille du motif soit un p# (primorial p = p# = produit des nombres premiers jusqu'à p). Dans mon générateur perso j'ai choisi p=17 (17# = 510510). Ca donne un motif de taille raisonnable.

La méthode peut être utilisée pour cribler toute sorte de type de nombre dont les Mersennes. Je pense que c'est donc cette methode que tu utilises. Evidemment tout celà ce fait sans la moindre division, seulement des additions simples.

[SPH]

C'est bien comme ça que fonctionne tous les programme de crible, dès qu'un nombre du lot testé est rejeté (on a trouvé un facteur premier) il est éjecté de la liste et plus aucun test n'est fait à son sujet.

Encore une fois, ca permet justement de s'epargner un long test inutile quand on sais qu'a coup sur, tel ou tel nombre n'est pas premier

[invitebdaccd77]

SPH:
Encore une fois, ca permet justement de s'epargner un long test inutile quand on sais qu'a coup sur, tel ou tel nombre n'est pas premier

Oui, c'est bien ce que j'ai dis. Mais comment sais-tu qu'un nombre n'est pas premier sans un lon test autrement qu'en identifiant qu'il est divisible par un autre nombre ?

[invite8c514936]

Pareil que DanielH... Cette question me démange depuis le début de ce fil...

[leg]

bonjour,
d'aprés ce que j'ai cru comprendre, son programme analyse la "signature" d'un nombre PREMIER 0111110 = 7 par rapport au nombre composé. si pour tous les impairs composés il y a une relation, dans les colonnes que fait son algo,par rapport au nbr P; il doit pouvoir identifié P mais ce qui me surprend c'est pourquoi ne pas supprimer directement les multiples de 3 et 5 , dans ces huit colonnes ; peut être servent-ils a quelque chose ? l'algorythme doit surement travailler par comparaison...?
on verra une fois que les Premiers sont remplacés par zéro et Composés par 1; car pour l'instant j'ai du mal a imaginer... ,chaque place d'un nombre premier est défini par la place qu'occupe un nombre composé, quelque soit l'arrangement que l'on peut faire; c'est exactement comme les décimales de Pi, mais a la différence ar ex, si on prend 7*11 on sait que dans la série 17(30) en partant de ce point précis, on retrouve 7,11 et 31; 77cellules plus loin.puis 2387cellules idèm avec 31² ..etc etc; autrement dit on sait exactement ou il y aurra 1. C'est ce que fait mon algo mais pas de la même façon,
son algo doit analyser la chaine que fait un nombre.. on verra..A+

[invitedebe236f]

c est pour ca que je lui est demander combient il a de 0 entre 1 10000000 s il en a autant que de nombre premier ca sert a rien
faudrai qu il en ai max 1000

[leg]

cricri tu veux dire lorsque l'on écrit a la chaine 1,3,5,7....10000000, mais si il y a 8 colonne cela donne un modulo 16;
1 ...3...5. 7.9 . 11.13.15
17.19.21 etc.
si dans chaque colonne tu remplaces les nombre P par 0 et 1,pour les composés ..qu'est ce que cela donne ..?

[SPH]

M(adn)=
[101011111011101011111111111011 111111101111101111101111101111 111111111011111111111111111111 101111111111111111101111101111 111011101111101111111111101011 101011111111111111111111101011 101111101111111111111111111111 111111111011111111111011101111 111011111111111111111111101011 111111111111101011111111111011 111011111111101111101011111111 111111111111101111111111101011 111111111111101111101111111011 111111111111111111111111111111 101011111011111111101111111111 101111111111101011111111111111 111011101111111111101111111111 101111111111111011111011111111 101011101011111111111011101111 111111101111111011111011111111 111111111111101011111011111011 111111101011101111111111111111 111111111111111111111111111111 101111111111111011111111111011 111111101111111011111111111011 111111111111111011111011111111 101111111111111011111111111111 111111111111101011111111111011 111111111011111111111011111011 101111111111111111111111101111 111011101111111111111111111011 111011111111111111111011101011 101111101011111111111011101111 111111111111111011111011101011 111111111111111111111111111111 111111111011111111111111111111 101111111111111111111111111111 101011111111111111111111111011 111011101111111011111111111111 111111101111111111111011111011 111111111111111011101111101011 111111111111101111101011101111 111111101011111111111111111111 111111101111111111101111111011 111011111111111111111011111111 101011111011111011111111101111 111011101011111011111011101111 111111111011101111101111101111 101011111011111111111111111111 111111111111101111111111101011 111111111011101011111111111011 111111111011111111101111111111 101011111111101111101111101111 111011111111111111111011101111 101111101011101111101111111111 111011111111111011101111101111 101011101111101111101111111111 101011111111111111111111111011 101111101111111111111011101111 111111111011111011111111101111 111011111111111011101111111011 111111111011111111111011111011 101111101111111011101011111111 111111101111101111101111111111 111111111011111111111011111111 111011111011111111111111111111 111011111111111111101111111011 111111111111111111111111111111 111111111111111111101011111111 101111111011111111111111111111 111111111111111111111011111111 111111111011111111101111101111 101111111111101011111111111111 111111101111111011111111111111 111011111111111011111111111111 111011111111111111101111111011 111111111111111111101111111011 111011111011101111111011101111 111111111011111011101111111011 111111101111111011111011101011 111011101011111011111111111111 111011101111101111111011111111 101111101011101111111111111111 101111111011111111111111111111 101111111111111111111011111011 111111111111111111111111111111 111111111111111111111111111111 111111111111101111101111111111 111111111011111111111011111011 111011111011111111101111111111 111111111011111111111011101011 111011111111111111111011111111 111111111111101111111111111111 111111111011101011111011111111 111111111011101111111011111111 111011111011111111111111111111 111111111111111111101111111111 111111111111111011111111101111 101111111111101111111111111111 111111111111111111101111111111 111111111011101111111111111111 111111111111111111101111111111 111011111111111111111111101111 101011101111111111111111111011 111111111111111011111111101011 111111101111111111111011111111 111111111111101011101111111011 111011101111101011101111111111 111111111011111111111011111111 111111101111111111111111111011 111111111111111111111111101111 111011111111101111111111111011 111111101111111011111111111111 101111111111111011111111101111 111111111011111111111111111011 101011111111101111111011111011 111111101111111111111111111111 101011111111101011111011111111 111111111111111111111011101111 111111101111111011101111101011 111111101111111111111111111011 111011111111111111111111111011 101011101111101111111111111111 101111111111111111111111111111 111111111011111011111111111111 111011111011111011111111101111 101111111111101111101111111111 111111101111101111111111111011 101111111011111111111111111011 111111111111111011101111101111 111111111111111111111011101111 111111111111111111111011111111 1]

Cet ADN commence a 2^4 et boucle a l'infini. Je ne l'ai pas verifié, je fais confiance a ma programmation.
Tous les "0" sont des NP de mersennes potentiels

ps : pénible ces séparations alors que tout est compact dans mon post !!!!