Timeline for Why is the brute force search time for hashing algorithms 2^(num_bits / 2)?
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 8, 2014 at 21:53 | answer | added | Thomas Pornin | timeline score: 2 | |
| Oct 9, 2014 at 22:45 | comment | added | Stephen Touset | Birthday paradox. It's (2^n)/2 = 2^(n-1) to find a collision for a specific output in the average case, but it's (2^n)^(1/2) = 2^(n/2) operations on average to find some collision. By the time you've generated 2^(n/2) outputs, odds are better than even that some pair of them are identical. | |
| Sep 9, 2014 at 19:49 | comment | added | RoraΖ | Right, it's Tuesday so I guess I can't do math | |
| Sep 9, 2014 at 19:47 | answer | added | David | timeline score: 0 | |
| Sep 9, 2014 at 19:47 | comment | added | gsgx | (2^n)/2 is 2^(n-1), right? | |
| Sep 9, 2014 at 19:45 | comment | added | RoraΖ | The worst case is 2^N, the average time is half that. | |
| Sep 9, 2014 at 19:38 | history | asked | gsgx | CC BY-SA 3.0 |