Erwartete Kollisionen für perfekten 32bit crc

Question

Ich versuche, um zu bestimmen, wie mein crc im Vergleich zu einem " ideal " 32-Bit-CRC.

So lief ich meine crc über 1 Millionen vollständig Stichproben von Daten und gesammelt, um die Menge an Kollisionen, mag ich diese Zahl auf die Anzahl der Kollisionen vergleichen ich aus dem „ ideal “ crc erwarten könnte .

Wer weiß, wie die erwartete Kollision für ein " ideal " berechnen 32bit crc?

Answer 1

Das erklärt schön das „Geburtstags-Problem“ und alles über die Kollisionswahrscheinlichkeit vorhersagen CRC32 Hash Kollisionswahrscheinlichkeit

Answer 2

Vergleichen Sie Ihre eigenen CRC mit 0x1EDC6F41 als "ideal" Referenz.

Having said that, gibt es keine idealen 32-Bit-CRC. Verschiedene Polynome haben unterschiedliche Kollisionseigenschaften in Abhängigkeit von der Länge der Daten gehasht. Jedoch fand ein Papier von Castagnoli 1993, was als der besten 32-Bit-CRC-Wert über das breiteste Spektrum an Datenlängen, die 0x1EDC6F41 ist. Dieses Polynom wird von einigen Netzwerkprotokollen wie iSCSI und auch die x86-CRC32 Anweisung.

verwendet