如何从给定数列推导随机数生成器种子？何时难以找到该种子？

一、是否可以从输出序列反推初始种子？ #

可以，前提是已知伪随机数生成器（PRNG）的具体实现，且该生成器是确定性的（几乎所有常见PRNG都是如此，比如示例中的线性同余生成器LCG）。

这类PRNG的核心逻辑是：初始种子是唯一的状态起点，后续每一步的状态和输出都由前序状态通过固定算法推导而来。只要算法可逆，就能从输出序列逆向计算出每一步的状态，最终得到初始种子。

以你提供的示例代码为例：

int seed;
int myRand() // RAND_MAX assumed to be 32767
{
    seed = seed*1103515245 + 12345;
    return (seed/65536) % 32768;
}

// given numbers: 19098, -31546, 32637, 21910, -27300
// use reverse calculations to find seed 75235

int main() {
    
    seed = 75235;
    
    printf("%d\n", myRand()); // 19098
    printf("%d\n", myRand()); // -31546
    printf("%d\n", myRand()); // 32637
    printf("%d\n", myRand()); // 21910
    printf("%d\n", myRand()); // -27300

    return 0;
}

这个myRand()是标准LCG的变种（与glibc的rand()实现一致），状态更新公式为seed = seed * 1103515245 + 12345，输出是状态右移16位后取模32768的结果。已知输出序列时，我们可以通过逆向求解线性同余方程，一步步倒推出每一步的seed值，最终得到初始种子75235。

二、哪些情况难以找到对应种子？ #

• 生成器状态不可逆：如果PRNG的状态更新包含不可逆操作（比如输出仅保留状态的部分比特，且丢弃的比特无法通过输出或后续状态恢复），或者输出是状态的单向哈希结果，那么无法从输出反推状态，自然找不到初始种子。
• 序列长度不足，状态存在多解：当PRNG的状态空间远大于输出序列的信息量时，多个初始种子可能生成相同的前缀序列（碰撞）。比如状态是128位的生成器，每次仅输出32位，若只给2个输出值，会有大量种子满足条件，无法确定唯一解。
• 密码学安全PRNG（CSPRNG）：这类生成器的状态转移设计为计算上不可逆，即使已知实现，逆向求解初始种子的难度等同于破解加密算法，在合理时间内几乎不可能完成。
• 序列超出PRNG的周期：如果给定的序列长度超过了PRNG的周期，序列会进入循环，此时可能出现矛盾（同一位置出现不同输出），说明不存在对应的初始种子；或者循环后的序列无法对应唯一的初始状态。
• 生成器包含非线性操作：部分PRNG会引入非线性变换增强随机性，这类变换的逆向求解非常复杂，甚至没有解析解，只能通过暴力枚举，但当状态空间过大时（比如2^64以上），暴力枚举完全不现实。

内容的提问来源于stack exchange，提问作者Thomas B.