0
$\begingroup$

I want to find a set $H = \{x\mid x=(x_1, x_2, \ldots, x_k), x_i \in \{0, 1, \ldots, k-1\}\}$, which is pairwise independent(every $x_i$ and $x_j$ of the vector $\mathbf x$ in the set, it's $k^2$ combinations of values have the same probability) and the size of the set be as small as possible. Now I found that for all $k=p^n$, p is a prime, n is positive, the set size could be $k^2$, but I don't have a good answer for those $k\ne p^n$, for any $p, n$.

Actually, this question is to construct a set of a 2-universal family of hash functions to $\{0, \ldots, k-1\}$. It is easy if k is the size of a finite field, but the other cases I can't figure out how to construct a good enough one.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.