可双向遍历且支持游标值重掷的伪随机数发生器需求

核心需求回顾 #

• 生成周期近乎无限的伪随机序列
• 支持双向遍历：游标可前后移动，序列对应更新
• 支持重掷游标指向的数值：修改后永久保留，不影响序列其他元素

对可逆LFSR方案的问题分析 #

你提到的可逆LFSR确实能实现双向步进，但存在本质局限：LFSR的序列生成依赖抽头的线性反馈，修改中间比特会通过反馈链路影响整个序列的前后生成逻辑。即使限制修改非抽头位，非边缘抽头的可逆LFSR实现难度极高，且会大幅降低重掷操作的灵活性，因此这个方案并不适配你的需求。

可行替代方案 #

方案1：基于可逆哈希的带修改表PRNG #

核心逻辑

用双射（可逆）哈希函数构建序列的双向映射，同时维护一个修改表记录被重掷的位置：

1. 周期保障：选择大状态空间的可逆哈希（比如256位），周期可达2^256，完全满足“近乎无限”的要求。
2. 双向遍历：利用哈希的正向计算（下一个状态）和逆向计算（上一个状态）实现游标前后移动。例如基于AES的加密/解密就是天然的可逆双射：正向用AES加密得到下一个状态，逆向用AES解密得到上一个状态。
3. 重掷操作：当需要修改游标位置的数值时，生成新的伪随机数替换该值，并将当前状态的唯一标识（比如状态的哈希值）和新值存入修改表。后续遍历到该状态时，优先读取修改表中的值，而非哈希生成的原始值。

实现步骤

• 初始化：设定初始状态S0，定义正向函数F(S)（如AES加密）和逆向函数F_inv(S)（如AES解密），输出值为V = truncate(F(S), 所需位数)。
• 向前步进：S_current = F(S_current)，输出对应V（若在修改表中则取修改后的值）。
• 向后步进：S_current = F_inv(S_current)，输出对应V（若在修改表中则取修改后的值）。
• 重掷：生成新的V_new（可通过独立PRNG或当前状态的变种哈希生成），将S_current作为键、V_new作为值存入修改表，游标保持在当前位置，状态不变。

方案2：基于块密码的索引式双向PRNG #

核心逻辑

将游标位置的索引作为块密码的输入，利用块密码的可逆性实现双向遍历：

1. 周期保障：用128位或256位的索引值，周期可达2^128或2256，满足需求。
2. 双向遍历：向前步进时索引i += 1，向后步进时i -= 1，用块密码加密索引i得到伪随机数V_i。
3. 重掷操作：维护一个以索引i为键的修改表，存储重掷后的V_new，遍历到该索引时优先使用修改表的值。

优势

块密码（如AES）的安全性和可逆性经过充分验证，实现简单，步进和重掷操作的时间复杂度均为O(1)。

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