C语言中rand()%N与整数算术方法的优劣对比及缺陷解析

让我一步步拆解你的问题，把这两种随机数生成方式的差异讲得明明白白：

一、rand()%N的核心劣势 #

首先得先搞懂rand()的常见实现：绝大多数标准库的rand()用的是线性同余生成器（LCG），公式大概是next = (a * current + c) % m，其中m通常是2的幂（比如2^32）。这种实现天生有两个致命问题，会被rand()%N放大：

1. 低位序列完全不随机 #

LCG的低位循环周期极短，比如最低位可能每2次生成就循环0→1→0→1，次低位可能每4次循环，以此类推。当你用rand()%N时，结果的低位直接继承了这种强相关性——比如rand()%5的结果，其最低位会严格交替0和1，任何人只要看到前一个结果，就能100%预测下一个结果的最低位，完全没有随机性可言。

2. 分布严重偏差 #

当RAND_MAX + 1不能被N整除时，rand()%N会导致某些数值出现的概率显著高于其他值。举个简单例子：假设RAND_MAX=3（简化模型），N=3，那么rand()的可能结果是0、1、2、3，对应rand()%3的结果是0、1、2、0——这意味着0出现的概率是2/4，而1和2只有1/4，偏差非常明显。

3. 完全不适合密码学 #

因为LCG的参数是公开的（比如glibc的rand()参数是公开的），只要拿到几个连续的rand()结果，就能反推出种子，进而预测所有后续结果。加上rand()%N暴露了低位的强规律，攻击者能更快破解，所以绝对不能用于密码学场景，最多只能用于对随机性要求极低的游戏（比如随机掉落道具，玩家不会去刻意预测）。

二、整数算术方法为什么更优？ #

这里说的整数算术方法，指的是用宽整数乘法做范围映射的写法，比如：

uint32_t rand_range(uint32_t N) {
    return (uint64_t)rand() * N / (RAND_MAX + 1ULL);
}

它的优势刚好命中rand()%N的痛点：

• 规避低位问题：通过64位乘法把rand()的高位信息（LCG中高位的随机性远好于低位）充分利用起来，再做除法映射到0~N-1的范围，结果的低位不再有明显的循环规律。
• 分布更均匀：这种方法本质是把rand()的整个取值范围（0~RAND_MAX）均匀划分成N个区间，每个区间对应一个结果，只要RAND_MAX足够大，每个结果的概率差异可以忽略不计，几乎完全均匀。

三、如何验证这些说法？ #

你可以自己写个简单的C程序来验证，几个核心测试方向：

1. 低位随机性测试 #

生成100000个rand()结果，统计最低位的0/1出现次数，再看连续结果的低位序列——你会发现0和1严格交替（或者非常接近交替）。再用整数算术方法生成同样数量的结果，统计低位的0/1比例，你会发现比例接近50%，且序列没有明显的循环规律。

2. 分布均匀性测试 #

比如选N=7（一个不能整除RAND_MAX+1的数），生成1000000个rand()%7的结果，统计每个数出现的次数——你会发现某些数的出现次数比平均值（约142857）多几百次。再用整数算术方法测试，每个数的出现次数会非常接近平均值，差异在几十以内。

3. 可预测性测试 #

如果你能找到LCG的参数（比如glibc的rand()参数是a=1103515245, c=12345, m=2^31），拿到3个连续的rand()结果，就能反推出种子，然后完美预测后续所有rand()%N的结果。而整数算术方法虽然基于同样的rand()，但结果的高位信息被保留，攻击者需要更多样本才能破解，难度稍高（当然，rand()本身就不适合密码学，这个方法只是比rand()%N好一点）。

四、低位非随机性对PE的影响 #

这里的PE应该是指概率误差（Probability Error）或者模式熵（Pattern Entropy）：

• 如果是概率误差：rand()%N的PE会非常大，因为分布不均匀，某些结果的概率偏离理论值很多；而整数算术方法的PE接近0，几乎可以忽略。
• 如果是模式熵：rand()%N的低位序列熵极低（比如最低位的熵是1比特，完全可预测），整体序列的熵远低于真正的随机序列；整数算术方法的序列熵更高，更接近理想随机序列的熵值。

内容的提问来源于stack exchange，提问作者myradio