collisions prévues pour crc 32bit parfait

Question

Je suis en train de déterminer comment mon crc se compare à un " idéal " 32bit crc.

Alors je courais mon crc plus de 1 million d'échantillons complètement aléatoires de données et recueilli le nombre de collisions, je veux comparer ce nombre au nombre de collisions que je pouvais attendre de la « idéal » crc .

Quelqu'un sait comment calculer la collision attendue pour un " idéal " 32bit crc?

Answer 1

Ceci explique admirablement le « problème anniversaire » et tout au sujet de prédire la probabilité de collision CRC32 Hash Collision Probabilité

Answer 2

Comparez votre propre CRC avec 0x1EDC6F41 comme référence "idéale".

Cela dit, il n'y a pas idéal CRC 32 bits. Différents polynômes ont des caractéristiques différentes de collision en fonction de la longueur des données hachurées. Cependant, un document par Castagnoli en 1993 trouvé ce qui est considéré comme la meilleure valeur CRC 32 bits sur la gamme la plus large de longueurs de données, qui est 0x1EDC6F41. Ce polynôme est utilisé par certains protocoles réseau comme iSCSI et aussi l'instruction x86 CRC32.