一、线性同余生成器 (LCG)
原理：
通过递推公式生成序列，公式为：
Xn+1=(aXn+c)mod mX_{n+1} = (aX_n + c) \mod mXn+1=(aXn+c)modm
其中aaa是乘数，ccc是增量，mmm是模数。随机性取决于参数选择（如 a=1103515245, c=12345, m=2^31）。
特点：
• 速度快，但周期较短（最大周期为mmm）。
• 低位随机性差，通常取高位输出。
Python 实现：
class LCG:
def __init__(self, seed, a=1103515245, c=12345, m=2**31):
self.state = seed
self.a = a
self.c = c
self.m = m
def random_int(self):
self.state = (self.a * self.state + self.c) % self.m
return self.state
def random_float(self):
return self.random_int() / self.m
# 使用示例
lcg = LCG(seed=42)
print(lcg.random_float()) # 输出：0.255...
二、梅森旋转算法 (Mersenne Twister)
原理：
基于一个 624 维的状态数组，通过移位和异或操作生成随机数。周期极长（219937−12^{19937}-1219937−1），且分布均匀。
特点：
• Python random 模块的默认算法。
• 适合科学计算，但状态空间大，不适合加密。
Python 示例：
import random
random.seed(42)
print(random.randint(1, 100)) # 输出随机整数
三、平方取中法
原理：
将当前数平方后取中间部分作为下一个数。例如，4位数 1234 平方为 1522756，取中间4位 5227。
缺点：
• 容易陷入短周期或退化到0。
Python 实现：
def middle_square(seed, digits=4):
seed = seed ** 2
seed_str = str(seed).zfill(2 * digits)
start = (len(seed_str) - digits) // 2
middle = seed_str[start:start + digits]
return int(middle) if middle else 0 # 处理全零情况
# 使用示例
n = 1234 # 必须为偶数位数
print(middle_square(n)) # 输出：5227
四、Xorshift
原理：
通过位运算（异或、移位）快速生成随机数。公式示例：
x←x⊕(x≪a)x \leftarrow x \oplus (x \ll a)x←x⊕(x≪a)
x←x⊕(x≫b)x \leftarrow x \oplus (x \gg b)x←x⊕(x≫b)
x←x⊕(x≪c)x \leftarrow x \oplus (x \ll c)x←x⊕(x≪c)
特点：
• 速度快，周期长（232−12^{32}-1232−1或更高）。
Python 实现（32位）：
class Xorshift32:
def __init__(self, seed=1):
self.state = seed & 0xFFFFFFFF
def random(self):
self.state ^= (self.state << 13) & 0xFFFFFFFF
self.state ^= (self.state >> 17)
self.state ^= (self.state << 5) & 0xFFFFFFFF
return self.state
# 使用示例
xorshift = Xorshift32(seed=42)
print(xorshift.random()) # 输出：2707161783
五、密码学安全随机数
原理：
使用加密学哈希函数（如 SHA-256）或加密算法（如 AES、ChaCha20）生成不可预测的随机数。
Python 实现：
import secrets
# 生成安全随机整数
print(secrets.randbelow(100)) # 输出 0-99 的整数
# 生成安全随机字节（可用于生成大整数）
random_bytes = secrets.token_bytes(4)
print(int.from_bytes(random_bytes, 'big'))
六、物理熵源
原理：
利用硬件噪声（如热噪声、鼠标移动）生成真随机数。例如 Linux 的 /dev/random。
Python 示例：
import os
# 使用操作系统熵源
random_bytes = os.urandom(4) # 生成4字节随机数据
num = int.from_bytes(random_bytes, byteorder='big')
print(num % 100) # 输出0-99的整数
总结对比
算法速度周期长度安全性应用场景LCG快较短（mmm）低简单模拟梅森旋转中等极长（219937−12^{19937}-1219937−1）低科学计算、游戏Xorshift极快长（232−12^{32}-1232−1）低实时生成密码学安全算法慢依赖熵源高加密、密钥生成物理熵源可变无限极高安全关键系统以下是使用 C 语言实现各类随机数生成算法的代码示例：
一、线性同余生成器 (LCG)
#include
#include
typedef struct {
uint32_t state;
uint32_t a;
uint32_t c;
uint32_t m;
} LCG;
void lcg_init(LCG *lcg, uint32_t seed) {
lcg->state = seed;
lcg->a = 1103515245;
lcg->c = 12345;
lcg->m = 0x7FFFFFFF; // 2^31-1
}
uint32_t lcg_next(LCG *lcg) {
lcg->state = (lcg->a * lcg->state + lcg->c) % lcg->m;
return lcg->state;
}
int main() {
LCG lcg;
lcg_init(&lcg, 42);
printf("LCG: %u\n", lcg_next(&lcg)); // 输出：1622650073
return 0;
}
二、梅森旋转算法 (Mersenne Twister)
#include
#include
#define MT_N 624
#define MT_M 397
typedef struct {
uint32_t state[MT_N];
int index;
} MersenneTwister;
void mt_init(MersenneTwister *mt, uint32_t seed) {
mt->state[0] = seed;
for (int i = 1; i < MT_N; i++) {
mt->state[i] = 0x6C078965 * (mt->state[i-1] ^ (mt->state[i-1] >> 30)) + i;
}
mt->index = MT_N;
}
void mt_twist(MersenneTwister *mt) {
for (int i = 0; i < MT_N; i++) {
uint32_t x = (mt->state[i] & 0x80000000) | (mt->state[(i+1)%MT_N] & 0x7FFFFFFF);
x = (x >> 1) ^ ((x & 1) ? 0x9908B0DF : 0);
mt->state[i] = mt->state[(i+MT_M)%MT_N] ^ x;
}
mt->index = 0;
}
uint32_t mt_next(MersenneTwister *mt) {
if (mt->index >= MT_N) mt_twist(mt);
uint32_t y = mt->state[mt->index++];
y ^= (y >> 11);
y ^= (y << 7) & 0x9D2C5680;
y ^= (y << 15) & 0xEFC60000;
y ^= (y >> 18);
return y;
}
int main() {
MersenneTwister mt;
mt_init(&mt, 42);
printf("Mersenne: %u\n", mt_next(&mt)); // 输出：1608637542
return 0;
}
三、平方取中法
#include
#include
uint32_t middle_square(uint32_t seed, int digits) {
uint64_t squared = (uint64_t)seed * (uint64_t)seed;
uint32_t mask = 1;
for (int i = 1; i < digits; i++) mask *= 10;
squared /= mask; // 右移 digits/2 位
squared %= (mask * 10); // 取中间 digits 位
return (uint32_t)squared;
}
int main() {
uint32_t seed = 1234;
for (int i = 0; i < 5; i++) {
seed = middle_square(seed, 4);
printf("Middle Square: %u\n", seed); // 输出序列：5227, 3215, 3362...
}
return 0;
}
四、Xorshift
#include
#include
typedef struct {
uint32_t state;
} Xorshift32;
void xorshift32_init(Xorshift32 *xs, uint32_t seed) {
xs->state = seed;
}
uint32_t xorshift32_next(Xorshift32 *xs) {
xs->state ^= xs->state << 13;
xs->state ^= xs->state >> 17;
xs->state ^= xs->state << 5;
return xs->state;
}
int main() {
Xorshift32 xs;
xorshift32_init(&xs, 42);
printf("Xorshift: %u\n", xorshift32_next(&xs)); // 输出：2707161783
return 0;
}
五、密码学安全随机数（Linux/Unix 实现）
#include
#include
#include
#include
#include
uint32_t secure_random() {
uint32_t num;
int fd = open("/dev/urandom", O_RDONLY);
if (fd == -1) {
perror("Failed to open /dev/urandom");
exit(1);
}
read(fd, &num, sizeof(num));
close(fd);
return num;
}
int main() {
printf("Secure Random: %u\n", secure_random()); // 输出真随机数
return 0;
}
六、物理熵源（Linux 实现）
#include
#include
#include
#include
uint32_t hardware_random() {
uint32_t num;
int fd = open("/dev/random", O_RDONLY);
if (fd == -1) {
perror("Failed to open /dev/random");
exit(1);
}
read(fd, &num, sizeof(num));
close(fd);
return num;
}
int main() {
printf("Hardware Random: %u\n", hardware_random()); // 阻塞直到熵足够
return 0;
}
编译与运行
将代码保存为 .c 文件，例如 lcg.c。使用 GCC 编译：gcc lcg.c -o lcg && ./lcg
其他算法同理。
关键说明
数据类型：
使用 uint32_t 和 uint64_t 确保位运算的准确性。
性能优化：
梅森旋转算法中的 mt_twist 函数会重构整个状态数组，建议批量生成随机数。
安全性警告：
LCG、梅森旋转和 Xorshift 生成的随机数 不可用于加密场景，密码学安全实现需依赖系统 API。
跨平台问题：
示例中的 /dev/urandom 和 /dev/random 仅适用于 Linux/Unix，Windows 需使用 BCryptGenRandom 或 RtlGenRandom。