求可自由选择周期的非加密伪随机数生成算法（免存储索引）

针对你需要直接生成置换索引、无存储需求、周期可控的需求，推荐这个带二次项的同余生成器，既保证全周期遍历所有索引，又能打破LCG的线性间距限制：

核心公式 #

X(n+1) = (a * X(n) + b * X(n)² + c) mod m

全周期条件（满足则序列遍历0~m-1每个值一次） #

• 若m是奇质数幂（如p^k，p为奇质数，k≥1）：
  • b与m互质
  • a ≡ 1 + 2b mod m
  • c与m互质
• 若m是2的幂（如2^k，k≥3）：
  • b为奇数
  • a ≡ 1 + 4b mod 8
  • c为奇数

伪代码实现 #

def permutation_prng(seed, m, a, b, c):
    x = seed % m
    while True:
        yield x
        x = (a * x + b * (x ** 2) + c) % m

适配你的需求点 #

• 无存储压力：仅需维护当前的x值，无需生成并存储整个索引数组
• 周期严格可控：满足条件时，序列周期恰好为m，每个索引仅出现一次
• 解决LCG间距问题：二次项的引入让相邻输出的差值不再是线性关联的固定模式，间距取值更分散，避免折线状的输出分布
• 实现简单：仅依赖基础算术运算，比洗牌算法轻量得多

如果觉得二次项计算麻烦，这个线性+逆元的组合方案更简洁，同样能规避LCG的线性缺陷：

核心公式 #

X(n+1) = (X(n) * a + inv(X(n) + 1)) mod m

注意事项 #

• m需为质数（保证非零数都有逆元）
• a选与m互质的数（比如3、5这类小质数）
• 初始种子避开m-1（避免X(n)+1 ≡0 mod m，无逆元）

伪代码实现 #

def mod_inv(x, m):
    # 质数模下的逆元计算，直接用快速幂
    return pow(x, m-2, m)

def inv_based_perm(seed, m, a):
    x = seed % m
    if x == m-1:
        x = (x + 1) % m  # 跳过无逆元的情况
    while True:
        yield x
        temp = (x * a + 1) % m
        x = (x * a + mod_inv(temp, m)) % m

这个方案的相邻输出差值由逆元项主导，随机性很强，周期接近m（允许种子偏差的情况下完全够用）

如果不想调整复杂的生成器结构，也可以在原有LCG的基础上，对输出做一次简单的非线性变换，比如：
X_out = (X_lcg ^ (X_lcg >> 2)) mod m
这样能快速打破LCG的线性间距模式，实现成本最低，同时保留LCG的全周期特性

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