Cooperation

Jeff Simmons (jsimmons@goblin.punk.net)
Fri, 2 May 1997 20:30:48 -0700 (PDT)


Here's a little thought experiment for you.

Imagine there are 100 keys. I pick 25 at random, you pick 25 at random.
So together we've picked 50. We're half way through the keyspace, and
together we have a 50% chance of having found the right key.

Wrong of course. Since I've covered 25% of the keyspace, each of your
choices has a 25% chance of being one of the keys I've already picked.
So the number of dual-picked keys, on average will be 25% of 25, or
6.25 duplicates.

So together we've only searched 43.75 unique keys. We have to search 6.25 more
keys together, or 3.125 each. Now the odds of picking identical keys are
slightly higher, say 30% (way too high, but it's a thought experiment).
So say we have to search 4 more keys each to get to 50 unique, counting
duplicates.

So on average, if I pick 29 keys and you pick 29 keys, we'll have each have
picked 21 unique keys, and 8 that were duplicated. Total searched - 58.
Total unique - 50. 58/50 = 1.16 *ON AVERAGE* this is the penalty for
not cooperating.

The serious math to get the exact number is left as an exercise for the
student.

-- 
Jeff Simmons					jsimmons@goblin.punk.net

Hey, man, got any spare CPU cycles? Help crack DES. http://www.frii.com/~rcv/deschall.htm