难以了解证明中的几个步骤：“\ mathscr {h} _ {p，m} $的哈希函数是通用的”

Question

我正在通过cormen等来通过文本介绍算法。 al。在我遇到以下摘录关于上述证明的摘录以及我感受到困难的步骤，其中包含 $ \ dagger $ 和 $ \匕首\匕首分别为$ 。

设计通用类散列函数

$ p $ 是一个足够大的素数，使每个可能的键 $ k $ 范围 $ 0 $ 到 $ p - 1 $ ，包含。让 $ z_p $ 表示set $ \ {0,1，...，p - 1 \} $ ，让 $ z_p ^ * $ 表示set $ \ {1,2，...，p - 1 \} $ 。因为假设键的宇宙大小大于哈希表中的Slots $ m $ 我们有 $ p> m $ 。

我们现在定义哈希函数 $ h_ {a，b} $ 对于任何 $ a \在z_p ^ * $ 和任何 $ b \在z_p $ ：

$ h_ {a，b}=（（a.k + b）\ mod p）\ mod m $ 。

所有这些散列函数的家庭：

$$ \ mathscr {h} _ {p，m}={h_ {a，b}：a \在z_p ^ *，b \中z_p \} $ $

---

定理：类 $ \ mathscr {h} _ {p，m} $ 散列函数是通用的。

---

证明：

考虑两个不同的键 $ k $ 和 $ l $ 从 $ z_p $ ，使 $ k \ neq l $ 。对于给定的哈希函数 $ h_ {a，b} $ 我们让

$$ r=（ak + b）\ mod p $$ ，

$$ s=（al + b）\ mod p $$ 。

我们首先注意到 $ r \ neq s $ 。为什么？观察

$$ r - s= a（k - l）（\ mod p）$$ 。

遵循$г\ neqs $ 因为 $ p $ 是prime和两个 $ a $ 和 $（k - l）$ 是nonzero modulo $ p $ ，因此它们的产品也必须是非零Modulo $ p $

因此，在计算任何 $ h_ {a，b} $ 中的 $ \ mathscr {h} _ {p，m} $ ，不同的输入 $ k $ 和 $ l $ 映射到不同的值 $ r $ 和 $ s $ modulo $ p $ ; “Mod P级别”还没有碰撞。此外，每个可能的 $ p（p-1）$ 选项中的每一个 $（ a，b）$ 使用 $а\ neq 0 $ 产生不同的结果对 $（r，s ）$ 使用 $ r \ neq s $ ，因为我们可以解决 $ a $ $ b $ 给定 $ r $ 和 $ s $ $ ^ \ dagger $ ：

$$ a=（（r - s）（（k - l）^ {-1} \ mod p））\ mod p $$ ，< / p>

$$ b=（r - ak）\ mod p $$ ，

其中 $（（k - l）^ {-1} \ mod p）$ 表示 $ k - l $ 。由于只有 $ p（p-1）$ 可能对 $（r，s）$ $г\ neqs $ ，对 $（a，b）$ 带 $ a \ neq 0 $ 和对 $（r，s）$ with $ r \ neq s $ 。因此，对于任何给定对输入<跨度类=“math-container”> $ k $ 和 $ l $ ，如果我们选择 $（a，b）$ 从 $ z_p ^ * \ times z_p $ ，结果对 $（r，s）$ 同样可能是任何一对不同的值Modulo p。

然后它遵循不同键 $ k $ a的概率

nd $ l $ 碰撞等于 $ r r \ seciv s（\ mod m）$ 的概率当<跨度类=“math-container”> $ r $ 和 $ s $ 被随机选择为不同的值modulo $ P $ 。 为 $ r $ ， $ p - 1 $ $ s $ 的可能剩余值，值 $ s $ 这样 $ s \ neq r $ 和 $ s \ seciv r（\ mod m）$ 最多 $ ^ {\ Dagger \ Dagger} $

$$ \ lceil p / m \ rceil - 1 <（（p + m-1）/ m） - 1 $$ $$=（p-1）/ m $$ 。

$ s $ 与 $ r $ 减少的modulo $ M $ 最多 $（（p - l）/ m）/（p-1）= 1 / m $ 。

因此，对于任何对不同的值 $ k，l \ z_p $ ，

$$ pr \ {h_ {a，b}（k）= h_ {a，b}（l）\} \ leq 1 / m $$

使 $ \ mathscr {h} _ {p，m} $ 确实是通用的。

---

疑惑：

我无法理解证明中的以下陈述：

$ \ dagger $ ：每个可能的 $ p（p-1）$ 对于该对的选择 $（a，b）$ 使用 $а\ neq 0 $ 产生不同的结果对 $（r，s）$ 使用 $ r \ neq s $ ，因为我们可以解决 $ a $ 和 $ b $ 给定 $ r $ < / span>和 $ s $

为什么，“我们可以解决 $ a $ 和 $ b $ 给定 $ r $ 和 $ s $ “ $ \意味着$ “可能的 $ P（P-1）$ 选项 $（a，b）$ 使用 $а\ neq 0 $ 产生不同的结果对 $（r，s）$ $г\ neq s $ “

---

$ \ dgragr \ dgager $ ：对于给定值 $ r $ ， $ p - 1 $ $ s $ 的剩余值，值 $ S $ 这样 $ s \ neq r $ 和 $ s \ Equiv R（\ mod m）$ 最多 $ \ lceil p / m \ rceil - 1 $ 。

如何获得术语 $ \ lceil p / m \ rceil - 1 $ ？

Answer 1

我们想显示，如果 $ k_1 \ neq k_2 \ in \ mathbb {z} _p $ 那么

$ \ pr \ limits _ {（a，b）\ in \ mathbb {z} _p ^ * \ times \ mathbb {z} _p} [ak_1 + b \ seciv ak_2 + b \ pmod m] \ le \ frac {1} {m} $ 。

在 $ \ mathbb {z} _p $ 中，两个加法和乘法都是预成型的。

我们首先显示，如果 $ a \ simu（z_p ^ *）$ 和 $ b \ sim u （Z_P）$ 然后所有 $ k_1 \ neq k_2 \ in \ mathbb {z} _p $ ， $（ak_1 + b，ak_2 + b）$ 通过 $ \ {（x，y）\ in \ mathbb {z} _p ^ 2 | $ （即 $ h（k_1）$ 和 $ h（k_2）$ 与具有不同条目的对共同均匀，其中随机性遍布 $ h $ ）。从所有 $（c_1，c_2）\ in \ mathbb {z} _p ^ 2 $ 带有 $ c_1 \ neq c_2 $ ，以下线性方程系统：

$ \ begin {align *} ＆ak_1 + b= c_1 \\ ＆ak_2 + b= c_2 \结束{align *} $

在变量 $（a，b）>中有一个唯一的解决方案在z_p ^ * \ times \ mathbb {z} _p $ 中。从第一个收益率 $ a（k_1-k_2）= c_1-c_2 $ 中减去第二个等式，因为 $ k_1-k_2 $ 是非零，我们可以通过它的反向乘以和获取 $ a=（k_1-k_2）^ { - 1}（c_1-c_2）$ 。如果 $ c_1 \ neq c_2 $ ，那么这是 $ a $ 的非零解决方案，我们可以从两个方程中的任何一个中提取 $ b $ 。因此，对于每对 $（c_1，c_2）$ with $ c_1 \ neq c_2 $ 有唯一 $（a，b）\在z_p ^ * times \ mathbb {z} _p $ 这样 $ \ big（ h_ {a，b}（k_1），h_ {a，b}（k_2）\ big）=（c_1，c_2）$ 。这解决了你的第一个问题。

现在，划分 $ \ mathbb {z} _p $ 进入 $ \ lceil p / m \ rceil $ 桶， $ b_1，...，b_ {l= lceil p / m \ rceil} $ 如下： $ b_1= {0,1，...，m-1 \}，b_2={m，m + 1，...，2m-1 \} $ ，...，<跨越类=“math-container”> $ b_l={m \ lfloor p / m \ rfloor，m \ lceil p / m \ rceil + 1，...，p-1 \} $ 。注意，除了最后一个大小的每个桶 $ m $ ，并且在同一桶中的任何两个元素都是等效的modulo $ M $ 。我们得出结论， $ \ {（x，y）\ in \ mathbb {z} _p ^ 2 |不同对的数量x \ neq y \} $ 是等效的modulo $ m $ 最多 $ p（\ lceil p / m \ rceil-1）$ ，自从选择第一个元素后，您将留下 $ \ lceil p / m \ rceil-1 $ 可供选择的元素（您必须选择不同的桶，每个桶提供大多数候选者）。回想一下， $ \ big（h_ {a，b}（k_1），h_ {a，b}（k_2）\ big）\ sim u（\ {（x，y）\在\ mathbb {z} _p ^ 2 | x \ neq y \}）$ ，所以我们最终可以得出结论：

$ \ pr \ limits _ {（a，b）\ in \ mathbb {z} _p ^ * \ times \ mathbb {z} _p} \ left [h_ {a， b}（k_1）= h_ {a，b}（k_2）\ pmod m \ rectle]=frac {p（\ lceil p / m \ rceil-1）} {p（p-1）} \ le \ frac {1} {m} $

注意，允许 $ a $ 拍摄值 $ 0 $ 只使我们的分析更容易现在 $ \ big（h（k_1），h（k_2）\ big）$ 与 $ \ mathbb { z} _p ^ 2 $ ，但是 $ \ frac {1} {p} $ 那个 $ a= 0 $ ，我们的哈希将是等效的modulo $ m $ ，所以在这种情况下，我们将不得不满足 $ o（\ frac {1} {m}）$ 碰撞概率绑定。