Ожидаемые столкновения для идеальной 32-битной CRC
Я пытаюсь определить, как мой CRC сравнивается с "идеальным" 32-битным CRC.
Итак, я запустил свой crc более 1 миллиона полностью случайных выборок данных и собрал количество столкновений, я хочу сравнить это число с количеством столкновений, которое я мог бы ожидать от "идеального" crc.
Кто-нибудь знает, как рассчитать ожидаемое столкновение для "идеальной" 32-битной CRC?
2 ответа
Это прекрасно объясняет "проблему дня рождения" и все о предсказании вероятности столкновения CRC32 Hash Collision Вероятность
Сравните ваш собственный CRC с 0x1EDC6F41 в качестве "идеального" эталона.
Сказав это, нет идеального 32-битного CRC. Различные полиномы имеют разные характеристики столкновения в зависимости от длины хешируемых данных. Однако в работе Кастаньоли в 1993 году было обнаружено, что считается лучшим 32-битным значением CRC в самом широком диапазоне длин данных, который равен 0x1EDC6F41. Этот полином используется некоторыми сетевыми протоколами, такими как iSCSI, а также инструкцией x86 CRC32.