17

Adler-32 チェックサム アルゴリズムは 65521 を法として合計します。65521 が 16 ビットに収まる最大の素数であることは知っていますが、このアルゴリズムで素数を使用することがなぜ重要なのですか?

(誰かが私に教えてくれれば答えは明らかだと確信していますが、私の脳の数論の部分は機能していません。チェックサム アルゴリズムの専門知識がなくても、http://en.wikipedia. org/wiki/Fletcher%27s_checksumでおそらく説明できます。)

4

6 に答える 6

4

Adler-32 アルゴリズムは計算することです

A = 1 + b1 + b2 + b3 + ...

と

B = (1 + b1) + (1 + b1 + b2) + (1 + b1 + b2 + b3) + ... = 1 + b1 + 2 * b2 + 3 * b3 + ...

そしてそれらをモジュロ m で報告します。m が素数の場合、m を法とする数値は、数学者が体と呼ぶものを形成します。フィールドには、任意の非ゼロ c に対して、c * a = c * b の場合にのみ a = b があるという便利なプロパティがあります。素数ではないモジュロ 6 のタイムズ テーブルを、次のモジュロ 5 のタイムズ テーブルと比較します。

* 0 1 2 3 4 5
0 0 0 0 0 0 0
1 0 1 2 3 4 5
2 0 2 4 0 2 4
3 0 3 0 3 0 3
4 0 4 2 0 4 2
5 0 5 4 3 2 1

* 0 1 2 3 4
0 0 0 0 0 0
1 0 1 2 3 4
2 0 2 4 1 3
3 0 3 1 4 2
4 0 4 3 2 1

ここで、2 バイトを交換するたびに A 部分がだまされます。つまり、足し算は交換可能です。B 部分はこの種のエラーを検出することになっていますが、m が素数でない場合、より多くの場所が脆弱になります。のアドラー チェックサム mod 6 を考えます。

1 3 2 0 0 4

A = 4 で B = 1 です。ここで、b2 と b4 を交換することを検討してください。

1 0 2 3 0 4

2 * 3 = 4 * 0 = 2 * 0 = 4 * 3 (モジュロ 6) であるため、A と B は変更されません。2 と 5 を交換して同じ効果を得ることもできます。これは、タイム テーブルがアンバランスな場合に発生する可能性が高くなります。モジュロ 5 では、これらの変更が検出されます。実際、素数モジュラスが単一のスワップを検出できないのは、m を法とする 2 つの等しいインデックスがスワップされた場合のみです (m が大きい場合、それらは大きく離れている必要があります!)。^ このロジックは交換された部分文字列にも適用できます。

小さいモジュラスを使用することの欠点は、ランダム データで失敗する可能性がわずかに高くなることです。ただし、現実の世界では、破損がランダムに発生することはめったにありません。

^ 証明: インデックス i と j を値 a と b で交換するとします。このとき、a i + b j = a j + b i なので、a i - a j + b j - b i = 0 であり、(a - b)*(i - j) = 0 です。体は整域なので、 a = b (値が合同) または i = j (インデックスが合同) となります。

編集: Unknown がリンクした Web サイト ( http://www.zlib.net/zlib_tech.html ) は、Adler-32 の設計がまったく原則に基づいていないことを明らかにしています。DEFLATE ストリームのハフマン コードにより、小さなエラーでもフレーミングが変更され (データに依存するため)、出力に大きなエラーが発生する可能性があります。この回答は、人々が特定のプロパティを素数に帰する理由の少し不自然な例と考えてください。

于 2009-06-09T03:39:57.783 に答える
3

短編小説：

素数のモジュロは最高のビットシャッフル特性を持っており、それがまさにハッシュ値に必要なものです。

于 2009-05-29T18:42:17.277 に答える
1

完全にランダムなデータの場合、バケットが多いほど良いです。

データが何らかの形で非ランダムであるとしましょう。非ランダム性がアルゴリズムに影響を与える唯一の方法は、一部のバケットが他のバケットよりも使用される可能性が高い状況を作り出すことです。

モジュロ数が素数でない場合、モジュロを構成する数値の 1 つに影響を与えるパターンは、ハッシュに影響を与える可能性があります。したがって、15 を使用している場合、3 または 5 ごと、および 15 ごとのパターンで衝突が発生する可能性がありますが、13 を使用している場合、衝突を引き起こすにはパターンが 13 ごとである必要があります。

65535 = 3*5*17*257 したがって、3 または 5 を含むパターンは、このモジュロを使用して衝突を引き起こす可能性があります。たとえば、何らかの理由で 3 の倍数がはるかに一般的である場合、3 の倍数であるバケットのみが有効に活用してください。

現実的に、これが問題になる可能性があるかどうかはわかりません。乱数ではなく、ハッシュしたいタイプの実際のデータとの衝突率を経験的に決定することをお勧めします。(たとえば、http://en.wikipedia.org/wiki/Benford's_law">ベンフォードの法則またはそのような不規則性を含む数値データは、このアルゴリズムに影響を与えるパターンを引き起こしますか?現実的なテキストに ASCII コードを使用するのはどうですか?)

于 2009-06-09T19:13:13.477 に答える
0

チェックサムは通常、2つのものが異なることを検出する目的で使用されます。特に、両方が同時に同じ場所で使用できない場合に使用されます。それらは、さまざまな場所（たとえば、送信された情報のパケットと受信された情報のパケット）、またはさまざまな時間（たとえば、保存されたときの情報のブロックと、読み戻されたときの情報のブロック）で利用できる可能性があります。 。場合によっては、あるデバイスから別のデバイスに実際のデータを送信することなく（たとえば、ロードされたコードイメージや構成を比較することなく）、2つの異なる場所に独立して保存されている2つのものが一致する可能性があるかどうかを確認することが望ましい場合があります。

比較されているものが一致しない唯一の理由がそれらの1つのランダムな破損である場合、Adler-32チェックサムに素数係数を使用することはおそらく特に役に立ちません。ただし、いずれかの項目に「意図的な」変更が加えられた可能性がある場合は、非プライム係数を使用すると、特定の変更が見過ごされる可能性があります。たとえば、バイトを00からFFに変更したり、257バイトの倍数である別のバイトをFFから00に変更したりすると、フレッチャーのチェックサムを使用するとキャンセルされますが、Adler-32チェックサムを使用するとキャンセルされません。このようなシナリオがランダムな破損から発生する可能性は特に高くありませんが、プログラムを変更すると、このような相殺の変更が発生する可能性があります。特にそうなる可能性は低いでしょう。

于 2011-08-26T17:32:23.333 に答える
0

答えは場の理論にあります。演算に und 回を加えた集合 Z/Z_n は、n が素数 (つまり、モジュロ n による加算と乗算) の場合の体です。

つまり、次の式です。

m * x = (in Z/Z_n)

m の任意の値 (つまり x = 0) に対して解が 1 つしかない

次の例を検討してください。

2 * x = 0 (mod 10)

この方程式には、x = 0 と x = 5 の 2 つの解があります。これは、10 が素数ではなく、2 * 5 と書くことができるためです。

このプロパティは、ハッシュ値の分散を改善する役割を果たします。

于 2013-11-26T08:00:21.673 に答える