Thus, for each pair (q, r) ∈ [p]
2
, there is at most on e pair (a, b) ∈ [p]
2
satisfying (3) and (4). On
the other hand, (3) and (4) define a u n ique pair (q, r) ∈ [p]
2
for each pair (a, b) ∈ [p]
2
. We have p
2
pairs of each kind, so th e correspondence must be 1-1.
Since x 6= y, by Fact 2.1,
r = q ⇐⇒ a = 0. (7)
Thus, when we pick (a, b) ∈ [p]
+
× [p], we get r 6= q.
Returning to the proof of (2), we get a collision h
a,b
(x) = h
a,b
(y) if and only if q mod m =
r mod m. Let us fix q and set i = q mod m. There are at most ⌈p/m⌉ values r ∈ [p] wit h
r mod m = i and one of them is r = q. Therefore, the nu mber of r ∈ [p] \ {q} with r mod m =
i = q mod m is at most ⌈p/m⌉ − 1 ≤ (p + m − 1)/m − 1 = (p − 1)/m. However, there are
values of i
′
∈ [m] wit h only ⌊p/m⌋ values of q
′
∈ [p] with q
′
mod m = i
′
, and then the num ber
of r
′
∈ [p] \ {q
′
} with r
′
mod m = i
′
= q
′
mod m is ⌊p/m⌋ − 1 < ⌈p/m⌉ − 1. Summing over
all p values of q ∈ [p], we get that the number of r ∈ [p] \ {q} with r mod m = i = q mod m is
strictly l ess than p(⌈p/m⌉−1) ≤ p(p −1)/m. Then our 1-1 correspondence imp lies that there are
strictly less than p(p − 1)/m collision pairs (a, b) ∈ [p]
+
× [p]. Since each of the p(p − 1) pairs
from [p]
+
×[p] are equally likely, we concl u de that the collision probabil ity is st rictly below 1/m,
as claimed in (2).
Exercise 2.6 Suppose we for o ur hash functio n also consider a = 0, that is, for random (a, b) ∈
[p]
2
, we define the hash function h
a,b
: [p] → [m] by
h
a,b
(x) = ((ax + b) mod p ) mod m.
(a) Show that this function may n ot be universal.
(b) Prove t hat it is always 2-approximat el y universal, that is, for any distinct x, y ∈ [p],
Pr
(a,b)∈[p]
2
[h
a,b
(x) = h
a,b
(y)] < 2/m.
2.2.1 Implementation for 64-bit keys
Let us now consider the implementation of our hashing scheme
h(x) = ((ax + b) mod p) mod m
for the ty pical case of 64-bit keys in a s tandard imperative programming language such as C. Let’s
say the hash values are 20 bits, s o we have u = 2
64
and m = 2
20
.
Since p > u = 2
64
, we generally need to reserve more than 64 bits for a ∈ [p]
+
, so the product
ax has m ore than 128 bits. To compute ax, we now have the issue that multi plication of w-bit
numbers automatically discards overflow, returning only the w least significant bits of the produ ct .
However, we can get t he produ ct of 32-bit numbers, representi n g them as 64-bit numb ers, and
getting the full 64-bit result . We need at least 6 such 64-bit multiplications to compute ax.
Next issue is, how do we compute ax mod p? For 64-bit numbers we have a general mod-
operation, though it is rather slow, and here we have more than 128 bits.
5
剩余21页未读，继续阅读
weixin_38634323
- 粉丝: 7
- 资源: 899
我的内容管理
展开
最新资源
- JDK 17 Linux版本压缩包解压与安装指南
- C++/Qt飞行模拟器教员控制台系统源码发布
- TensorFlow深度学习实践：CNN在MNIST数据集上的应用
- 鸿蒙驱动HCIA资料整理-培训教材与开发者指南
- 凯撒Java版SaaS OA协同办公软件v2.0特性解析
- AutoCAD二次开发中文指南下载 - C#编程深入解析
- C语言冒泡排序算法实现详解
- Pointofix截屏：轻松实现高效截图体验
- Matlab实现SVM数据分类与预测教程
- 基于JSP+SQL的网站流量统计管理系统设计与实现
- C语言实现删除字符中重复项的方法与技巧
- e-sqlcipher.dll动态链接库的作用与应用
- 浙江工业大学自考网站开发与继续教育官网模板设计
- STM32 103C8T6 OLED 显示程序实现指南
- 高效压缩技术：删除重复字符压缩包
- JSP+SQL智能交通管理系统：违章处理与交通效率提升
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
