O colecție de funcții hash $H=\{h:\{0,1\}^n \la \{0,1\}^m\}$ este independent perechi dacă pentru fiecare $x_1 \neq x_2 \in \{0,1\}^n$ și $y_1, y_2 \in \{0,1\}^m$:
$$ \Pr_{h \leftarrow H}[h(x_1)=y_1 \wedge h(x_2)=y_2]=\frac{1}{2^{2m}} $$
Dat un câmp finit $\mathbb{F}$ de mărime $2^n$ Am putut dovedi pentru setul de funcții hash:
$\{h_{a,b}: \mathbb{F}\la \mathbb{F}\}_{a,b \in \mathbb{F}}$ Unde: $h_{a,b}=ax+b$
că este independent pe perechi.
Acum mi se cere să extind acest lucru pentru cazul în care domeniul și domeniul nu sunt aceleași - - primul are dimensiune $2^n$ iar acesta din urmă $2^m$.
M-am gândit la următoarea extensie, dar nu sunt sigur dacă ar funcționa: alege $a,b \in \mathbb{F}_{2^m}$. Ideea este că trebuie să am un invers în domeniu pentru a putea rezolva în mod unic $a,b$ (de ex. pentru $ax_1+b=y_1$ vreau sa rezolv pt $a,b$ unic prin găsirea $a=(y_1-b)x_1^{-1}$ si asemanator pentru $b$ (un sistem de două ecuații mod $\mathbb{F}_{2^m}$) astfel încât să obțin probabilitatea menționată mai sus). Un corolar ar însemna a fi sigur $x_1, x_2$ sunt pe teren, adică există $a$ și $b$ astfel încât $x_1=(y_1-b)a^{-1}$. De cand $y_1 \in \mathbb{F}_{2^m}$ atunci ar fi suficient ca și $a,b \in \mathbb{F}_{2^m}$.
Sunt destul de nesigur dacă acest lucru este corect. Orice sfat ar fi foarte apreciat.
