math - XOR と mod の可換性

Question

そのため、ハッシュ関数を調べていると、次の式に気付きました。

((129*N)^prev)%256 = ((129*N)%256)^prev

0 から 255 までの任意の数値N, prev。基本的には、結果を変更せずに mod 操作をドラッグすることができます。これは数値 129 に対してのみ機能します。誰か、129 の何が特別なのか教えてもらえますか?

Answer 1

剰余算術を扱う場合、次のことが起こります。

(a*b) mod m = ((a mod m) * (b mod m)) mod m

この性質を当てはめるとb = a

a^2 mod m = (a mod m)^2 mod m

nそして同じ時間を繰り返す

a^n mod m = (a mod m)^n mod m

また、これは の任意の値に対して有効であるためa、次も得られます。

(a*b)^n mod m = (a*b mod m)^n mod m

したがって、プロパティは、存在するかどうか、および存在するかどうかに関係mなく256有効aです129。

129ただし、 as1, 127, 129には非常に特別な何かがあり、そのような255唯一の残りがあります。と にも注意してください。mod 256r * r = 1 mod 256255 = -1 (mod 256)127 = -129 mod 256

Answer 2

これは、256 によるモジュロをビットごとの AND 255 として解釈する場合、つまり、最下位 8 ビットのみを保持する場合に簡単に確認できます。

明らかに、XOR は上位ビットから下位ビットに移動する情報を作成しません (実際にはどちらの方向にも移動しません)。上位ビットに違いが生じる可能性があります (XOR が設定され、AND が最初に発生するか 2 番目に発生するかに応じて、これらのビットはそれぞれ設定またはリセットされます)。

代数的に、AND は XOR で分散するので、

(a ^ b) & c =
& distributes over ^
(a & c) ^ (b & c)

これは 255 であり、0 から 255 の間ですb & c = b。cb

(a & c) ^ (b & c) =
by assumptions
(a & c) ^ b

これは乗算とは関係ありません。文字通り何でもかまいませんa。ここではその部分を呼び出しました。