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

[SPH]

hmmm, manifestement, il y a une erreur. On ne retrouve pas le NP mersenne (2^61)-1... Je cherche pkoi.......
-----

[SPH]

Je sais pourquoi (un décallage que j'ai oublié d'insérer)

[invite8595663a]

Tout le monde se focalise sur la recherche des nombres premiers, ce qui est absurde. La factorisation d'un grand nombre ne signifie pas nécessairement rechercher les facteurs premiers.
A mon humble avis, il est possible de factoriser des grands entiers sans se soucier de la valeur première d'un nombre.
Les réseaux neuronaux peuvent jouer un rôle important dans ce domaine.
Question : Connaissez-vous une société ou une université disposant d'un supercalculateur qui serait prête à tenter l'expérience ?
Je recherche un partenaire public ou privé qui accepterait de tester ma méthode de factorisation visant à partager les lots offerts part RSA Security.

[invitebdaccd77]

laurend:
Tout le monde se focalise sur la recherche des nombres premiers, ce qui est absurde. La factorisation d'un grand nombre ne signifie pas nécessairement rechercher les facteurs premiers.
A mon humble avis, il est possible de factoriser des grands entiers sans se soucier de la valeur première d'un nombre.

Effectivement, il n'y a pas grand chose à voir entre le recherche de grands nombres premiers et la factorisation d'un nombre. La plus part du temps, on déclare composite un nombre sans connaitre le moindre de ces facteurs premiers.

laurend:
Les réseaux neuronaux peuvent jouer un rôle important dans ce domaine.

Il est peut probable que ce soit le cas, mais pourquoi pas. Tu devrais déjà tester des décompositions de nombres de tailles raisonables pour lesquels un simple PC ferait l'affaire. Si ta méthode marche, tu peux alors augmenter petit à petit la taille est voir comment augmente le temps de carcul. Si cette augmentation est polynomiale, tu as gagné, si elle est exponentiel, c'est pas la bonne méthode...

Bonne chance !!!

[erik]

La plus part du temps, on déclare composite un nombre sans connaitre le moindre de ces facteurs premiers.

Toutefois dans le cas qui interresse Laurend (le défi RSA security) il faut qu'il produise les facteurs premiers qui compose la clé.

[leg]

bonjour Erik, c'est exact d'ailleur je ne vois pas l'interêt de factoriser un entier par des composites, d'autant plus qu'un trés ...trés... grand composite n'ayant que deux facteurs premiers tres tres grand, (quel sont les deux composés qui le factorise..?)de plus les entiers composés sont produits par des facteurs premiers et non l'inverse ; aussi je ne vois pas trops ce qu'il y a d'absurde dans la recherche des premiers ; car si c'etait aussi simple même avec les reseaux neuronaux ...
la répartition des nombres premiers est un probléme aussi difficile a résoudre que l'expansion de l'univers.

[invitedebe236f]

desoler sph
je compte 3960 nombre dans ta suite ( de 1 a 3960 ) on est d accord ?

381 0 donc possible mersenne il y a reelement 548 premier avant 3960 t en a pas eliminer boucoup

de plus si ta suite continu comme ca tu vas trouver 762 0 avant 7920 alors qu il y a 1000 premier

tres vite tu aura plus de nombre a tester que de premier

soit j ai rien comprit soit c est totalement inutile ton calcul

[SPH]

Cricri, oui, je suis aussi perplexe que toi.
Je suis en quete des nombres premiers et je dois explorer d'autres solutions. Et comme le dit "laurend" (et d'autre), je me demande si finalement la solution la plus rapide ne serait elle pas le test de nombres finissant par 1,3,7 ou 9.
En tout cas, j'ai appris des TAS DE CHOSES sur les NP et je continu avec passion dans ce domaine.
Actuellement, je cherche si a la base il n'y aurait pas un stockage des NP au niveau binaire...
Bref, je cherche

[invitedebe236f]

je crois que tu n as pas comprit le reel probleme des nombres de mersenne

2^x -1 le plus grand connu x =25 964 951
x premier

trouver le premier suivant 25 964 951 ca ce fait en 2 secondes
calculer 2^x -1 pareil 10 secondes
mais prouver qu il est premier ca prend 80 jours

cherche des nombre premier n est pas le probleme

au pif je dirais qu entre 25 964 951 et 32 000 000 il y a 1 seul mersenne

[SPH]

je crois que tu n as pas comprit le reel probleme des nombres de mersenne

2^x -1 le plus grand connu x =25 964 951
x premier

trouver le premier suivant 25 964 951 ca ce fait en 2 secondes
calculer 2^x -1 pareil 10 secondes
mais prouver qu il est premier ca prend 80 jours

cherche des nombre premier n est pas le probleme

au pif je dirais qu entre 25 964 951 et 32 000 000 il y a 1 seul mersenne

Si, je dicerne bien que le probleme etait celui la.

[leg]

bonjour a tous; cricri
p = 25 964 951 soit = 11(30); 2p + 1 = 23(120) si est seulement si ,2p + 1 est premiers, alors 2^p - 1 est composé!

en faisant une recherche sur internet, concernant les Mn voila ce que cela donne:

• Existe-t-il une infinité de nombre de Mersenne composés ?

Euler a montré que :
• Si k >1 et p = 4k + 3 est premier, alors 2p+1 est premier
si et seulement si 2^p = 1 (mod 2p+1).
• Donc, si p = 4k + 3 et 2p + 1 sont premiers alors
le nombre de Mersenne 2^p-1 est composé
• Il semble raisonnable d'affirmer qu'il y a
une infinité de telles paires p et 2p+1

la réponse est oui, il y a une infinité de Mn composés! Le contraire serait absurde ils seraient tous premiers !


Donc je suppose, que pour p = 7, congrue 3 (4) soit 4k+3, égale (2*7)+1.

D’où les seuls nombres P qui nous intéressent sont uniquement les Premiers congrues11modulo30 soit la série 11(30)qui ne comprend que( 3.3%)/2,= 1,666% des entiers naturels( 11 + (k 60) ; 71, 131

Pour p = 11, soit 22+1=23 premier, soit un nombre de Mersenne congrue 7(120) composé.

Série 29(30)=1,666%, + Série 17(30) et Série 23(30)
Pour p = 59, + k 60 pour p = 47, + k 60 et enfin pour p = 23, + k 60 ;
on peut donc supprimer la série 17(30) « en effet (2 * 17)+1 serait multiple de 5 a l’infini

Il ne reste que 3 séries ; et 2p+1 devient congrue 17(30), 23(30)et 29(30)une infinité de premiers ce qui est facile à démontrer avec l’algorithme P(30)!

Et : (2*23)+ 1= 47qui divise :
2^23 – 1. soit le Mn 8388607 qui est donc composé

Tous Mn est congrue 31(120) ; 31(510)et 7(120) en infinité.< 6,666% des entiers naturels

Il y a effectivement une infinité de paires p et 2p+1, où : 2p+1 est congrue),17(30),23(30)et 29(30). Or dire que : si 2p + 1, ne divise pas 2^p – 1
Mn serait premier si le nombre de Mn composé est fini , est aussi contradictoire que de supposer le nombre 2p + 1 composé a l’infini a une lim x
Cela représenteraient 50 % de l’infinité des entiers premiers congrues p (30).
Est tous nombres p > 5 est égale à p (30), pour p, allant de 7 à 31 !

Si 2p + 1= 17(30), plus précisément 47 (120), divise 2^p – 1 ; l’autre facteur est congrue 11(30) ;

si 2p + 1= 29(30) soit exactement 59(60) divise 2^p – 1 ; l’autre facteur est ≡ 23(30).

Est enfin si 2p + 1 = 23(30), soit 23(120) divise 2^p – 1 ; l’autre facteur est ≡ 29(30)

Dans ces trois cas possibles, les nombres de Mersenne Mn, sont congrues 7(30)
Et les seuls cas ou Mn serait Premier, possible, 2p + 1 non premier, avec p premier.. ? ne divisant pas 2^p – 1 , uniquement pour cette catégorie de Mn

Voilà probablement la raison qu’il y aurait plus de Mn premiers lorsqu’ils sont congrues 31(120). Mais si il y a un nombre fini de Mn composés, cela veut dire qu’à une lim x, tous Mn congrues 7(30 )non divisible par 2p + 1 composé, est Premier.. ? ce qui est absurde.

c’est la famille des Nombres premiers P , ≡ P(30)
A+

[SPH]

Bien, voici un résumé complet de tout ce que j'ai trouvé concernant les nombres premiers. Peut etre mes trouvailles sont elles connues mais qu'importe, je vous dit tout ici avant que mon travail soit perdu :

Tout d'abord, voici le genre de tableau sur lequel j'ai exclusivement bossé : 8 colonnes et autant de ligne que nécessaire remplis de nombres impairs :

--C0 C1 C2 C3 C4 C5 C6 C7
L0 01 03 05 07 09 11 13 15
L1 17 19 21 23 25 27 29 31
L2 33 35 37 39 41 43 45 47
etc.......

J'ai remarqué qu'il y a des effets de copie et de mirroir quand on crible avec euratostene.
Par exemple, quand on crible 3 et 5, on obtient ca :

01 03 05 07 09 11 13 15
17 19 21 23 25 27 29 31
33 35 37 39 41 43 45 47
49 51 53 55 57 59 61 63
Observez bien ce qu'il y a avant et apres "15" ! Ca se copie a l'envers; comme dans un mirroir. Puis cette chaine qui va de "1" a "29" se recopie a l'infini a partir de 31 !!!
"15" parce que les NP concerné sont "3" et "5" (15 etant le produit). Et la recopie de la chaine totale (de "1" a "29") est en fait une copie mais aussi un mirroir sur le nombre 2*3*5; donc 30.
Voila donc une occasion de ne cribler eratostene que jusqu'au prochain nombre mirroir. Quel est il ? Et bien 2*3*5*le prochain NP. On arrive ainsi a 210. Il sufit de s'arreter a 210 pour recommencer l'operation avec le NP "7".

Autre observation : tous les Mersennes se trouvent soit sur la ligne 0 (seulement pour 3; 5; 7; 11 et 13) soit sur la derniere colonne (colonne 7). La formule pour connaitre sur quel ligne se trouve l'eventuel mersenne d'un NP est celle ci : (2^^(NP-4) )-1
Prenons un exemple : le mersenne de NP "5" est sur la ligne (2^^("5"-4) )-1; c'est a dire la ligne 1 (ca commence a ligne 0, je le rapelle) et colonne 7 (derniere colonne). On tombe sur "31"
Un autre exemple completement inverifié mais qui est certain :
le mersenne de NP "61" est sur la ligne (2^^("61"-4) )-1; c'est a dire la ligne (2^{^57} )-1

Vous vous rapellez de l'effet de repetition et de mirroir ? Et bien, quand on crible une 20ene de ligne, on se rend compte qu'il y a ces effets dans la colonne où se trouvent tous les eventuel mersenne !
L'autre propriété de la derniere colonne est que les mersennes correspondent a la ligne (2^^x )-1.
Pourquoi c'est interessant ? Et bien, prenez seulement le tableau avec le crible du NP "3". Ca donne ca :
01 03 05 07 09 11 13 15
17 19 21 23 25 27 29 31
33 35 37 39 41 43 45 47
49 51 53 55 57 59 61 63
etc..........
Le crible se repete toutes les 3 lignes ! C'est le meme crible des colonnes en ligne 0 qu'en ligne 3.
Et comme les mersennes se trouvent en derniere colonne et qu'ils sont en ligne (2^^x )-1, ca permet d'affirmer ceci (rien que pour le crible du NP "3"):
La colonne donne [X00X00X00X00X00X00X... etc]
Les "X" sont des nombres eliminé par le crible et les 0 sont d'eventuels mersennes. Mais comme les mersennes sont à (2^^x )-1, ca permet de reduire notre chaine repetitive en ceci : [X0]. Car les mersennes seront en ligne 0, puis en ligne 1 puis en ligne 3 puis en ligne 7, etc. Mais comme ca boucle toutes les 3 lignes, quand on a un mersenne en ligne 3, il est en fait = au crible de la ligne 0. Voila ce que j'ai appelé l'ADN de mersenne. Ainsi, rien qu'avec le "3" criblé, je sais qu'un mersenne sur 2 est eliminé ! Je peux ainsi regarder tres tres tres loin pour savoir si le "3" a criblé ou non.

Derniere chose : j'ai remarqué qu'on pouvait cribler un NP uniquement a partir de son carré car les precedents NP ont deja criblé le reste. Par exemple, "3" crible le "15". Alors, quand on commence le criblage de "5", on peut se permettre de commencer le criblage a 5^² .

[invite3d7be5ae]

Mais il faut quand même cribler les P jusqu'à 2^x/2 pour savoir si 2^x-1 est P.

On doit aller jusqu'à quelle ligne pour trouver un nombre divisible par un P (sur la dernière colonne)?

[SPH]

Mais il faut quand même cribler les P jusqu'à 2^x/2 pour savoir si 2^x-1 est P.

Oui

On doit aller jusqu'à quelle ligne pour trouver un nombre divisible par un P (sur la dernière colonne)?

?? Je ne sais pas, je ne me suis jamais posé cette question !
Bin, la ligne 0 = 15; donc divisible par le NP "3"
Si tu veux savoir, la derniere colonne de chaque ligne = "16*Ligne+15" (les lignes commencant par 0)
Donc, la 478 ligne contient 16*478+15 = 7663

[leg]

pole, il a classé les impairs modulo 16 comme le crible d'erathostène ,
donc tous les 2^p - 1, sont = 15(16) qu'ils soient premiers ou composés, cela ne donne pas d'indication sur le produit de ces nombres, pour les relations de ces nombres ça continue sur l'autre fil nombre de mersenne.

[invite3d7be5ae]

Pour p premier, la premier nombre x =0 mod p, et =7 mod 8 (dernière colonne) doit vérifier 16*x=1(puisque on doit enlever 1) mod p.
Donc x=16^-1 mod p (algo d'Euclide). Et on a la ligne!
Le pas est p.

[SPH]

Je vais prendre le tableau le plus simple du monde et vous me direz comment est le modulo :

00 01 02 03 04 05 06 07 08 09
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29
etc.....

Ici, qu'est ce qui est modulo ?

[leg]

10 ! tu vois bien que tu rajoutes 10 dans chaque colonne, à n.
si n = 11 et que tu rajoute 10 +10 +10 +10 +k 10 toutes ces sommes seront congrue 11 modulo 10 soit: n = 11(10) donc pour n = 41 , 41 -11 =30 qui est divisible par ton modulo 10. le modulo c'est le diviseur, donc lorsque l'on te dis que n = x(y) tu soustrais
x à n est du divises le résultat par le modulo . n est congrue x modulo y , c'est bon ...

[SPH]

J'ai compris :
Mon tableau d'impairs à 8 colonnes donne donc ceci :
Tous les nombres de la colonne 0 sont congru 01(16)
Tous les nombres de la colonne 1 sont congru 03(16)
Tous les nombres de la colonne 2 sont congru 05(16)
Tous les nombres de la colonne 3 sont congru 07(16)
Tous les nombres de la colonne 4 sont congru 09(16)
Tous les nombres de la colonne 5 sont congru 11(16)
Tous les nombres de la colonne 6 sont congru 13(16)
Tous les nombres de la colonne 7 sont congru 15(16)

YEEEEEEEEES

[leg]

maintenant j'attend tes exposants sur l'autre fil....

[SPH]

maintenant j'attend tes exposants sur l'autre fil....

>> Ca << tu veux dire ??

[invite3d7be5ae]

Tu as donc tous les P jusqu'à 10^5000000! Je crois que tu as oublié de dire quelque chose...

[SPH]

Bon, je ne sais pas si c'est normal mais je suis septique. Laissez moi vous dire tout mon septicisme face a la tache qui attend ceux, comme moi, qui cherche sans relache des choses inaccessibles.
Je ne sais plus trop ou j'en suis...

[leg]

non pole , il ne peut pas avoir tous les primes que tu supposes, maximum serait déjà bien si, ils les avaient jusqu'a10^25...

[leg]

sph , seul le temps est inaccessible, il faut donc continuer a chercher, une solution existe pour toutes choses, il faut tout simplement les découvrire, certaines questions ont comme solution, réponse impossible a définir dans un sens comme dans l'autre..
mais étudie la façon de programmer un algorythme de façon plus efficace , par exemple améliore celui que je 'tai envoyé en capacité est en vitesse, il est possible je pense de supprimer les cellules déjà stockées est de rajouter des cellules plus loin afin d'augmenter le nombre de premier jusqu'a x tendant vers 10^1000, etc c'est peut être le materiel qu'il faudra ...qui posera probl . A+

[invite3d7be5ae]

SPH, je crois que ton algo n'est pas performant. Mais avec des petits truc : Mn est divisible uniquement par des nombres de la forme 2*n*k+1. Résultat : moins de crible, meilleure efficacité.

Dis nous comment tu l'as programmer. (Tu peux mettre le prog sur le forum)

[leg]

pour Mn >31 Mn est divisible par P = 7,11,13,et 23 modulo30 si Mn = 7(30) mais cela sera toujours aussi long......il faut une autre méthode plus rapide a moins de connaître la racine de Mn, ou encore la racine P modulo 30 : est ce le couple, 7 et31(30), le couple 17 et 11(30) , 23 et 29 (30) ou 19 et 13(30) ???? essaye pole 2^67 - 1, racine carrée 12148001999,9 tous les facteurs prim < 12148002001 = 31(30)
Mn =147573952589676412927, par ex 412927=7(30) mon idée serait le couple 7*31(30) c'est à dire p(30)* n(30) comment déterminer si le facteur p = 7(30) ou 31(30)?en suposant qu'il existe bien P factorisant Mn dans une de ces deux séries. si on pouvait déterminer déjà le couple (30) qui factorise Mn, là cela irait trés trés vite .
quels sont les couples qui donnent un produit = 67(60).
a toi pole.

[SPH]

J'avais pensé a quelque chose que j'avais commencé a calculé d'ailleurs. J'avait multiplier tous les NP connu entre 2 et X jusqu'a obtenir un nombre a 10 millions de chiffres (j(y suis presque). Que penser de se chiffre si on lui soustrait "1" ???
J'avais pensé qu'il avait des chances d'etre premier...

[leg]

une sur deux!

[SPH]

une sur deux!

La "malchance" serait toujours divisible par le meme nombre ?