Premium
Optimal linear perfect hash families with small parameters
Author(s) -
Barwick S. G.,
Jackson WenAi,
Quinn Catherine T.
Publication year - 2004
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/jcd.20010
Subject(s) - mathematics , combinatorics , perfect hash function , hash function , order (exchange) , discrete mathematics , injective function , vector space , linear space , perfect power , algorithm , pure mathematics , cryptography , cryptographic hash function , computer security , finance , computer science , economics
A linear ( q d , q , t )‐perfect hash family of size s consists of a vector space V of order q d over a field F of order q and a sequence ϕ 1 ,…,ϕ s of linear functions from V to F with the following property: for all t subsets X ⊆ V , there exists i ∈ {1,·, s } such that ϕ i is injective when restricted to F . A linear ( q d , q , t )‐perfect hash family of minimal size d ( – 1) is said to be optimal. In this paper, we prove that optimal linear ( q 2 , q , 4)‐perfect hash families exist only for q = 11 and for all prime powers q > 13 and we give constructions for these values of q . © 2004 Wiley Periodicals, Inc. J Comb Designs 12: 311–324, 2004