On 25 Jan 2008 at 0:00, Dan Asimov wrote:
Oops, it has been kindly pointed out to me that Bernie's questions ,.. is about sampling *without* replacement, which I somehow managed to ... miss. Sorry about that. ] It isn't what I'm thinking about, but one way to see the question I'm asking is: you have M ciphers using the same ciphersystem with a keyspace of size N. If you have to brute-force the key, trying each test-case against each of the M ciphertexts in turn, how far on average do you have to through the keyspace to decode one of the messages? To decode all of them?
There might be an interesting asymptotic formula for E(k*M;k*N) as k -> oo.
(My guess, however, is that this just approaches the expectation for sampling ... *with* replacement, i.e., N/M.)
As I said, my guess is pretty much that. If you assume that the M 'targets' are uniformly distributed across the sample space, then you'd think it'd take about N/(M+1) probes before you run into the first one and N*M/(M+1) probes before you get all of 'em. /Bernie\ -- Bernie Cosell Fantasy Farm Fibers mailto:bernie@fantasyfarm.com Pearisburg, VA --> Too many people, too few sheep <--