CODEWITHSUNDEEP
collision-detectioncrc32
testing111
testing111

Reputation: 1

What is probability of collision in CRC32 in first 4.2Billion

I am using numbers as input and length will be 10 characters.

EG. Input - 8429294732 Output - 96325be7

Total possibility of crc32 is 16^8 which is roughly 4.2Billion.

Does anyone know what is chance of collision here?

And can you please explain.

Upvotes: 0

Views: 1130

Answers (2)

Mark Adler
Mark Adler

Reputation: 112547

See this answer.

Assuming you mean ten decimal digits of uniform, independent probability, then your inputs will result in on the order of 90% coverage of the possible 32-bit CRC values. We will use the formula with n = 0.9 232, and from the question title I will presume, k = 232. You will have about two billion collisions. If the inputs are chosen randomly, the chance of not having a collision is about 10-1036266998. Also known in practical terms as: zero.

(By the way, your "roughly 4.2 billion", should be roughly 4.3 billion.)

Upvotes: 1

guga
guga

Reputation: 724

Assuming your input uses the full range of the 10 digits, that would give you 10^10 different numbers, and you map this to 16^8=2^32 numbers generated by the CRC32. So, on average, you have (10^10)/(2^32)=2.3 numbers mapped to every possible CRC32 value generated. So, the answer to your question is that you have 100% chance of collision.

Upvotes: 0

Related Questions