主题
Search

通用哈希函数

设 h:{0,1}^(l(n))×{0,1}^n->{0,1}^(m(n)) 可通过算法有效计算（解决一个 P 问题）。对于固定的 y in {0,1}^(l(n))，将 h(x,y) 视为 h_y(x) 的函数 x，它将 n 位映射（或哈希）到 m(n) 位。设 Y in _R{0,1}^(l(n))，则如果对于不同的 x,x^' in {0,1}^n 且对于所有 a,a^' in {0,1}^(m(n))，则称 h 为（成对独立的）通用哈希函数：

Pr_(Y)[(h_Y(x)=a) and (h_Y(x^')=a^')]=1/(2^(2m(n))),

即，h_Y 独立且均匀地映射所有不同的 x,x^'。

这些函数很容易构造（Wegman and Carter 1981, Luby 1996）。

另请参阅

哈希函数

使用 探索

参考文献

Luby, M. Pseudorandomness and Cryptographic Applications. Princeton, NJ: Princeton University Press, 1996.Wegman, M. N. and Carter, J. L. "New Hash Functions and Their Use in Authentication and Set Equality." J. Comput. System Sci. 22, 265-279, 1981.

在 上被引用

通用哈希函数

请这样引用

Weisstein, Eric W. "通用哈希函数。" 来自 —— 资源。 https://mathworld.net.cn/UniversalHashFunction.html

主题分类