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

[invite4793db90]

Je cherche a faire 2^2^25. Qui pourrais me filer ce nombre ?

Salut,

ici, zippé, 4.8Mo.
-----

[SPH]

Désolé je ne l'ai pas sous la main, mais (juste pour être sur) tu as conscience que le nombre de Mersenne M2^25=2^2^25-1 ne peut pas être un nombre premier ?

Bien sur

Aucun nombre de format 2^2^n (avec n>=2) ne peux etre un NP de mersenne car ils finissent TOUS par 6. Et quand on enleve 1, ils sont éliminés par le NP 5

[SPH]

Salut,

ici, zippé, 4.8Mo.

Merci beaucoup. D'ailleur, qui a le lien pour downloader le programme qui donne ce genre de nombre ??
Merci

[erik]

tu peux trouver un programme qui s'appelle bc ici http://gnuwin32.sourceforge.net/packages/bc.htm (telecharge le "Complete package, except sources")
ça paye pas de mine (ligne de commande sous dos) mais ça devrais pouvoir t'aider.
(pour que le résultat de tes calculs apparaissent dans un fichier et non à l'écran pense à rediriger la sortie quand tu lance bc : bc>resultats.txt)

[invitedebe236f]

personne n a reussi a faire tourner mon programme ?
il donne 2 2 25 en 12s
2 2 26 en 25 s
2 2 27 en 52s
apres il declare forfait plus de memoire

[Le_boulet]

tu peux trouver un programme qui s'appelle bc ici http://gnuwin32.sourceforge.net/packages/bc.htm (telecharge le "Complete package, except sources")
ça paye pas de mine (ligne de commande sous dos) mais ça devrais pouvoir t'aider.
(pour que le résultat de tes calculs apparaissent dans un fichier et non à l'écran pense à rediriger la sortie quand tu lance bc : bc>resultats.txt)

Ah oui, bc est un excellent langage pour manipuler les grands nombres. C'est directement issu du monde linux.

SPH, tu devrais profiter de ce que tu es en train de faire pour affiner la constante de Brun:

http://fr.wikipedia.org/wiki/Constante_de_Brun

C'est un peu ce qu'avait évoqué Martini-bird

[SPH]

@cricri
Non, je n'ai pas reussi a faire tourner ton programme. Dommage d'ailleur. Pour info, ton programme qui fait 2^2^25 en 12 secondes, moi, je le faisait en 57 heures !!!!
Alors, j'ai beaucoup a apprendre sur ta technique !!

@le_boulet
Je vais lire ton lien avec grande attention.

[SPH]

Ok, j'ai lu les articles sur la constante de brun et autres.
Mais je m'adresse a cricri :
comment decris tu le processus utilisé par ton programme pour calculer 2^2^25 ? Decris un peu, ca m'interesse.

Egalement, je demande a martini bird si le nombre zippé qu'il a mis en telechargement est fiable a 100% (je dis cela car apres avoir lu les articles, il m'a semblé qu'il pouvait y avoir une erreur infime de calcul) ?

[invite4793db90]

Egalement, je demande a martini bird si le nombre zippé qu'il a mis en telechargement est fiable a 100% (je dis cela car apres avoir lu les articles, il m'a semblé qu'il pouvait y avoir une erreur infime de calcul) ?

Evidemment, on est jamais à l'abri du rayon cosmique qui vient altérer le calcul de la machine.

Le mieux est de comparer en faisant plusieurs* calculs sur des plate-forme différentes.

Cordialement.

*A moins d'être parano, deux devraient suffire.

[SPH]

*A moins d'être parano, deux devraient suffire.

Alors, je vais faire le test sur 4 machines
PS: tu peux me donner le lien de telechargement de ton programme ?

[leg]

bonjour à tous ; le boulet
SPH, tu devrais profiter de ce que tu es en train de faire pour affiner la constante de Brun:
le problème est infini, il faudra toujours l'affiner aussi bien celle d'Euler que Brun, B , B2 ou B4 et pourquoi pas B6 celle ci: (les sextuplés de premiers jumeaux; 1/11+1/13 +1/17+1/19 +1/29+1/31) + ...
et peut être même qu'un jour on s'approchera du nombre d'or "phi" - 1 = 0,618033.. pour calculer la répartition de ces nombres car dans l' Ensemble P(30) on oscille autour... A +

[leg]

j'avais oublié de dire la cause : la coube du nombre de premiers est oscillatoire par rapport à zéro lorsque N tend vers l'infini...

[Le_boulet]

Je suis d'accord.

Mais ce sont des séries convergentes. Donc qui donnent bien des constantes. Et dont nous ne connaissont simplement pas toutes les décimales (et pour cause, on ne pourra que s'en approcher).

Mais c'est quand-même fascinant de savoir que d'une suite de nombres comme les premiers dont nous n'arrivons même pas à tirer une loi exacte, et bien il en sort des constantes fixes, tout comme Pi.

Je me plais à penser qu'un jour, on découvrira que les constantes de Brun interviennent dans d'autres lois mathématiques (ou physiques)qui n'auront a priori rien à voir avec la répartition des NP.

Bon, je rêve un peu, peut-être !

(désolé pour le léger hors-sujet)

[invitedebe236f]

j ai verifier les premier et dernier chiffre de son calcul je trouve pareil
c est bon signe

multiplication a la main 9*9 1 operation
99*99 4 operation
9999*9999 16 operation etc
2*2=4
4*4=16
16*16=256 etc jusqua 2^{2 25} ca donne un nombre astronomique d operation

intervient la FFT fast fourier transformation

qui est capable de multiplier un nombre de n chiffre par un autre nombre de n'(quasi egale a n) chiffre en gros en n*ln(n) operation au lieu de n²
et la du coup on tombe a 12s

mon programme n est qu une fft qui pars de 2⁶⁴ et qui le multplie x fois par lui meme pour arriver au resultat

[leg]

le boulet : à la différence de pi , ces constantes ne sont que de vague estimation
en ex prend M42 avec la constante de B l'erreur sur le nombre de P sera énorme par rapport à la circonférence en disant que le diametre = M42.
pour revenir au nombre P la deuxième série des 6 P jumeaux est :
(1/18041+1/18043+1/18047+1/18049+1/18059+1/18061)..B6 =..je ne sais pas.

[invite3d7be5ae]

Au lieu de faire la FFT, fais plutôt la multiplication avec la méthode de Karatsuba. A mon avis, elle va accellerer ton programme (et de beaucoup).

[invitedebe236f]

bon puisque personne n arrive a excecuter mon programme

je livre le source du code dans un fichier excel il est executable tel quel avec excel
evidament il est un peu plus lent c est de l interpreter pas du compile

http://craftac2.free.fr/puis.xls

[SPH]

Petit résumé pour le modo :

Ce post, je l'ai voulu et on m'a assez vite répondu que les grands NP influencent moins la sécurité que le cassage de la facon de chiffrer. Ca c'est ok.
Maintenant, le fil a tourné avec le vent mais on parle encore néanmoins de NP. On parle aussi d'une assistance informatique et de méthodes de calculs de grands nombres comme les puissances de 2.
Je tenais a dire cela pour ne pas que martini bird s'inquiete outre mesure.
On est la pour parler des NP et de tout ce qui y touche alors, déballons gaiement nos sacs a dos.

Bon, pour le nombre 2^2^25 que j'ai demandé, il va en effet me servir de point de repair car autant les nombres comme 50, 2480 ou meme 500000 sont des nombres "concrets", autant les nombres de 10 millions de chiffres ne sont ni "palpables" ni prenoncables.
Quand au nombre que j'ai calculé l'autre fois (en 44 heures), il est actuellement a 9300000 chiffres. Mais il faut que je le monte le plus pret possible au 2^2^25. Alors, comme certains m'ont fait decouvrir une partie mathematique qui m'etait COMPLETEMENT inconnue, je pose une question pour ne pas me retaper un programme avec 10h de calculs :
mon nombre de 9300000 chiffres doit etre multiplié par des nombres a 9 chiffres. Alors, pour eviter l'overflow (>2,1 milliard), avez vous une methode pour effectuer la multiplication qui serait semblable a la methode pour trouver 2^2^x ?

[leg]

bonsoir cricri,
j'ai chargé ton executable pour faire un essai sur 2^2^20 en 3.57 segondes
le nom commence par 067411 ...et fini par 79136 mais pourquoi il commence par 0 ?

[leg]

cricri, je vient de calculer projet1 21 res 27, temps mis 61'' taille du fichier 40 mega le nombre commence par 001196380...fini par..6787456 est ce exact?
A+

[leg]

project1 20 res 26; temps mis 34'' début du nombre00109379 .... fin 13519616
j'ouvre les fichiers avec wpad
a+

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