Коллекция хеш-функций $H=\{h:\{0,1\}^n \to \{0,1\}^m\}$ попарно независимым, если для каждого $x_1 \neq x_2 \in \{0,1\}^n$ и $y_1, y_2 \in \{0,1\}^m$:
$$ \Pr_{h \leftarrow H}[h(x_1)=y_1 \клин h(x_2)=y_2]=\frac{1}{2^{2m}} $$
Учитывая конечное поле $\mathbb{F}$ размера $2^n$ Я смог доказать для набора хеш-функций:
$\{h_{a,b}: \mathbb{F}\to \mathbb{F}\}_{a,b \in \mathbb{F}}$ куда: $h_{a,b}=ax+b$
что она попарно независима.
Теперь меня просят расширить это для случая, когда домен и диапазон не совпадают - первый имеет размер $2^n$ и последний $2^м$.
Я подумал о следующем расширении, но не уверен, что оно сработает: выберите $a,b \in \mathbb{F}_{2^m}$. Идея состоит в том, что мне нужно иметь инверсию в поле, чтобы однозначно решить для $а,б$ (например, для $ax_1+b=y_1$ Я хочу решить для $а,б$ однозначно, найдя $a=(y_1-b)x_1^{-1}$ и аналогично для $b$ (система двух уравнений по модулю $\mathbb{F}_{2^m}$), так что я получаю вышеупомянутую вероятность). Следствие означало бы убедиться, $x_1, x_2$ находятся в поле, т.е. $а$ и $b$ такой, что $x_1=(y_1-b)a^{-1}$. С $y_1 \in \mathbb{F}_{2^m}$ тогда было бы достаточно, чтобы также $a,b \in \mathbb{F}_{2^m}$.
Я совершенно не уверен, правильно ли это. Мы будем очень признательны за любые советы.
