On 20 Sie, 16:41, "prorok" <p...@t...nie.adres> wrote:
> Użytkownik "hubert depesz lubaczewski" <d...@d...com> napisał w
> wiadomościnews:7e92k7-ffc.ln1@depesz.com...
>
> > nie za bardzo chce mi się liczyć dla 50%, ale 40% prawdopodobieństwo
> > jest przy 2^64 plików.
>
> Skąd taka mała ilość? Przypuszczałbym że skoro dla dwóch plików jest rzędu
> 1/2^128 to prawdopodobieństwo 50% byłoby jeśli nie dla ilości 2^128, to
> przynajmniej 2^127, skąd nagle wychodzi spierwiastkowana liczba?

No wasnei, nie chcemy uniknac tego, ze ostatni md5 nie powtarza
sie z innymi, ale, ze zadne dwie sumy nie sa takie same.

http://pl.wikipedia.org/wiki/Paradoks_dnia_urodzin

Jakie jest prawdopodobienstwo, ze n probkach kazda trafi
w inna liczbe. niech m = 2^128.

Pierwsza moze byc dowolna, 1. Druga moze przyjac wartosc
dowolna poza juz przybrana, trzecia - poza dwoma juz zajetymi
wiec (1-1/m) i (1-2/m)

Lacznie p=iloczyn_{i=1..n} ( 1 - i/m )

liczenie na piechote zajeloby troche komputerowi,
wiec trzeba kombinować. Zalozmy ze n<<m.

Nazwijmy nasza wielkosc przez p i zlogarytmujmy,
oraz skorzystajmy z log(1+x)=x (tu przydatne zalozenie)

log p = - (1/m + 2/m + ...+ n/m) = - [n(n+1)/m]/ m=~= -n^2/(2m)

p=exp(-n^2/2m)

Nasz interesuje prawdopodobienstwo, ze wystapi co najmniej
jedna kolizja, czyli 1-p

1-exp (-n^2/2m) = a. a=1/2, 1/10, 1/100

exp(-n^2/2m) = 1-a
n=sqrt( -2m*log(1-a) )

a=1/2, n= 2.17e19 [hmm, mniej niz obok podawane, moze sie
gdzies kopnalem, moze juz przyblizenie za grube]
a=1/10 n=8e18
1/100 n= 2e18

dla malych a mozna uzyc [modulo ewentualny blad w rachunkach]
n=sqrt( 2m*a ) = 2.6e19 *sqrt(a)

pozdrawiam
bartekltg