Erwartete Kollisionen für perfekten 32bit crc
-
01-10-2019 - |
Frage
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?
Lösung 2
Das erklärt schön das „Geburtstags-Problem“ und alles über die Kollisionswahrscheinlichkeit vorhersagen CRC32 Hash Kollisionswahrscheinlichkeit
Andere Tipps
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