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

[leg]

non puique la malchance n'est pas le produit de deux nombres
-----

[invite3d7be5ae]

Voilà : ( | = divise )

p|Mn
o premier, que l'on teste pour savoir si k=o mod h(ex:15)
2*n*k+1=o mod h
k=((2n)^-1).(o-1) mod h

MAIS, pour calculer l'inverse de 2n il faut que h ne soit PAS divisible par 2.(Ce qui interdit 30,210,...).
Les solutions potentielles sont celles pour lesquelles ((2n)^-1).(o-1) mod h est premier OU divisible par 2.

une sur deux!

Pourquoi 1/2? On sait que ce nombre n'est pas divisible par les P de 1 à X.

...il faut une autre méthode plus rapide a moins de connaître la racine de Mn, ou encore la racine P modulo 30 ...

Calculer une racine (mod 30 aussi) carrée est facile.

Le reste, (même message) je ne comprend pas

[leg]

salut pole reprend l'ex pour Mn, l'exposant = 67 cité ci dessus et détail s t p
est 'il possible de trouver le couple modulo 30 dans cet exemple moi je dis le couple 7 et 31 mod 30 , un de ces facteur divise Mn =2^67 - 1
détail ton calcul est a quelle conclusion tu arrives, en mettant les valeurs....
A +

[leg]

suite, la raison est : si on pouvait déterminer quel couple (30) factorise un Mn, on utilise que les facteurs P = 7(30) pour l'exemple indiqué ! si on a deux processeur on met en parrallel aussi p =31(30) car un des facteur p(30) sera le plus petit ce qui fait une obligation minimum de deux séries d'exposant sur 8 ssi Mn se factorise par plus de dux facteurs P , par contre si Mn est le produit de deux facteurs p et q on a besoin que d'une série, mais il est impossible de savoir cela!

[invite3d7be5ae]

Comme tu peux le voir, si un algo existait, on pourrait factoriser rapidement un Mn : on prend modulo un nombre plus grand que le facteur, et c'est fini.

Mon algo donne les différents k possibles modulo un nombre(mais il doit être premier avec 2*n).

P Résultat

3 13
5 11
7 9 -> le bon
13 3

[leg]

SPH:
post#222.
je demande a Martini si il est possible de mettre le post de SpH #222
dans le fil des nombre de Mersenne car ses explication et son tableau sont en rapport avec l'algorythme P(30) et le tableau des congruences que j'ai mis Mn = 31(60) en fonction de son exposant ou 7(60) cela permettra a Sph de ne pas jeter son travail ou de le perdre! il y a une propriété trés interressant dans ses remarques et dans son tableau
le N_eme nombre premier vaut le N^eme nombre de Mersenne .
grosso modo, chaque nombre de Mersenne donne le prochain nombre premier!!!!,la suite dans les nombre de Mersenne une fois ce post déplacé merci au modérateur de faire ce patit effort sinon je ferai un copier colé A+ leg

[SPH]

haaaaa, voila qui fait plaisir. Je manquais cruellement de reconnaissance =)
Sachez que j'ai reprix l'etude des NP et je viens de découvrir quelque chose de TRES interessant !!!
Je vous dirais tout bientot...

[invite3d7be5ae]

Moi, j'ai trouvé quelque chose sur les P.
1+2=3=P
3+4=7=P
7+6=13=P
13+8=21=3*7 (donc la ligne +3 sera divisible par 3 et pareil pour 7)
21+10=31=P
31+12=43=P
43+14=57=3*19
57+16=73=P
73+18=91=7*13
91+20=111=3*37
111+22=133=7*19
133+24=157=P
157+26=183=3*61
183+28=211=P
211+30=241=P

etc...

On fait donc un crible, mais les nombres vont rapidement grandir : au bout de 1000 lignes 1 001 001
10000->100 010 001
100000->10 000 100 001.

A chaque fois que l'on multiplie par 10, les nombres sont multipliés par 100!!!

Bonne programmation.

[invitecf787e7b]

Pole,
le nieme terme de votre suite s'exprime par Un=3+(n-1)(n-2)=n²+n+1
donc cette suite croitra selon la plus grande puissance (ici n²)
si vous cherchez des Mersenne c'est a dire Un=2^x-1, a ma connaissance, personne n'a encore trouvé de valeur de n , au dela de n =90 (qui donne 8191) , qui verifie cette relation
et ensuite...?

[invite3d7be5ae]

Je ne cherche pas les 2^x-1 premiers, je cherche les nombres premiers dans le cas général. Dans mon exemple, en criblant 6 nombres, j'arrive à 241. Alors que pour Erathostène, on arrive à 31. Le problème c'est pour 7 : les deux premiers nombres divisibles par 7 ne sont pas éloignés de 7. Et ce pourrais être comme ça pour beaucoup de nombres, et peut être plus de 2. Ca peut donc être très embêtant.

[leg]

tu veux dire que tu cherche des nombre p mais pas forcement tous les pemiers? chaque résultat de chaque ligne te donnera un composé a la Nième ligne dons le nombre de p va décroître tres rapidement, non?
par ex 3ème ligne = 7+6 = 13 donc tu peux deja suprimer le résultat de la 16ème ligne le résultat est un multiple de 13 etc etc , chaque résultat va composé sa propre ligne quel interêt pole,? maintenant tu peux stocker les facteur P qui apparaisse comme
3*19,37,61, qui ne peuvent apparaître dans les résultats.

[invite3d7be5ae]

Je cherche que certains P. Mais les nombres de Mersenne aussi ce ne sont que certains nombres, et eux aussi il y a de - en - de P.
Dans mon algo, je pense avoir deux fois moins que dans celui d'Erathostène. Et ça sera surement plus puisque les facteurs 5,11,17,etc n'apparait pas.
On peut espérer de bons résultats avec cet algo.

Et on doit pouvoir tirer aussi quelque chose avec ses variantes : F(x)=x^0+x^1+x^2+x^3+x^4+....+ x^d.

[invitecf787e7b]

Dans mon algo, je pense avoir deux fois moins que dans celui d'Erathostène. Et ça sera surement plus puisque les facteurs 5,11,17,etc n'apparait pas.

Pole,
vous pensez que pour une valeur donnée de x, vous avez moitié moins de nombres premiers qu'avec le crible d'eratosthene ?
c'est cela ?

[invite3d7be5ae]

Je pense que j'aurais entre 2 fois moins de nombres premiers avec mon algo avec x cases, qu'avec le crible d'Erathostène avec x cases.
Mais le plus grand premier avec mon algo est de l'ordre de x^2 alors qu'avec Erathosthène c'est x.

[invitecf787e7b]

Pole,
votre suite X²+X+1 est une suite de densité limite nulle , on ne sait pas demontrer qu'elle contient une infinité de nombres premiers (cela fut cependant fait pour la suite n^2+m^4)
pourriez vous noter le nombre de nombres premiers que vous trouverez jusqu'a x=1000, X=10000 etc (enfin le plus grand nombre que vous pourrez atteindre )
merci

[invite3d7be5ae]

Jusqu'à 1000 : 189. 1000/ln(1000)~=144 (168 P)
10000 : 1410 10000/ln(10000)~=1085 (1229 P)
50000 : 5760 50000/ln(50000)~=4621 (5133 P)
100000 : 10751 100 000/ln(100 000)~=8685 (en vrai, 9592 P)

Donc, comme je l'ai dit, il y en a à peu autant (et même un peu plus) que de nombres premiers de 1 à x mais leur taille est x^2!

[invite3dc2c2f6]

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^² .

Salut

Cette analyse figure dans un petit bouquin intitulé "Initiation à la cryptographie", paru chez dunod, je crois, il ya quelques annees..
Je vous donnerai les references exactes de ce bouquin si vous ne le connaissiez pas..
manu

[invite3dc2c2f6]

Salut

Cette analyse figure dans un petit bouquin intitulé "Initiation à la cryptographie", paru chez dunod, je crois, il ya quelques annees..
Je vous donnerai les references exactes de ce bouquin si vous ne le connaissiez pas..
manu

Voila les references: "Initiation à la cryptographie" de G.Dubertret, Ed.Vuibert.

[SPH]

Oui, ce que j'ai découvert a certainement ete a de multiples reprises decouvert dans le passé. Merci de tes references.