Matematici, fatevi avanti

[absinthe]

Scusa MAT, ma sei sicuro di quella formula? Io dovrei rispolverare le nozioni di calcolo combinatorio, forse tu le hai più fresche. Se provi a calcolare il limite della formula per n che tende a infinito e supponi n>>k, usando l'approx di Stirling per il fattoriale, ti accorgi che è infinito. Da qui il numero molto grande trovato da absinthe, col quale mi scuso. Se è una probabilità dovresti trovare un numero tra 0 e 1.

macchè scusarsi e scusarsi: me lo hanno sempre detto. prima rifletti poi parti con i calcoli :P

ora capisco ancor di più perchè ho passato analisi uno solo al 4 o 5 tentativo... non ricordo più

M

[absinthe]

puo procedere cosi:
se ti interessa solo dire che P "e' grande" allora il problema mi sembra banale,

adoro quest'uomo!!!

ogni fattore moltiplicativo (compreso quello "piu piccolo" (n-k+1)/n) che compone P giace in un intorno sinistro di 1 di raggio infinitesimo.

tarapia tapicoca come se fosse antani????

dunque dunque...spetta che riavvio con win e matlab ihihih adoro spengere il cervello e far lavorare quel coso...

M

[elettronicha]

Non credo che nella tesi di laurea accettino una scommessa al posto di una dimostrazione matematica

Noi in questa tesi vogliamo vedere scritti tanto di ringraziamenti con nick, uno per uno.

[absinthe]

allora gente. matlab dice che:

2^160 = 1.5*10^48
2^30=10^9

ne vien fuori che

n-k = 1.5*10^48 - 10^9 approssimabile con 1.5* 10^48 = n

quindi secondo stirling.. facendo due calcolucci:

n!/(n-k)! * 1/n^k = sqrt( n/(n-k) ) * ( n/(n-k) )^(n-k) * e^(n-k)/e^n

utilizzando la semplificazione di cui sopra:

1 * 1 * 1 =1

OVVIAMENTE A MENO DI QUALCHE INFINITESIMO, OVVERO LA *tua* PROBABILITa' FINALMENTE TRASCURABILE !!!

se fossi un professore ma la accetterei

M

PS: e anche per stamani 2 ore le ho perse... w la voglia di lavorare ihihih

[MAT]

Direi che tale probabilità di collisione sia decisamente prossima allo zero. Il valore 2^30 non è nemmeno paragonabile a 2^160. Come scritto su http://en.wikipedia.org/wiki/Birthday_attack, se la probabilità è uniforme (ovvero la densità di probabilità è costante), allora occorrono in media circa 1.2*sqrt(n) tentativi prima di beccare due valori che, passati alla funzione hash, vengano mappati sulla stessa chiave.

[first]

se ti interessa solo dire che P "e' grande" allora il problema mi sembra banale, ogni fattore moltiplicativo (compreso quello "piu piccolo" (n-k+1)/n) che compone P giace in un intorno sinistro di 1 di raggio infinitesimo. Puoi cosi' scommetterci 100 euro che P e' "sicuramente" > di 0.9 e avresti ancora un gigantesco margine di errore. Per capirci P> [(n-k+1)/n]^k>(1-10^(-5))

Non credo che nella tesi di laurea accettino una scommessa al posto di una dimostrazione matematica

ehm...

Codice: Seleziona tutto

P> [(n-k+1)/n]^k>(1-10^(-5))

Questa e' una dimostrazione.
Pensavo di saltare i passi banali ( noi chiamavamo il nostro prof di geometria Canuto "banalman" fai te ) ma mi sa che mi devo de-Canutizzare..

(n-1)/n > (n-2)/n >... > (n-k+1)/n

quindi

P> (n-k+1)/n * (n-k+1)/n* ... * k volte = [(n-k+1)/n]^k

[(n-k+1)/n]^k =circa (1 - 10(^-5))^(10^9) che e' circa uguale a (1-10^(-5))

siccome non avevo voglia di calcolare 48/9 lo ho approssimato per difetto a 5, non credo che un aumento del grado di accuratezza possa farti guadagnare punti per la tua tesi ( di certo li avresti persi se nella tua tesi avessi calcolato effettivamente il risultato vero di P.....)

quod erat demostrandum ( e beccati pure la citazione latina )

P> [(n-k+1)/n]^k>(1-10^(-5))


PS io mi chiamo Diego e ti autorizzo a citarmi nella tua tesi

[elettronicha]

Ma hai studiato a Torino? Canuto non mi è nuovo come nome.

[MAT]

Hai ragione first, un minorante per quella probabilità si può trovare in quel modo, per cui si trova un maggiorante per il complemento a 1. Tuttavia
(n-1)/n*(n-2)/n*...*(n-k+1)/n viene fatto (k-1) volte, non k. Questo comunque non influisce sul risultato, dato che 1 è nulla rispetto a 10^9.

Dopo però c'è un errore più grossolano.
Arriviamo alla condizione

p > (1 - (k-1)/n)^(k-1)
che, per i valori di n (10^48 ) e k (10^9) che abbiamo si può ridurre a

p > (1 - 10^9/10^48 )^(10^9) = (1 - 10^(9-48 ))^(10^9) = (1 - 10^(-39))^(10^9)
che è un valore ancora più alto di quello indicato da te prima.

Posso inserire questo calcolo come dimostrazione, tuttavia faccio riferimento a risultati trovati da Bellare e Kohno e da Wang, Yin e Yu, che fanno riferimento proprio alla SHA-1. Questi ultimi hanno implementato un algoritmo che ha trovato una collisione dopo 2^69 tentativi.

[MAT]

Sviluppandolo in serie e arrestandosi al primo termine si ha

p > (1 - 10^(-39))^(10^9) ~ 1 - 10^9*10^(-39) = 1 - 10^(-30)

quindi la probabilità di collisione è 10^(-30), il che mi sembra piuttosto basso

Grazie a tutti!!

[first]

Hai ragione first, un minorante per quella probabilità si può trovare in quel modo, per cui si trova un maggiorante per il complemento a 1. Tuttavia
(n-1)/n*(n-2)/n*...*(n-k+1)/n viene fatto (k-1) volte, non k. Questo comunque non influisce sul risultato, dato che 1 è nulla rispetto a 10^9.

Dopo però c'è un errore più grossolano.
Arriviamo alla condizione

p > (1 - (k-1)/n)^(k-1)
che, per i valori di n (10^48 ) e k (10^9) che abbiamo si può ridurre a

p > (1 - 10^9/10^48 )^(10^9) = (1 - 10^(9-48 ))^(10^9) = (1 - 10^(-39))^(10^9)
che è un valore ancora più alto di quello indicato da te prima.

Posso inserire questo calcolo come dimostrazione, tuttavia faccio riferimento a risultati trovati da Bellare e Kohno e da Wang, Yin e Yu, che fanno riferimento proprio alla SHA-1. Questi ultimi hanno implementato un algoritmo che ha trovato una collisione dopo 2^69 tentativi.

hai ragione, nella divisione di potenze gli esponenti si sottraggono non si dividono, da qui l'errore (speriamo che Canuto non abbia letto! ) a mia scusante c'e' il tempo pari a 10^(-3) secondi con cui ho risposto.