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

[SPH]

Les nombres premiers intervenants dans le cryptage, ma question est de savoir si les gouvernements interdisent la publication des nombres premiers superieur a X ?

[invitec5b86fa9]

Vu que la méthode repose en gros sur la multiplication de très grands nombres premiers inconnus, on pourrait penser ce que tu dis.

Mais le problème se situe dans la divisibilité du nombre obtenu, donc je ne pense pas qu'il interdise la publication.

[inviteab2b41c6]

Ce serait une belle entrave à certaines libertés...

[SPH]

Ce serait une belle entrave à certaines libertés...

Pourtant, pour raison d'état, tu peux etre officieusement condamné a mort... meme si c'est une liberté légitime !

[A voir en vidéo sur Futura]

[invitec314d025]

Pourtant, pour raison d'état, tu peux etre officieusement condamné a mort... meme si c'est une liberté légitime !

Faut arrêter le délire ...

Sinon, pas de loi sur la publication de nombres premiers, mais des restrictions sur l'utilisation du cryptage (et encore les lois ont été assouplies), et dans certains pays (USA) on ne pouvait pas publier le code des logiciels de cryptographie sauf sur papier. Je ne sais pas où ça en est aujourd'hui vu que des comiques ont imprimés des livres de 70000 pages, ensuite exportés et traités par OCR.

[SPH]

Faut arrêter le délire ...

Sinon, pas de loi sur la publication de nombres premiers, mais des restrictions sur l'utilisation du cryptage (et encore les lois ont été assouplies), et dans certains pays (USA) on ne pouvait pas publier le code des logiciels de cryptographie sauf sur papier. Je ne sais pas où ça en est aujourd'hui vu que des comiques ont imprimés des livres de 70000 pages, ensuite exportés et traités par OCR.

Matthias, je parle bien evidement de tres grands nombres premiers. Celui découvert cette année et qui comporte 7 millions de chiffres a fait dire a certains que ca tendait a affaiblir la securité.
Quand a ce livre de 70000 pages dont tu parles, il s'agit de nombres premiers que tout le monde peux trouver en quelques jours de calculs.
le "délire" n'en serait plus un si un bouquin de 100 pages publiait tous les nombres premiers de plus de 1 million de chiffres.
Evidement, ca demande certainement des annees de calculs pour en trouver toute une liste sur un ordi domestique et c'est sur cette gigantesque entreprise impossible que la barriere se situe. D'ou ma question qui tiens toujours !

[invitec314d025]

Matthias, je parle bien evidement de tres grands nombres premiers. Celui découvert cette année et qui comporte 7 millions de chiffres a fait dire a certains que ca tendait a affaiblir la securité.

Je ne crois pas qu'on utilise d'aussi grands nombres pour le cryptage.

Quand a ce livre de 70000 pages dont tu parles, il s'agit de nombres premiers que tout le monde peux trouver en quelques jours de calculs.

Non, c'est le code d'un programme de cryptage.

Evidement, ca demande certainement des annees de calculs pour en trouver toute une liste sur un ordi domestique et c'est sur cette gigantesque entreprise impossible que la barriere se situe. D'ou ma question qui tiens toujours !

La réponse est toujours la même, aucune loi n'interdit la publication de nombres premiers quels qu'ils soient.

[SPH]

La réponse est toujours la même, aucune loi n'interdit la publication de nombres premiers quels qu'ils soient.

Curieux, mais ok, si tu le dis, j'ai ma reponse.

[invitec314d025]

Ca ne signifie pas que s'il suffisait de publier une liste de nombres premiers pour casser les algos de cryptage et que tu t'amuses à le faire avec le but clair d'aider les gens à casser les algos, on te laisserait faire. Mais c'est plutôt le but visé qui serait condamnable. Tout est question d'interprétation. Mais après il faudrait demander à un juriste.

[invitedebe236f]

calcule combient il y a de nombre premier < 10²⁰⁰ et la place necessaire a garder tous ca sur un disque dur

de plus il restera toujours n division a faire et c est la le hic c est pas faisable meme en 50 siecle

[SPH]

oui oui, je comprend bien votre raisonnement et il est totalement justifié. Mais comment expliquer qu'un nombre premier de X million de chiffres puisse affaiblir la cryptosecurité ??

ps: debut le debut, j'entendais par "cryptographie" les systemes militaires et gouvernementaux utilisant du matos autrement plus puissant que le nôtre.

ps2 : a cricri : je te parie que je met meme pas une semaine a te donner la liste de tous les NP de moins de 2000 chiffres

[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]

pour leg il commence par 0 parce que j ecrit des bloc de 3 chiffres
donc on efface les premiers 0

exact surement il fini par 6 ca c est sur si la fft qui un calcul aproximatif n ai pas dans ces limites c est correct
je regarderais ce soir

[invite3d7be5ae]

Pour calculer 2^2^x, on prend 2, on le met au carré x fois.
Sinon on fait des décalages : on prend 2, (10)₂ il y a donc 1 zéro, après on en met 2*1 zéros->4(100)₂, puis on double le nombre de zéros à chaque fois.

Ces opérations sont très rapides.

Pour multiplier, c'est plus dur (Karatsuba) :

On coupe nos deux nombres en deux parties : pour le premier en a et b, pour le deuxième en c et d.
k=nombres de chiffre d'un des deux nombres
Et après on calcule ac-((a-b)*(c-d)-ac-bd)*10^k+bd*10^(2*k).
On a le résultat (a+b*10^k)*(c+d*10^k).

Exemple :

Nos deux nombres sont 13 et 49 :
a=3, b=1,
c=9, d=4
k=1

ac=27
bd=4

27-(2*5-27-4)*10+4*100=
27-(-210)+400=
237+400=
637

Résultat : trois muliplications 3 soustractions et 1 addition.
On utilisant cette méthode pour caluler ac,bd,(a-b)*(c-d) on arrive à
une complexité en O(n^1.58) au lieu de O(n^2) pour la multiplication "normale"

[SPH]

ok pour tes 2 exemple pole. Mais je ne comprend pas l"exemple du 2^2^x.
Moi, je faisait :
2*2=4
4*4=16
16*16=256
etc
mais c'est long.
Toi, tu fais comment ?????
Detailles pour voir. thx

[invitedebe236f]

pour leg l erreur max est de 0.002 donc pour moi c est bon

pour sph
http://craftac2.free.fr/mult.xls
asser simple a comprendre tu peux multiplier 5 millions de chifffres par 5 autre sans probleme

[invite3d7be5ae]

Si tu travailles en base 10, c'est cuit : change en base 2.
Sinon, c'est simple.
J'imagine que tu travailles avec des tableaux de petits nombres dans une certaine base.
Par exemple pour mettre 18 dans tes tableaux tu fais tab[0]=8, tab[1]=1, le reste 0.
Pour la base 2, 18=(10010)₂. donc tab[0]=0, tab[1]=1,tab[2]=0,tab[3]=0 et tab[4]=1.
Donc pour décaler tu fais : tab[i]=tab[i-1] pour i<=0<=5.
Tu as décalés ton nombre d'un rang (=multiplié par deux).
Exemple en base 2:
10,on décale de 1
100," 2
10000,"4
100000000,"8
1000000000000000,"16.

etc...

[leg]

bonjour a tous.
sph est que ton programme permet de calculer exactement le nombre de premiers jusqu'à N par ex : mille milliards rapidement
or si on fait N/lN ; pour N= 100 resulta 21,N=1027 res :148 au lieu de 170 +2,3 et 5
quelqu'un à t'il un prog pour calculer le nombre de Premiers jusqu'a N
le mien va jusqu'a 500 mds .
mais en utilisant une constante, je me suis aperçus que la valeur approximative du nombre de premier ..N est oscillatoire par rapport au nombre reel Pi(n), mais plus précise que la fonction Pi(N) ; N/ par le log naturel de N si je ne me trompe pas et cette fonction a été améliorée tel que N/ln-1 "je n'ai pas verifié".
la constante que j'utilise et comprise entre (phi - 1) , et (2 pi)/10ce qui me donne dans l'E.p(30){2.3.5};come résultat pour 2^10,+ ou - 3 = 1027, 164 au lieu de 169,

2^16 +1 = 65537; 6912 au lieu de 6541

2^17 -1 =131071 ; 12171 au lieu de 12248
soit un peu plus ou un peu moins par rapport au nbr exact de premiers jusqu'a N ce qui donne une droite = Pi(n) et une courbe oscillatoire sur cette droite mais s'en trop s'écarter pour l'instant..
qu'en est-il des résultats que vous avez par ex: jusqu'a 10^19; 20 ; 21; 22; 23..
Pi(N) = combien
fonction Pi(n) ou autre = combien ? ou jusqu'aux valeurs que j'ai indiquées par comparaison..merci A+

[SPH]

SPH, est-ce que ton programme permet de calculer exactement le nombre de premiers jusqu'à N par ex : mille milliards rapidement
Quelqu'un à t'il un prog pour calculer le nombre de Premiers jusqu'a N
le mien va jusqu'a 500 mds.

Alors,je te répond. Oui, mon code permet de savoir combien de NP existe entre 0 et X. Il peut me le dire mais ce n'est pas "instantané". Cependant, c'est tres tres rapide, style 5 ou 10 secondes pour X=100 millions

Mon code allait jusqu'a 2 milliards (X=2 milliards). Mais pendant que mon ordi recalcule un nombre dont j'ai besoin, j'ai etablis une technique qui permet d'aller jusqu'a saturation d'un diskdur !! (tout en considerant n'importe quel NP comme un simple bit !!!!)
Par contre, ma technique non "instantanée" demande peut etre 24H pour un X tres tres tres grand (mais ca vaux le coup)

[leg]

sph pour te donner une indication il faut savoir a) que mon résultat jusqu'à X= 2 milliards c'est 2 segondes
b)cela n'a aucune importance dans l'imédiat, si il tu es capable par la suite de les dénombrer jusqu'à X = 10^25.26.27 par ex avec un pc de 2 giga de ram en quelque jours...
c) avec un résultat exact + ou - 1!
d) ton program permet ' il de localiser les facteurs P suceptible de factoriser Mn j'entend par là de définir leur congruence par ex Mn est congru 7(30), un des 4 facteur A est congrue x(30) et B y(30) on va dire si X ets congru 7(30), alors y est congru 31 (30) Mn n'est pas premier!.. merci !

[leg]

sph : pour le nombre tu peux déja comparer par tranche de 90 milliards sur l'autre fil:
nombre premier ennimax page 2 post 22! bien sur il faut décompter les trois premiers 2, 3 et 5 dans ton résultat si tu en tiens compte.
A +.

[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.

[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