论文部分内容阅读
哈希函数在计算机和密码学领域都有着广泛的应用.1979年,J.Carter和M.Wegman提出的泛哈希函数族的概念,因其碰撞概率的可控性,得到了广泛关注并迅速在多个研究领域得到应用.同时,强泛哈希函数族,ε-泛哈希函数族等概念相继问世.关于泛哈希函数族与其它数学结构的联系的研究也逐渐展开.
在实践中,对于泛哈希函数族特性的要求最终体现为对其定义域、值域、函数族基数以及碰撞概率等参数的限制,所以有必要探究以上参数间的制约关系.本文结合已有研究结果,首先给出了以上参数间关系的主要结论,并且提出了饱和最简泛哈希函数族的概念.在此类泛哈希函数族中,对任两个自变量,函数族中仅存在一个使之取值相同的函数,而且函数族中函数个数达到理论上的上界.饱和最简泛哈希函数族满足碰撞最优,而且可以用来快速构造高重叠数的泛哈希函数族.本文给出了饱和最简泛哈希函数族的一个筛选算法,然后给出了它与有限仿射平面的等价性.文中同时介绍了素数幂阶饱和最简泛哈希函数族的构造.最后,本文给出了关于非素数幂阶饱和最简泛哈希函数族存在性的一个猜想.