Вероятность почти универсальной хеш-функции $ax \bmod p \bmod m$ производит вывод из входов, равных по модулю $m$
Для одной из почти универсальных хэш-функций $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$.
Я задал этот вопрос несколько месяцев назад на сайте Mathematics Stack Exchange и так и не получил ответа. Это достаточно просто, но это либо уровень исследования, либо предварительное исследование вопроса очень сложно найти. Раздел ниже - это то, как я думал об этом, и его не следует воспринимать слишком серьезно как часть вопроса. На самом деле, я подозреваю, что есть более простой способ подойти к этому.
Этот вопрос отличается от обычного вопроса о вероятности столкновений в почти универсальных хэш-функциях, поскольку $a$ постоянно и $x$ переменная и только те $x$с одинаковым двойным модулем. Ответ, по-видимому, заключается в подсчете ошибок на одну. Ответ тоже очень неопределенный. Например, если$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}$.
Я подумал о трех источниках ошибок столбов забора при подсчете количества решений.
Во-первых, не принимая $\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}$).
Во-вторых, на более высоком уровне могут быть две области в начале и в конце диапазона $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$ на каждом конце диапазона.
В-третьих, однако, поскольку период обычно не является целым числом, кажется, что могут быть ошибки столбов забора более высокого порядка. Если вы посмотрите на последовательность больших кратных$\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$, большая часть отклонений от равномерного распределения будет связана с этим третьим источником ошибок столбов забора более высокого порядка. поскольку$ax \bmod p \bmod m$- это всего лишь почти универсальная хеш-функция, это не должно быть проблемой, но я беспокоюсь, что я могу перестать думать об этом, и может быть более простой способ решения проблемы. Вопрос мотивирован вычислением хешированной модульной экспоненты в хешированных вариантах алгоритма дискретного логарифмирования Шора из унитарных матриц, представляющих умножение степеней двойки оснований, как показано здесь: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) определяют многогранник в трехмерном пространстве $(c,k,t)$, а числитель $\mathrm{Pr}(f(x_r)=s)$равно количеству целых точек в этом многограннике . Я не думаю, что есть простое выражение для этого числа в терминах заданных параметров$p,m,a,r,s$.