050 Applications of Congruences
Hashing Functions
我们经常使用 作为哈希函数。简答，计算快，每一个可能性都会覆盖到。
如果多个 计算的 相同，称为碰撞（collision）。解决冲突有很多方式，最简单的线性扫描法。 从 0 开始到 ，按照 找下一个空位。
Pseudorandom Numbers
系统方法产生的随机数不是真随机，所以成为伪随机数（pseudorandom numbers）。
最常用的伪随机数生成方法是线性同余法（linear congruential method）。我们选择四个数：模 ，倍数 ，增量 和种子 ，生成随机数公式是
有的时候，我们使用 的线性同余法，此时，我们称之为纯乘法生成器（pure multiplicative generator）。
线性同余法被用于很多任务，不过它生成的随机数不满足某些随机数统计属性。因此，在一些对随机数要求比较高的任务中，需要使用其他随机数生成方法。
Check Digits
例 奇偶校验比特（Parity Check Bit） 任意一串数据有 个比特，我们会增加第 位使得
如果检验位错了，那么数据不正确。不过即使检验位是对的，也不代表数据是正确的，比如有偶数个比特发生了反转。
例 通用产品代码（Universal Product Code, UPC） 一般有 12 位，第一位是产品类别，接下来五位是生产商，再接下来五位指定产品，最后一位是检验位。这些数字满足
例 国际标准书号（International Standard Book Number, ISBN） 一般有 ISBN-10 和 ISBN-13 两种。下面分析 ISBN-10。十个数字，最后一个可能是 10，用 X 表示，这些数字满足
常见的错误有单个数字错误（single error）和置换错误（transposition error），两个不同数字交换了位置。任意一种校验码都希望能校验出这些错误，甚至是其他类型的错误。下面考察 ISBN 和 UPC 的能力。
假定新的 ISBN 是 ，假定第 位出粗了，那么 且 ，其中 ，那么 因为 ，所以 。因此 不是合法的 ISBN。
现在来看置换错误，假定第 位置交换，那么 ，其余有 ，那么 原因类似，，所以 不是合法的 ISBN。
对于 UPC 而言，单个数字的错误与原来 UPC 的差值是 或者 ，因为 ，所以不是合法的 UPC。
对于交换错误，如果交换都在奇数位置或者都在偶数位置的两个值，前面的系数都是一样的，和不变，所以同余性质不变，无法检测。如果交换奇数和偶数位置的值，比如 变成了 ，那么和的差值是 ，如果差值是 5，那么能够整除 10，无法检测错误。