Probabilidad una función hash casi universal $ax \bmod p \bmod m$ produce una salida de entradas igual módulo $m$
Para una de las funciones hash casi universales $f(x) = ax \bmod p \bmod m$ dónde $p$ es primo y $m < p, m>1$ y $x$ se extiende sobre $1 \dots p-1$ , ¿cuál es la probabilidad de que dado $x_r \in \{ x | x \bmod p \bmod m = x \bmod m = r\}$, $f(x_r) = s$? Es decir, encontrar$Pr_{x_r}(f(x_r)=s)$. La probabilidad es la fracción de$x$es tal que $x \bmod p \bmod m = x \bmod m= r$ eso tiene $f(x)=s$.
Hice esta pregunta hace unos meses en Mathematics Stack Exchange y nunca obtuve una respuesta. Es bastante simple, pero es un nivel de investigación o una investigación previa sobre la pregunta es muy difícil de buscar. La siguiente sección es solo cómo lo he pensado y no debería tomarse demasiado en serio como parte de la pregunta. De hecho, sospecho que hay una forma más sencilla de abordarlo.
Esta pregunta difiere de la pregunta habitual sobre la probabilidad de colisiones en funciones hash casi universales porque $a$ es constante y $x$ es variable y solo aquellos $x$con el mismo módulo doble se consideran. La respuesta parece ser una cuestión de contar los errores uno por uno. La respuesta también es muy diferente. Por ejemplo, si$a=1$, $Pr_{x_r}(f(x_r)=s) = \delta_{r,s}$ y si $a = m+3$, $Pr_{x_r}(f(x_r)=s) \approx \frac{1}{m+3} or \frac{2}{m+3}$.
He pensado en tres fuentes de errores en los postes de cerca al contar la cantidad de soluciones.
Primero, sin tomar $\mod p$ o $\mod m$, $f(x_r)=s$ ocurre solo en ciertos rangos de longitud $p$ que repiten cada $mp$. (Específicamente,$s = (a \bmod m)(x_r \bmod m) + \lfloor \frac{ax_r}{p} \rfloor p \bmod m$.) Al final (y al principio) del rango de $f(x)$ antes de tomar los módulos puede haber una región adicional de longitud de $p$lleno de soluciones adicionales. Esto produce desviaciones de la uniformidad del orden de$\frac{p}{ma}$ soluciones (y diferencias de probabilidad del orden de $\frac{1}{a}$).
En segundo lugar, en un 'orden superior' puede haber dos regiones al principio y al final del rango de $f(x_r)$ (nuevamente antes de tomar los módulos) donde un número $(f(x_r)=s)$-regiones de longitud $p$tener una solución adicional cada uno. (Es decir, hay un poste de cerca adicional en la longitud$p$.) Con la adición de cada $mp$, la primera solución se revierte $m(p \bmod a)$. Esto produce del orden de$\frac{a}{p \bmod a}$ $mp$longitudes que pueden contener una solución adicional. (El número de$mp$s se trata de $\frac{a}{p \bmod a}$ y una fracción de ellos redondeados tiene una solución extra.) Para que haya una solución extra, la primera $ax_r$ en o después del múltiplo correcto de $p$ debe ser menor que $p - \lfloor \frac{p}{am} \rfloor am = p \bmod am$. Entonces, la cantidad real de solución adicional será como máximo$\lfloor \frac{p \bmod am}{mp \bmod a} \rfloor + 1$ en cada extremo del rango.
En tercer lugar, sin embargo, dado que el período no suele ser un número entero, parece que puede haber errores de poste de cerca de orden superior. Si observa una secuencia de grandes múltiplos de$\frac{a}{p \bmod a}$ $mp$s que son más pequeños que el rango total de $f(x_r)$ (que es múltiplo de $mp$ en el orden $\frac{(p \bmod a)(ap)}{a(mp)} = \frac{p \bmod a}{m}$ ) (por ejemplo, de la expansión continua de la fracción de $\frac{a}{p \bmod a}$ o de potencias de 10) debe haber errores en los postes de la cerca en los bordes de $[0,a(p-1)]$para cada aproximación en la secuencia. La longitud de las regiones de borde donde los errores de uno por uno debería ser mayor para cada múltiplo, pero la fracción de errores de uno por uno debería ser proporcionalmente menor. Por lo tanto, los errores de los postes de la cerca deben ocurrir en una fracción constante de la relación de las longitudes de los miembros adyacentes de la secuencia, por lo que, siempre que la relación entre las precisiones no varíe demasiado, la desviación total de la uniformidad debe ser de$\log p$ soluciones.
Esto significa que el promedio sobre $a$ la desviación de la uniformidad debe ser de orden $\frac{m\log p}{p}$. De modo que para un elegido al azar$a$, la mayor parte de la desviación de una distribución uniforme estará en esta fuente de tercer orden superior de errores en los postes de la cerca. Ya que$ax \bmod p \bmod m$es solo una función hash casi universal, esto no debería ser un problema, pero me preocupa que haya terminado de pensarlo y que haya una forma más simple de resolver el problema. La pregunta está motivada por calcular el exponente modular con hash en variantes con hash del algoritmo de logaritmo discreto de Shor a partir de las matrices unitarias que representan multiplicaciones por exponentes de potencia de dos de las bases como se describe aquí:https://arxiv.org/abs/1905.10074 y https://quantumcomputing.stackexchange.com/questions/12354/shors-discrete-logarithm-algorithm-with-a-qft-with-a-small-prime-base/
Respuestas
Denotar $\mathbb Z_p^*:=\{1,2,\dots,p-1\}$ y $\mathbb Z_m:=\{0,1,2,\dots,m-1\}$.
Asumo $p\nmid a$. Entonces$f(x) = g(h(x))$, dónde $h:\mathbb Z_p^*\to \mathbb Z_p^*$ es una biyección definida por $h(x):=ax\bmod p$y $g:\mathbb Z_p^*\to \mathbb Z_m$ es definido por $g(x):=x\bmod m$.
Dejar $b:=(p-1)\bmod m$ y $q:=\left\lfloor\frac{p-1}m\right\rfloor=\frac{p-1-b}m$. Resulta que$p=qm+b+1$. Dejar$B:=\{1,2,\dots,b\}\subset\mathbb Z_m$ y $I_B:\mathbb Z_m\to\{0,1\}$ ser la función indicadora del conjunto $B$.
Ahora, por supuesto $r,s\in \mathbb Z_m$, tenemos el espacio muestral $$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}\},$$ dónde $\delta$es el delta de Kronecker . En particular, tenemos$|X_r| = q + I_B(r)$. Este es el denominador de la probabilidad$\mathrm{Pr}(f(x_r)=s)$. Obtener el numerador es más complicado.
Muestreo de $x_r\in X_r$ corresponde a muestrear un entero $c\in [ \delta_{r0}, q-1+I_B(r)+\delta_{r0} ]$y entorno $x_r=cm+r$.
Tenemos $$(1)\qquad 1\leq cm+r\leq p-1.$$ Entonces $h(x_r) = acm + ar - kp$ para algunos $k$ (Dependiendo de $c$) satisfactorio $$(2)\qquad 0\leq acm + ar - kp\leq p-1.$$ Finalmente, $g(h(x_r))=s$ es equivalente a $$(3)\qquad ar - kp = s + mt$$ por algún entero $t$ (de nuevo, dependiendo de $c$).
Las (in) igualdades (1), (2), (3) definen un poliedro en el espacio 3D de $(c,k,t)$, y el numerador de $\mathrm{Pr}(f(x_r)=s)$es igual al número de puntos enteros en este poliedro . No creo que haya una expresión simple para este número en términos de los parámetros dados.$p,m,a,r,s$.