ほぼ普遍的なハッシュ関数の確率 $ax \bmod p \bmod m$ モジュロに等しい入力から出力を生成します $m$
ほぼ普遍的なハッシュ関数の1つ $f(x) = ax \bmod p \bmod m$ どこ $p$ 素数であり、 $m < p, m>1$ そして $x$ 範囲 $1 \dots p-1$ 、与えられた確率は何ですか $x_r \in \{ x | x \bmod p \bmod m = x \bmod m = r\}$、 $f(x_r) = s$？つまり、見つける$Pr_{x_r}(f(x_r)=s)$。確率はの割合です$x$そのような $x \bmod p \bmod m = x \bmod m= r$ 持っている $f(x)=s$。
数か月前にMathematicsStack Exchangeでこの質問をしましたが、返事がありませんでした。それは十分に単純ですが、それは研究レベルであるか、質問に関する以前の研究を検索するのは非常に困難です。以下のセクションは、私がそれについてどのように考えたかであり、質問の一部としてあまり真剣に受け止めるべきではありません。実際、もっと簡単な方法があるのではないかと思います。
この質問は、ほぼ普遍的なハッシュ関数での衝突の確率に関する通常の質問とは異なります。 $a$ 一定であり、 $x$ 可変であり、それらのみ $x$同じ二重弾性率を持つものが考慮されます。答えは、エラーを1つずつ数えることの問題のようです。答えも非常に異なります。たとえば、$a=1$、 $Pr_{x_r}(f(x_r)=s) = \delta_{r,s}$ で、もし $a = m+3$、 $Pr_{x_r}(f(x_r)=s) \approx \frac{1}{m+3} or \frac{2}{m+3}$。
ソリューションの数を数える際のフェンスポストエラーの3つの原因について考えました。
まず、服用せずに $\mod p$ または $\mod m$、 $f(x_r)=s$ 特定の長さの範囲でのみ発生します $p$ 毎回繰り返す $mp$。（具体的には、$s = (a \bmod m)(x_r \bmod m) + \lfloor \frac{ax_r}{p} \rfloor p \bmod m$。）の範囲の終わり（および始まり） $f(x)$ 係数を取る前に、長さの追加の領域が存在する可能性があります $p$追加のソリューションでいっぱい。これにより、均一性からの偏差が$\frac{p}{ma}$ 解（および次のオーダーの確率の差） $\frac{1}{a}$）。
第二に、「高次」では、範囲の最初と最後に2つの領域が存在する可能性があります。 $f(x_r)$ （再びモジュラスを取る前に）ここで、 $(f(x_r)=s)$-長さの領域 $p$それぞれに追加のソリューションがあります。（つまり、長さに追加のフェンスポストがあります$p$。）それぞれを追加して $mp$、最初のソリューションは次のようにロールバックします $m(p \bmod a)$。これは、$\frac{a}{p \bmod a}$ $mp$追加のソリューションを含む可能性のある長さ。（の数$mp$sは約 $\frac{a}{p \bmod a}$ そして、それらの一部を丸めると、追加の解決策があります。）追加の解決策があるためには、最初に $ax_r$ の正しい倍数以降 $p$ 未満である必要があります $p - \lfloor \frac{p}{am} \rfloor am = p \bmod am$。したがって、追加のソリューションの実際の数は最大で$\lfloor \frac{p \bmod am}{mp \bmod a} \rfloor + 1$ 範囲の両端に。
ただし、第3に、ピリオドは通常整数ではないため、高次のフェンスポストエラーが発生する可能性があるようです。あなたがの大きな倍数のシーケンスを見れば$\frac{a}{p \bmod a}$ $mp$の全範囲よりも小さいs $f(x_r)$ （つまり、の倍数です $mp$ 注文時に $\frac{(p \bmod a)(ap)}{a(mp)} = \frac{p \bmod a}{m}$ ）（たとえば、連分数の拡大から $\frac{a}{p \bmod a}$ または10の累乗から）の端にフェンスポストエラーがあるはずです $[0,a(p-1)]$シーケンス内の各近似に対して。倍数ごとにオフバイワンエラーが長くなるエッジ領域の長さですが、オフバイワンエラーの割合は比例して小さくする必要があります。したがって、フェンスポストエラーは、シーケンスの隣接するメンバーの長さの比率の一定の割合で発生するはずです。したがって、精度間の比率があまり変化しない場合、均一性からの全体的な偏差は約$\log p$ ソリューション。
これは、平均 $a$ 均一性からの逸脱は秩序だったはずです $\frac{m\log p}{p}$。ランダムに選択された$a$、一様分布からの偏差のほとんどは、この3番目に高いフェンスポストエラーの原因になります。以来$ax \bmod p \bmod m$はほぼ普遍的なハッシュ関数にすぎないので、これは問題にはならないはずですが、私はそれを考えすぎて、問題を解決するより簡単な方法があるのではないかと心配しています。この質問は、ユニタリ行列からショアの離散対数アルゴリズムのハッシュされたバリアントでハッシュされたモジュラー指数を計算することによって動機付けられます。これは、ここで概説するように、底の2乗指数による乗算を表します。https://arxiv.org/abs/1905.10074 そして https://quantumcomputing.stackexchange.com/questions/12354/shors-discrete-logarithm-algorithm-with-a-qft-with-a-small-prime-base/
回答
示す $\mathbb Z_p^*:=\{1,2,\dots,p-1\}$ そして $\mathbb Z_m:=\{0,1,2,\dots,m-1\}$。
私が想定し $p\nmid a$。次に$f(x) = g(h(x))$、 どこ $h:\mathbb Z_p^*\to \mathbb Z_p^*$ によって定義される全単射です $h(x):=ax\bmod p$、および $g:\mathbb Z_p^*\to \mathbb Z_m$ によって定義されます $g(x):=x\bmod m$。
しましょう $b:=(p-1)\bmod m$ そして $q:=\left\lfloor\frac{p-1}m\right\rfloor=\frac{p-1-b}m$。その結果$p=qm+b+1$。しましょう$B:=\{1,2,\dots,b\}\subset\mathbb Z_m$ そして $I_B:\mathbb Z_m\to\{0,1\}$ セットのインジケーター機能になります $B$。
さて、与えられた $r,s\in \mathbb Z_m$、サンプルスペースがあります $$X_r := \{ x\in Z_p^*\mid x\bmod m=r\} = \{ cm+r\mid \delta_{r0}\leq c\leq q-1+I_B(r)+\delta_{r0}\},$$ どこ $\delta$あるクロネッカーのデルタ。特に、$|X_r| = q + I_B(r)$。これは確率の分母です$\mathrm{Pr}(f(x_r)=s)$。分子を取得するのは難しいです。
のサンプリング $x_r\in X_r$ 整数のサンプリングに対応 $c\in [ \delta_{r0}, q-1+I_B(r)+\delta_{r0} ]$、および設定 $x_r=cm+r$。
我々は持っています $$(1)\qquad 1\leq cm+r\leq p-1.$$ 次に $h(x_r) = acm + ar - kp$ いくつかのための $k$ （応じて $c$）満足 $$(2)\qquad 0\leq acm + ar - kp\leq p-1.$$ 最終的に、 $g(h(x_r))=s$ と同等です $$(3)\qquad ar - kp = s + mt$$ いくつかの整数の場合 $t$ （繰り返しますが、 $c$）。
（不）等式（1）、（2）、（3）は、の3D空間で多面体を定義します。 $(c,k,t)$、およびの分子 $\mathrm{Pr}(f(x_r)=s)$この多面体の整数点の数に等しい。与えられたパラメータに関して、この数の簡単な式はないと思います$p,m,a,r,s$。