probability - 完全な 32 ビット CRC で予想される衝突

Question

私のcrcが「理想的な」32ビットcrcとどのように比較されるかを判断しようとしています.

そのため、100 万回の完全にランダムなデータ サンプルで CRC を実行し、衝突の量を収集しました。この数を、「理想的な」CRC から期待できる衝突の数と比較したいと思います。

「理想的な」32ビットcrcの予想される衝突を計算する方法を知っている人はいますか?

Answer 1

「理想的な」参照として、独自の CRC を 0x1EDC6F41 と比較します。

そうは言っても、理想的な 32 ビット CRC はありません。異なる多項式は、ハッシュされるデータの長さに応じて異なる衝突特性を持ちます。ただし、1993 年の Castagnoli による論文では、データ長の最も広い範囲で最適な 32 ビット CRC 値と見なされる値 (0x1EDC6F41) が見つかりました。この多項式は、iSCSI や x86 CRC32 命令などの一部のネットワーク プロトコルで使用されます。

Answer 2

これは、「誕生日の問題」と、衝突確率CRC32ハッシュ衝突確率の予測に関するすべてを美しく説明しています。