Expected collisions for perfect 32bit crc

StackOverflow https://stackoverflow.com/questions/3675728

Question

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?

Was it helpful?

Solution 2

This explains beautifully the "Birthday Problem" and all about predicting the collision probability CRC32 Hash Collision Probability

OTHER TIPS

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.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top