Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I've a question that has been bothering me regarding combinatorial searches, such as brute force of a key for an encryption.

Lets say I have 2^32 keys in a key space that would need to all be calculated to get a 1:1 probability of guessing the correct key. Would on average 2^32/2+1 random key searches be required to find the correct key?

My memory is leaving me about the above and what is required.

share|improve this question
    
@Didier, this makes a lot of sense. Thank you. –  Ron Kiu Aug 20 '11 at 12:47

1 Answer 1

up vote 1 down vote accepted

The mean rank of a given element of an ordered set of n to which one applied a uniformly distributed permutation is (n+1)/2. In your case you need to examine 2^(31)+.5 keys on average.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.