Ожидаемые столкновения для идеального 32-битного CRC

Question

Я пытаюсь определить, как мой CRC сравнивается с «идеал«32-битный CRC.

Поэтому я провел свой CRC более 1 миллионами совершенно случайными образцами данных и собрал количество столкновений, я хочу сравнить этот номер для количества столкновений, которые я мог ожидать от «идеал"CRC.

Кто-нибудь знает, как рассчитать ожидаемое столкновение для «идеал"32-битный CRC?

Answer 1

Это прекрасно объясняет «проблему на день рождения» и все о предсказании вероятности столкновения Вероятность столкновения хэш CRC32

Answer 2

Сравните свой собственный CRC с 0x1EDC6F41 в качестве «идеальной» ссылки.

Сказав это, нет идеального 32-битного CRC. Различные полиномы имеют разные характеристики столкновения в зависимости от длины хешированных данных. Тем не менее, бумага Castagnoli в 1993 году обнаружила, что считается лучшим 32-битным значением CRC по сравнению с широком диапазоном длин данных, что составляет 0x1EDC6F41. Этот полиномиал используется некоторыми сетевыми протоколами, такими как ISCSI, а также инструкция X86 CRC32.