[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: [email protected]*Subject*: Probability calculations*From*: [email protected] (Damien Doligez)*Date*: Tue, 29 Aug 95 14:03:08 +0200*Sender*: [email protected]

>From: Scott Brickner <[email protected]> >% k-space random sequential percent >searched method method difference [...] >99.9 115892899 16760439 591 But you fail to take into account the probability that the search will have to go that far. This is how I compute the expected cost of the random search. The probability of finding the key upon searching the k-th segment is: k-1 p(k) = (1 - 1/n) . 1/n The expected cost is the sum of all possible costs, weighted by their probability: ___ ___ \ \ i-1 e = > i p(i) = 1/n > i (1 - 1/n) /__ /__ i = 1..oo i = 1..oo ___ ___ \ \ i-1 = 1/n > > (1 - 1/n) /__ /__ i = 1..oo j = 1..i ___ \ i-1 = 1/n > (1 - 1/n) /__ {(i,j) | 1 <= j <= i} ___ ___ \ \ i-1 = 1/n > > (1 - 1/n) /__ /__ j = 1..oo i = j..oo ___ ___ \ j-1 \ i = 1/n > (1 - 1/n) . > (1 - 1/n) /__ /__ j = 1..oo i = 0..oo \_______________/ \_______________/ n n e = n This means that if you do many random searches (with a good RNG), the average cost of one search must be n. Any errors in the above ? -- Damien

- Prev by Date:
**Re: SSL trouble** - Next by Date:
**Joel's RSA-t's** - Prev by thread:
**TLA Menu!** - Next by thread:
**Claiming chunks of keyspace...** - Index(es):