ハッシュ関数 xxHash の入力を32bitに限定した場合に重複した値が出ないことを確認したい

#32bit入力のxxHash実装
xxHash は各所で人気のあるハッシュ関数のようです。
http://cyan4973.github.io/xxHash/
作者のYann Colletさんに敬意を表しつつ、これの入力を32bitに限定した場合の実装を書いてみます。言語はC#にしておきましょう。

int get_xxhash(int data, uint seed)
{
	const uint PRIME32_2 = 2246822519U;
	const uint PRIME32_3 = 3266489917U;
	const uint PRIME32_4 = 668265263U;
	const uint PRIME32_5 = 374761393U;
	uint h32 = (uint)data * PRIME32_3;
	h32 += seed + PRIME32_5 + 4U;
	h32 = (h32 << 17) | (h32 >> 15);
	h32 *= PRIME32_4;
	h32 ^= h32 >> 15;
	h32 *= PRIME32_2;
	h32 ^= h32 >> 13;
	h32 *= PRIME32_3;
	h32 ^= h32 >> 16;
	return (int)h32;
}
int get_xxhash(int data)
{
	return get_xxhash(data, 12345U);
}

オリジナルのソースコードは入力がデータ配列なので、先頭の4bytesだけ扱うように書き換えたものです。
seedは指定してもしなくてもいいよう、適当な値をデフォルトにしておきます。

#重複を調べる
ここで気になるのは、この関数が重複なくバラバラの値を返してくれるのか否か。異なる入力で同じ値が返ってきちゃうことが本当にないのか？
理屈としては、入力が32bitで出力が32bitなので、この関数が全単射になっていれば重複はないことになります。
全単射は、逆関数が存在を調べることでも確認できます。先ほどの関数の逆関数が存在するかを考えていきましょう。

##関数内のすべての演算を調べる
xxhashはいくつかのステップで計算されていますが、それぞれの演算で逆関数があれば、この関数全体も逆関数を持つことになります。がんばって調べていきましょう。

	uint h32 = (uint)data * PRIME32_3; // (1)
	h32 += seed + PRIME32_5 + 4U;      // (2)
	h32 = (h32 << 17) | (h32 >> 15);   // (3)
	h32 *= PRIME32_4;                  // (4)
	h32 ^= h32 >> 15;                  // (5)
	h32 *= PRIME32_2;                  // (6)
	h32 ^= h32 >> 13;                  // (7)
	h32 *= PRIME32_3;                  // (8)
	h32 ^= h32 >> 16;                  // (9)

この９つの演算を調べます。４種類に分けられますね。
A. 素数との乗算 (1)(4)(6)(8)
B. 足し算 (2)
C. 17bit左シフトと15ビット右シフトのor (3)
D. 右シフトしてxor (5)(7)(9)
順番にやっつけていきます。がA.は難敵なので後回しです。

###B. 足し算
seed（任意の値）と素数374761393と4の和を加算しています。和の時点で2^32でオーバーフローしているかもしれませんが、気にする必要はありません。2^32の空間であれば足し算について逆関数が存在し、それは
ビット反転して+1したものを加算する
というものです。逆関数が存在し、すなわち全単射の演算である、すなわちこれは重複が起きない演算であることがわかります。

###C. 17bit左シフトと15ビット右シフトのor
これは32bitの右17bitと左15bitを入れ替える演算になります。よって逆関数も自明。問題なし。

###D. 右シフトしてxor
これが逆関数を持つかどうかについては、こちらの素晴らしい記事
https://blog.visvirial.com/articles/575
が丁寧に解説してくれています。結論から言えば逆関数は存在し、例えば
x ^ (x >> 15)
の逆関数は
x ^ (x >> 15) ^ (x >> 30)
となります。

###A. 素数との乗算
問題はこれです。いくら考えても逆関数を導出できなかったので、全単射かどうかだけを考えることにします。

####証明
ある数$a$と$P$の乗算結果を$M$で割ったあまりを$Q$とする。$Q$が与えられたとき、$a$がひとつだけ存在することを証明する。
ただし $0\leq a<2^{32}, 0\leq Q<2^{32}, P$は素数 とする。
$aP\ mod\ M=Q$より（$mod\ M$は$M$で割った余り）、$n$を整数とすると
　　　 $Q+Mn=aP ...(1)$
と表せる。ここで $a$ の他にこの式を満たす $b$ が存在すると仮定する。ただし $0\leq b<2^{32}, a<b$ とする。
$b$ は $a$ と同様に、$m$を整数として次の式を満たす。
　　　 $Q+Mm=bP ...(2)$
(2)-(1)より
　　　 $M(m-n)=P(b-a)$
$M \neq 0, a \neq b$より
　　　 $\frac{m-n}{b-a}=\frac{P}{M}$
ここで $(m-n)$ と $(b-a)$ の共通の因数を $k$ とおくと、
　　　 $k(m'-n')=m-n$
　　　 $k(b'-a')=b-a$
なる$a',b',n',m'$が存在する。（$k=1$の場合は $m-n$ と $b-a$ が互いに素であることを意味する）
このとき $k \geq 1$ となる ・・・$(A)$
$P$と$M$は互いに素なので（注；この条件が必要なので、実は仮定に誤りがあった。$P$が素数ではなく、$P$と$M$は互いに素、という条件にすべき）
$(m'-n')$と$(b'-a')$が互い素であることから、
　　　 $m'-n'=P$
　　　 $b'-a'=M ...(3)$
が成り立つ。仮定より

$0\leq a < M, 0 \leq b < M $ なので
　　　 $b-a < M$
よって
　　　 $k(b'-a') < M$
(3)より
　　　 $kM < M$
$M > 0$ より
　　　 $k < 1$
これは $(A)$ と矛盾する。$b$ の存在を仮定したことにより矛盾が生じたので、$b$ は存在しない。
よって条件を満たす $a$ はただひとつだけ存在する。

---

同様のやりかたで $a$ が与えられたとき $Q$ もただひとつであることが確認できるので、(1)(4)(6)(8)の演算は全単射であることを示せます。

##というわけで
32bit版xxhashで使用されている各ステップの演算にはすべて逆関数が存在しました。すなわち関数そのものが全単射で、入力に対する重複がない、ということがわかります。めでたしめでたし。

##おまけ
A.の逆関数に関しては存在は証明したものの、具体的な一般式は見つけられませんでした。総当たりでループするぐらいしか思いつきません。