Probabilità una funzione hash quasi universale $ax \bmod p \bmod m$ produce un output da input uguale modulo $m$
Per una delle funzioni hash quasi universali $f(x) = ax \bmod p \bmod m$ dove $p$ è primo e $m < p, m>1$ e $x$ varia $1 \dots p-1$ , qual è la probabilità che data $x_r \in \{ x | x \bmod p \bmod m = x \bmod m = r\}$, $f(x_r) = s$? Cioè, trova$Pr_{x_r}(f(x_r)=s)$. La probabilità è la frazione di$x$è tale che $x \bmod p \bmod m = x \bmod m= r$ che ha $f(x)=s$.
Ho posto questa domanda alcuni mesi fa su Mathematics Stack Exchange e non ho mai avuto risposta. È abbastanza semplice, ma è molto difficile cercare a livello di ricerca o ricerche precedenti sulla questione. La sezione seguente è proprio come l'ho pensata e non dovrebbe essere presa troppo sul serio come parte della domanda. In realtà, sospetto che ci sia un modo più semplice per affrontarlo.
Questa domanda differisce dalla solita domanda sulla probabilità di collisioni nelle funzioni hash quasi universali perché $a$ è costante e $x$ è variabile e solo quelli $x$con lo stesso doppio modulo sono considerati. La risposta sembra essere una questione di contare gli errori uno per uno. Anche la risposta è molto diversa. Ad esempio, se$a=1$, $Pr_{x_r}(f(x_r)=s) = \delta_{r,s}$ e se $a = m+3$, $Pr_{x_r}(f(x_r)=s) \approx \frac{1}{m+3} or \frac{2}{m+3}$.
Ho pensato a tre fonti di errori di recinzione nel conteggio del numero di soluzioni.
In primo luogo, senza prendere $\mod p$ o $\mod m$, $f(x_r)=s$ si verifica solo in determinati intervalli di lunghezza $p$ che si ripetono ogni $mp$. (In particolare,$s = (a \bmod m)(x_r \bmod m) + \lfloor \frac{ax_r}{p} \rfloor p \bmod m$.) Alla fine (e all'inizio) dell'intervallo di $f(x)$ prima di prendere i moduli ci può essere una regione aggiuntiva di lunghezza di $p$pieno di soluzioni extra. Ciò produce deviazioni dall'uniformità dell'ordine di$\frac{p}{ma}$ soluzioni (e differenze di probabilità dell'ordine di $\frac{1}{a}$).
In secondo luogo, in un "ordine superiore" possono esserci due regioni all'inizio e alla fine dell'intervallo di $f(x_r)$ (ancora prima di prendere i moduli) dove un numero $(f(x_r)=s)$-regioni di lunghezza $p$hanno una soluzione aggiuntiva ciascuno. (Cioè, c'è un palo di recinzione aggiuntivo nella lunghezza$p$.) Con l'aggiunta di ciascuno $mp$, la prima soluzione torna indietro $m(p \bmod a)$. Questo produce nell'ordine di$\frac{a}{p \bmod a}$ $mp$lunghezze che possono contenere una soluzione aggiuntiva. (Il numero di$mp$s riguarda $\frac{a}{p \bmod a}$ e una parte di esse arrotondate ha una soluzione in più.) Perché ci sia una soluzione in più la prima $ax_r$ in corrispondenza o dopo il corretto multiplo di $p$ deve essere minore di $p - \lfloor \frac{p}{am} \rfloor am = p \bmod am$. Quindi il numero effettivo di soluzioni extra sarà al massimo$\lfloor \frac{p \bmod am}{mp \bmod a} \rfloor + 1$ su ciascuna estremità dell'intervallo.
In terzo luogo, tuttavia, poiché il periodo di solito non è un numero intero, sembra che possano esserci errori di fence post di ordine superiore. Se guardi una sequenza di grandi multipli di$\frac{a}{p \bmod a}$ $mp$s inferiori all'intervallo totale di $f(x_r)$ (ovvero multipli di $mp$ sull'ordine $\frac{(p \bmod a)(ap)}{a(mp)} = \frac{p \bmod a}{m}$ ) (ad esempio dalla continua espansione della frazione di $\frac{a}{p \bmod a}$ o da potenze di 10) dovrebbero esserci errori di recinzione ai bordi di $[0,a(p-1)]$per ogni approssimazione nella sequenza. La lunghezza delle aree marginali in cui gli errori off-by-one dovrebbero essere più lunghi per ogni multiplo, ma la frazione di errori off-by-one dovrebbe essere proporzionalmente inferiore. Pertanto, gli errori del palo della recinzione dovrebbero verificarsi in una frazione costante del rapporto tra le lunghezze dei membri adiacenti della sequenza, quindi, a condizione che il rapporto tra le precisioni non vari troppo, la deviazione totale dall'uniformità dovrebbe essere intorno$\log p$ soluzioni.
Ciò significa che la media sopra $a$ la deviazione dall'uniformità dovrebbe essere corretta $\frac{m\log p}{p}$. In modo che per un scelto a caso$a$, la maggior parte della deviazione da una distribuzione uniforme sarà in questa terza fonte di errori di recinzione di ordine superiore. Da$ax \bmod p \bmod m$è solo una funzione hash quasi universale, questo non dovrebbe essere un problema, ma sono preoccupato di aver smesso di pensarci e potrebbe esserci un modo più semplice per risolvere il problema. La domanda è motivata dal calcolo dell'esponente modulare hash nelle varianti hash dell'algoritmo logaritmo discreto di Shor dalle matrici unitarie che rappresentano moltiplicazioni per potenza di due esponenti delle basi come delineato qui:https://arxiv.org/abs/1905.10074 e https://quantumcomputing.stackexchange.com/questions/12354/shors-discrete-logarithm-algorithm-with-a-qft-with-a-small-prime-base/
Risposte
Denota $\mathbb Z_p^*:=\{1,2,\dots,p-1\}$ e $\mathbb Z_m:=\{0,1,2,\dots,m-1\}$.
Presumo $p\nmid a$. Poi$f(x) = g(h(x))$, dove $h:\mathbb Z_p^*\to \mathbb Z_p^*$ è una biiezione definita da $h(x):=ax\bmod p$, e $g:\mathbb Z_p^*\to \mathbb Z_m$ è definito da $g(x):=x\bmod m$.
Permettere $b:=(p-1)\bmod m$ e $q:=\left\lfloor\frac{p-1}m\right\rfloor=\frac{p-1-b}m$. Ne consegue che$p=qm+b+1$. Permettere$B:=\{1,2,\dots,b\}\subset\mathbb Z_m$ e $I_B:\mathbb Z_m\to\{0,1\}$ essere la funzione di indicatore per il set $B$.
Ora, per scontato $r,s\in \mathbb Z_m$, abbiamo lo spazio campione $$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}\},$$ dove $\delta$è Kronecker delta . In particolare, abbiamo$|X_r| = q + I_B(r)$. Questo è il denominatore della probabilità$\mathrm{Pr}(f(x_r)=s)$. Ottenere il numeratore è più complicato.
Campionamento di $x_r\in X_r$ corrisponde al campionamento di un numero intero $c\in [ \delta_{r0}, q-1+I_B(r)+\delta_{r0} ]$e impostazione $x_r=cm+r$.
abbiamo $$(1)\qquad 1\leq cm+r\leq p-1.$$ Poi $h(x_r) = acm + ar - kp$ per alcuni $k$ (a seconda di $c$) soddisfacente $$(2)\qquad 0\leq acm + ar - kp\leq p-1.$$ Infine, $g(h(x_r))=s$ è equivalente a $$(3)\qquad ar - kp = s + mt$$ per un numero intero $t$ (di nuovo, a seconda di $c$).
Le (in) uguaglianze (1), (2), (3) definiscono un poliedro nello spazio 3D di $(c,k,t)$e il numeratore di $\mathrm{Pr}(f(x_r)=s)$è uguale al numero di punti interi in questo poliedro . Non penso che ci sia un'espressione semplice per questo numero in termini di parametri dati$p,m,a,r,s$.