# 随机数
# 简介
随机数在计算机领域，尤其在密码学领域，有非常重要的应用。
随机是自然界中很常见但又并不容易理解清楚的概念。比如抛一个硬币，正面或者背面向上的概率理论上各是 1/2。这个貌似是随机的，但是如果我们可以精确观测到抛出的初速度、角度、空气阻力等所有初始化条件，在宏观低速物体上(不讨论量子物理)，是可以提前计算出最后落地的正面还是背面，那这个还算随机吗？如果我做一个非常精妙的机器和实验环境，确保每次的抛出的时候的变量都精确，理论上一定可以保证每次都抛出正面。在物理界中，甚至对有没有真随机，都还是争议，但在数学里，还是给“真”随机数下了一个定义：
# 定义
比如对于符合 0 1 二项分布的数列这样定义，假设有一个无穷数列，假设你拥有无穷时间和无穷算力，也无法通过研究前 n 项的分布规律，使得你预测 n+1 项的概率大于或小于 1/2。
用极限表述就是假设有一个抛硬币游戏，对任意小的
这里强调一下，大于或小于 1/2, 如果下次猜对的次数小于 1/2，表示猜错的概率大于 1/2，这也不是真随机。
这个定义在工程上其实没有可用性，我们既没有无穷的时间，也没有无穷的算力。所以我们产生随机数，特别是用软件产生的随机数，只能尽量去接近这个标准，而无法达到这一标准。事实上，
目前没有数学证明表示密码学安全的伪随机数生成器是确实存在的。其存在性证明涉及到
# 计算机测试
随机的测试用例并不好写，因为这个问题定义就很难。我们一般的测试方式是通过大量的统计实验，计算均值和方差。概率论的知识这里暂不展开。有个终极测试方式叫柯尔莫哥罗夫-斯米尔诺夫检验 (opens new window) 简称 KS 测试，有兴趣的可以了解。
有意思的逻辑是，一个随机算法，如果 100% 通过了随机测试，那说明它的结果是可以预测的，就不是随机算法。
# 计算机实现
首先我们要了解一个事实，现在的所有计算机架构，是无法产生真随机数的。未来基于量子原理的量子计算机可以产生符合量子物理定义的“真随机”，但目前离实用还非常遥远。
计算机的输入和输出一定是确定的。JS 里能让程序执行结果每次不确定的，无外乎 Math.random、系统时间(Date.now, performance.now 等)、硬件输入(鼠标坐标等)、I/O (接口返回，数据读取)。而其余这些都是外设，不是计算机本身。
最早冯诺依曼用了一个现在看上去粗糙甚至错误的方式生成随机数:平方取中法。比如以 1234 做种子(seed)，算一下它的平方是 1522756，在左边填充 1 个 0，变成 01522756，然后他把中间四个数字输出作为随机数，就是 5227，然后再对 5227 做平方，以此类推...
由于代码写出来一定是无法数学意义保密的，我们通过老冯的递推公式，和前 N 项的值，只要倒推出 seed = 1234，那我们就可以预测未来任一项的“随机数”了。
然而事实上是，老冯的方法至今仍在使用，我们一直还在使用老冯的思路。所以随机数生成的安全，完全依赖于攻击者能不能在有限步下通过前 N 项找到 seed。
这回到了一个很吊诡的问题：我们要写一个随机函数，首先要有一个随机的 seed，它不能硬编码在代码里，也不能有规律可循。
在一般不严格的场景，我们可以使用当前系统时间做为 seed，但这在分布式系统里是不安全的，比如双 11 ，很多人都在抢 0 点，根据抽屉原理 (opens new window)毫秒级碰撞的可能性 100%。更严格的场景，我们需要使用物理世界的一些熵来做种子，比如用户的鼠标轨迹、电流的扰动、原子的衰变等。
# JS 实现
const random = () => {
return seed
}
是的，你没看错，最简单的随机函数就是直接返回 seed，只要保证每次从物理世界拿到的 seed 都是随机的，那 random 就是随机的。计算机里使用的伪随机，归根到底，不过是出于性能优化，并使工程应用上让随机数分区满足一定规则，比如区间，以及概率分布(如正态分布、泊松分布）。
目前工程上使用的 random 函数，多使用线性同余(LCG)算法 (opens new window)，这是一个简单高效的生成伪随机数方法。
比如设 a = 2, c = 9，m = 11 ，种子我们选择 1，那么依次生成的随机数是如下这个数列
const random = (x) => {
const a = 2
const c = 9
const m = 11
return (a * x + c) % m
}
const seed = 1
let arr = []
for (let i = 0 ; i < 10; i++){
arr.push(random(arr.length === 0 ? seed : arr[arr.length -1]))
}
console.log(arr)
// [0,9,5,8,3,4,6,10,7,1]
你可以运行这段代码，然后你会发现再继续下去，会呈现出周期性。对于伪随机算法，使周期尽可能大是必须要具备基础条件。对于 a, c, m 这三个魔术数字，取数有一定讲究 (opens new window) 。IBM 就曾经因为在自己的算法中魔术数字选取不佳，使得在统计学上失败，并使 70-90年代很多使用这个算法的科研结果被认为不可靠。足见写一个好的随机算法之难。
上面这个 JS 写得不够优雅，可以使用闭包或 generator 改造，但不是本文重点。Python 里，提供了自定义 seed 的功能，这个在做一些训练调参的时候很有用，能使得多次执行结果一致。JS 没有开放指定 seed 功能，想在年会抽奖代码里用真随机种子 (opens new window)装个 13，还得用 Python。另外 JS 的 random 返回
# 安全
LCG 算法并不安全，只是高效，密码学上的安全性算法，需要更高级的数学理论，比如基于梅森素数 (opens new window)的梅森旋转算法 (opens new window)。这一块我也不懂，不敢乱讲。
数学家要做的事，就是要找到一个通项公式，公式完全对你公开，但要推出 seed，需要难度超出攻击的成本。使得一个安全问题等价于一个数学难题，难到可以拿菲尔兹奖的难度，或者暴力破解超过宇宙热寂的时间复杂度，或者存储空间超过宇宙总粒子的空间复杂度。