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.


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.