2
$\begingroup$

I have two numbers:

3032643431333337636238613038343231383364303731376566303037663231

3861663464383131656131653461343961343364303737663565356561653361

36430373 repeats from digit 36-45 (I only extracted the 8, but the 9th matched too).

What are the chances that the same 8 digits would repeat in two 65 digit length numbers? What are the chances that the same 9 digits would repeat in two 65 digit length numbers?

Minor Details: I extracted 8 digits from a hash(md5) that was converted to a binary string and then hex encoded to get the 65 digits. I found the collision and was curious as to the odds.

Thanks

Edit: As was commented, the digits must be between the 36th and 45th position. Not elsewhere in the number.

$\endgroup$
  • $\begingroup$ In response to your edit: note there are $10$ digits in the $36$ through $45$ places. I presume you mean the $8$ digits to be $36$ through $43$. In that case, the $10^{-8}$ of the two answers applies. $\endgroup$ – Ross Millikan Oct 24 '14 at 2:32
1
$\begingroup$

If you want them to be in a specific set of places, the chance of a match starting at a given place is $10^{-8}$ for $8$ digits and $10^{-9}$ for $9$ digits. Assuming independence and ignoring the chance of two matches (both excellent approximations), there are $58$ places an $8$ digit run can start, so the chance of an $8$ digit match somewhere (but in the same places in both numbers) is $58 \cdot 10^{-8}$ If you want any pair of $8$ continuous digits to match (not necessarily the same places in both numbers) you have $58^2$ pairs of runs, so approximately $58^2 \cdot 10^{-8}=3.364\cdot 10^{-5}$ chance of a match somewhere.

$\endgroup$
0
$\begingroup$

If "repeats" means also "on the same places", as it is suggested by your example, it is simply a chance of taking a fixed 8-digit number, because the other digits are arbitrary. Hence the probability is $10^{-8}$.

You are lucky or your numbers are not uniformly distributed. :-)

$\endgroup$
  • $\begingroup$ That would be the correct answer if the places are specified, e.g., they must be in places $36$ to $45$. But I don't think that's what the OP means. $\endgroup$ – David Oct 24 '14 at 1:19
  • $\begingroup$ @David Let us think that the ciphers are on the ring... $\endgroup$ – Przemysław Scherwentke Oct 24 '14 at 1:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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