设U为由取自Zp中值构成的n元组集合，并设B=Zs...

[问答题]

设U为由取自Z_p中值构成的n元组集合，并设B=Z_p，其中p为素数。对于一个取自U的输入元组<a₀,a₁,...,a_n-1>，定义其上的散列函数h_b： $U\rightarrow B(b\in Z_{p})$ 为：

$h_{b}(<a_{0},<a_{1},...,<a_{n-1}>)=(\sum_{j=0}^{n-1}{a_{j}b^{j}})mod p$

并且设 $H=\left\{ h_{b}:b\in Z_{p} \right\}$ 。根据以下定义，证明H是（(n-1)/p）全域的。

定义：一个从有限集合U到有限集合B上的散列表簇H为 $\epsilon$ 全域的，如果对U中所有的不同元素对k和l，都有

$Pr{h(k)=h(l)}\leq \epsilon$

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

上传者：小小

难度：

0条回答 0收藏 289浏览

扫一扫，把题目装进口袋