Something I've been thinking about: it's entirely possible such an
identity doesn't even exist.
Imagine a hashing algorithm that takes a two bit input and returns a
two bit output. That is, the domain and range is {0, 1, 2, 3}. If the
algorithm perfectly distributes its hashes over the range then, for
each input value, there's a 0.25 probability of it being an identity.
So, the probability of no identity being produced by the hash function
over any of its domain is (0.75 ^ 4) = 0.32; about a one in three
chance.
MD5 has a range of 2 ^ 128. For finding the identity, the domain must
be the same as a range. So, there's a 1 in 2 ^ 128 chance of a random
input being the identity. The probability of an input not being an
identity is ((2 ^ 128) - 1 / (2 ^ 128)). And the probability of there
not being any Kember Identity at all is ((2 ^ 128) - 1 / (2 ^ 128)) ^
(2 ^ 128).
Which, according to some quick mpmath (http://pastebin.com/f484aa9f), is:
0.3678794411714423215955237701614608674452705807756669713837115293233486842268612093790091730736201865...
So, there's a decent chance that there is no Kember identity. Good to
know if you're considering starting to churn away on the problem.
Anyone see any obvious problems with my math?
Regards,
Dom
On Fri, May 8, 2009 at 6:47 AM, Elliott Kember <[email protected]> wrote:
>
> Hey guys,
>
> It's been a while since I've posted on here since I'm living in the UK
> now, but I thought I'd tell you all about a project I've started. It's
> the search for the "Kember Identity"; a string which, when MD5 hashed,
> returns itself - such that md5(x) == x.
>
> The project is at
> http://www.elliottkember.com/kember_identity.html
>
> And all the code is at
> http://github.com/elliottkember/The-Kember-Identity/tree/master
>
> I've put US$100 towards the prize pool. I don't really expect anybody
> to pay - hacking together some perl seems to be easier than paying to
> enter. The chances of someone finding it are so slim that my money's
> fairly safe. So best of luck - it might only take a few hundred
> million years!
>
> Thanks,
> Elliott
>
> >
>
--~--~---------~--~----~------------~-------~--~----~
NZ PHP Users Group: http://groups.google.com/group/nzphpug
To post, send email to [email protected]
To unsubscribe, send email to
[email protected]
-~----------~----~----~----~------~----~------~--~---
