Kemungkinan fungsi hash yang hampir universal $ax \bmod p \bmod m$ menghasilkan keluaran dari masukan modulo yang sama $m$
Untuk salah satu fungsi hash yang hampir universal $f(x) = ax \bmod p \bmod m$ dimana $p$ adalah bilangan prima dan $m < p, m>1$ dan $x$ berkisar $1 \dots p-1$ , berapa probabilitas yang diberikan $x_r \in \{ x | x \bmod p \bmod m = x \bmod m = r\}$, $f(x_r) = s$? Artinya, temukan$Pr_{x_r}(f(x_r)=s)$. Probabilitasnya adalah pecahan dari$x$seperti itu $x \bmod p \bmod m = x \bmod m= r$ yang mempunyai $f(x)=s$.
Saya mengajukan pertanyaan ini beberapa bulan yang lalu di Mathematics Stack Exchange dan tidak pernah mendapat jawaban. Ini cukup sederhana, tetapi baik itu tingkat penelitian atau penelitian sebelumnya tentang pertanyaan itu sangat sulit untuk dicari. Bagian di bawah ini adalah bagaimana saya memikirkannya dan tidak boleh dianggap terlalu serius sebagai bagian dari pertanyaan. Sebenarnya, saya curiga ada cara yang lebih sederhana untuk mendekatinya.
Pertanyaan ini berbeda dari pertanyaan biasa tentang kemungkinan tabrakan dalam fungsi hash yang hampir universal karena $a$ konstan dan $x$ adalah variabel dan hanya itu $x$dengan modulus ganda yang sama dipertimbangkan. Jawabannya tampaknya pertanyaan menghitung kesalahan satu per satu. Jawabannya juga sangat berbeda. Misalnya, jika$a=1$, $Pr_{x_r}(f(x_r)=s) = \delta_{r,s}$ dan jika $a = m+3$, $Pr_{x_r}(f(x_r)=s) \approx \frac{1}{m+3} or \frac{2}{m+3}$.
Saya telah memikirkan tiga sumber kesalahan tiang pagar dalam menghitung jumlah solusi.
Pertama, tanpa mengambil $\mod p$ atau $\mod m$, $f(x_r)=s$ hanya terjadi dalam rentang panjang tertentu $p$ yang berulang setiap $mp$. (Secara khusus,$s = (a \bmod m)(x_r \bmod m) + \lfloor \frac{ax_r}{p} \rfloor p \bmod m$.) Di akhir (dan awal) rentang $f(x)$ sebelum mengambil modulus mungkin ada daerah panjang tambahan $p$diisi dengan solusi ekstra. Hal ini menghasilkan penyimpangan dari keseragaman urutan$\frac{p}{ma}$ solusi (dan perbedaan probabilitas di urutan $\frac{1}{a}$).
Kedua, pada 'tatanan yang lebih tinggi' dapat terdapat dua wilayah di awal dan akhir rentang $f(x_r)$ (sekali lagi sebelum mengambil modulus) di mana nomor $(f(x_r)=s)$-regions panjang $p$punya solusi tambahan masing-masing. (Artinya, ada tiang pagar tambahan yang panjangnya$p$.) Dengan penambahan masing-masing $mp$, solusi pertama bergulir kembali $m(p \bmod a)$. Ini menghasilkan di urutan$\frac{a}{p \bmod a}$ $mp$panjang yang mungkin berisi solusi tambahan. (Jumlah$mp$s tentang $\frac{a}{p \bmod a}$ dan beberapa pecahan dari mereka yang dibulatkan memiliki solusi tambahan.) Karena akan ada solusi ekstra yang pertama $ax_r$ pada atau setelah kelipatan yang benar dari $p$ harus kurang dari $p - \lfloor \frac{p}{am} \rfloor am = p \bmod am$. Jadi jumlah solusi tambahan sebenarnya paling banyak$\lfloor \frac{p \bmod am}{mp \bmod a} \rfloor + 1$ di setiap ujung rentang.
Ketiga, bagaimanapun, karena periode biasanya bukan bilangan bulat, tampaknya ada kesalahan tiang pagar urutan tinggi. Jika Anda melihat urutan kelipatan besar$\frac{a}{p \bmod a}$ $mp$s yang lebih kecil dari rentang total $f(x_r)$ (itu adalah kelipatan $mp$ dalam pesanan $\frac{(p \bmod a)(ap)}{a(mp)} = \frac{p \bmod a}{m}$ ) (misalnya dari perluasan pecahan lanjutan dari $\frac{a}{p \bmod a}$ atau dari kekuatan 10) harus ada kesalahan tiang pagar di tepi $[0,a(p-1)]$untuk setiap perkiraan dalam urutan. Panjang daerah tepi di mana kesalahan satu per satu harus lebih panjang untuk setiap kelipatan, tetapi pecahan kesalahan satu per satu harus lebih kecil secara proporsional. Dengan demikian, kesalahan tiang pagar harus terjadi pada beberapa fraksi konstan dari rasio panjang anggota yang berdekatan dari urutan tersebut, jadi, asalkan rasio antara akurasi tidak terlalu bervariasi, total penyimpangan dari keseragaman harus sekitar.$\log p$ solusi.
Artinya rata-rata di atas $a$ penyimpangan dari keseragaman harus teratur $\frac{m\log p}{p}$. Sehingga untuk dipilih secara acak$a$, sebagian besar penyimpangan dari distribusi seragam akan berada di urutan sumber ketiga yang lebih tinggi dari kesalahan tiang pagar. Sejak$ax \bmod p \bmod m$hanya fungsi hash yang hampir universal, ini seharusnya tidak menjadi masalah, tetapi saya khawatir saya mungkin terlalu memikirkannya dan mungkin ada cara yang lebih sederhana untuk memecahkan masalah. Pertanyaannya dimotivasi dengan menghitung eksponen modular berciri dalam varian hash dari algoritme diskrit logaritma Shor dari matriks kesatuan yang merepresentasikan perkalian dengan pangkat dua eksponen dari pangkalan seperti yang diuraikan di sini:https://arxiv.org/abs/1905.10074 dan https://quantumcomputing.stackexchange.com/questions/12354/shors-discrete-logarithm-algorithm-with-a-qft-with-a-small-prime-base/
Jawaban
Menunjukkan $\mathbb Z_p^*:=\{1,2,\dots,p-1\}$ dan $\mathbb Z_m:=\{0,1,2,\dots,m-1\}$.
Saya berasumsi $p\nmid a$. Kemudian$f(x) = g(h(x))$, dimana $h:\mathbb Z_p^*\to \mathbb Z_p^*$ adalah kebijaksanaan yang ditentukan oleh $h(x):=ax\bmod p$, dan $g:\mathbb Z_p^*\to \mathbb Z_m$ didefinisikan oleh $g(x):=x\bmod m$.
Membiarkan $b:=(p-1)\bmod m$ dan $q:=\left\lfloor\frac{p-1}m\right\rfloor=\frac{p-1-b}m$. Ini mengikuti itu$p=qm+b+1$. Membiarkan$B:=\{1,2,\dots,b\}\subset\mathbb Z_m$ dan $I_B:\mathbb Z_m\to\{0,1\}$ menjadi fungsi indikator untuk set $B$.
Sekarang, untuk diberikan $r,s\in \mathbb Z_m$, kami memiliki ruang sampel $$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}\},$$ dimana $\delta$adalah delta Kronecker . Secara khusus, kami punya$|X_r| = q + I_B(r)$. Ini adalah penyebut probabilitas$\mathrm{Pr}(f(x_r)=s)$. Mendapatkan pembilang itu lebih sulit.
Pengambilan sampel $x_r\in X_r$ sesuai dengan pengambilan sampel bilangan bulat $c\in [ \delta_{r0}, q-1+I_B(r)+\delta_{r0} ]$, dan pengaturan $x_r=cm+r$.
Kita punya $$(1)\qquad 1\leq cm+r\leq p-1.$$ Kemudian $h(x_r) = acm + ar - kp$ untuk beberapa $k$ (bergantung kepada $c$) memuaskan $$(2)\qquad 0\leq acm + ar - kp\leq p-1.$$ Akhirnya, $g(h(x_r))=s$ setara dengan $$(3)\qquad ar - kp = s + mt$$ untuk beberapa bilangan bulat $t$ (sekali lagi, tergantung $c$).
Persamaan (dalam) (1), (2), (3) mendefinisikan polihedron dalam ruang 3D dari $(c,k,t)$, dan pembilang $\mathrm{Pr}(f(x_r)=s)$sama dengan jumlah titik integer dalam polihedron ini . Saya tidak berpikir ada ekspresi sederhana untuk angka ini dalam hal parameter yang diberikan$p,m,a,r,s$.