Expected collisions for perfect 32bit crc

probability crc crc32 probability-theory
Tristan picture Tristan · Sep 9, 2010 · Viewed 15.4k times · Source

I'm trying to determine how my crc compares to an "ideal" 32bit crc.

So I ran my crc over 1 million completely random samples of data and collected the amount of collisions, I want to compare this number to the number of collisions I could expect from the "ideal" crc.

Does anyone know how to calculate the expected collision for an "ideal" 32bit crc?

Answer

srking picture srking · Oct 27, 2010

Compare your own CRC with 0x1EDC6F41 as your "ideal" reference.

Having said that, there is no ideal 32-bit CRC. Different polynomials have different collision characteristics depending on the length of data hashed. However, a paper by Castagnoli in 1993 found what is considered the best 32-bit CRC value over the broadest range of data lengths, which is 0x1EDC6F41. This polynomial is used by some network protocols like iSCSI and also the x86 CRC32 instruction.

Related questions

Probability of collision when using a 32 bit hash

I have a 10 character string key field in a database. I've used CRC32 to hash this field but I'm worry about duplicates. Could somebody show me the probability of collision in this situation? p.s. my string field is unique …

Read More
How to calculate mean, median, mode and range from a set of numbers

Are there any functions (as part of a math library) which will calculate mean, median, mode and range from a set of numbers.

Read More
Find the similarity metric between two strings

How do I get the probability of a string being similar to another string in Python? I want to get a decimal value like 0.9 (meaning 90%) etc. Preferably with standard Python and library. e.g. similar("Apple","Appel") #would have a …

Read More