A linear (q~d, q, t)-perfect hash family of size s in a vector space V of order q~d over a field F of order q consists of a sequence Φ1.....Φs of linear functions from V to F with the following property: for all t subsets X is contained V there exists ∈{1,...,s} such that Φi is injective when restricted to F. A linear (q~d, q, t)-perfect hash family of minimal size d(t — 1) is said to be optimal. In this paper we use projective geometry techniques to completely determine the values of q for which optimal linear (q~3, q, 3)-perfect hash families exist and give constructions in these cases. We also give constructions of optimal linear (q~2, q, 5)-perfect hash families.
展开▼
