如何以亚指数算法查找2^128规模256位序列的重复值索引

现有支持实时计算序列下一个值、上一个值的迭代函数，生成的序列总长度为2¹²⁸，每个元素为256位数值：

• 序列中仅1个值重复出现2次，其余所有值全局唯一
• 全量存储序列需要2¹²⁸ × 256位空间，存储开销完全无法落地
• 需求：定位两个重复值对应的从序列起始位置计数的索引

已尝试的无效/低效方案 #

1. XOR校验方案 #

尝试对序列所有值逐次做XOR生成校验值识别重复项，示例代码如下：

a=[755,167,986,343,566,996,245,343]
crc=a[0]
for i in range(1,len(a)):
    crc=crc ^ a[i]

方案缺陷：重复值在XOR运算中会直接抵消，最终结果等价于对去重后序列做逐次XOR，完全无法识别重复项。以上述示例为例，重复值为343，对应1基索引#4、0基索引3，但最终XOR结果和序列[755,167,986,566,996,245]的XOR结果完全一致。

2. 双层倒序遍历方案 #

当前已实现的最优方案为双层倒序遍历：外层从序列尾部向前迭代x1，内层从当前外层遍历位置向后迭代x2，比对值是否相等查找重复，代码如下：

for i in range(maxX,1,-1):
    crc=crc^x1
    for j in range(i+1,maxX):
        if(x1==x2):
            break
        x2 = f(x2)# 正向迭代x2，等价于f(x2,+1)
    x1=f(x1) # 反向迭代x1，等价于f(x1,-1)

方案缺陷：时间复杂度为O(N²)，对于N=2¹²⁸的序列完全不具备可执行性。

已知序列迭代函数的输出示例：f(x1)=13082069741720843297365566874415150979823939205374148607908286415326657186361，实现语言无限制，Python/C/JavaScript/PHP/汇编均可，需要效率最优的重复值查找方案。

如果迭代函数f是无特殊代数结构的伪随机生成函数，经典计算模型下不存在亚平方根时间复杂度的算法，生日悖论给出的问题复杂度下界为Ω(2⁶⁴)，任何经典算法都不可能突破这个下界。

目前工程上可落地的最优方案是Van Oorschot-Wiener并行碰撞搜索算法，具体说明如下：

1. 算法核心基于生日悖论设计，期望时间复杂度为O(2⁶⁴)，空间复杂度为O(2⁶⁴ / k)（k为并行计算节点数），计算速度随并行节点数线性提升，是目前针对这类固定长度单碰撞序列查找的最优公开算法。
2. 实现逻辑：
   • 从序列起点和多个随机选择的索引位置出发，用f做正向迭代，每迭代固定步数就存储当前值和对应的索引，生成若干“标识点”
   • 当两个不同迭代路径生成同一个标识点时，回溯两个路径的交点，即可定位重复值的位置
   • 配合已实现的反向迭代函数，可以快速回溯路径交点，不需要存储完整迭代路径
3. 工程优化点：
   • 不要使用单一XOR作为校验值，可以搭配模257位素数的和、平方和校验，快速过滤非碰撞的相同标识点，避免误判
   • 可以根据硬件资源调整标识点的存储间隔，在内存占用和计算量之间做权衡：比如每迭代2²⁰步存一个标识点，只需要2⁴⁴左右的存储空间，配合消费级硬件集群就可以在可接受的时间内跑完计算
   • 如果确认f函数存在可利用的代数结构（比如线性同余、椭圆曲线映射等特殊结构），可以进一步把复杂度降到多项式级别，但从给出的输出示例来看，f大概率是类哈希的伪随机函数，不存在通用的代数破解方式。

补充说明：弗洛伊德龟兔赛跑环检测算法虽然空间复杂度为O(1)，但时间复杂度为O(N)=O(2¹²⁸)，计算量远大于Van Oorschot-Wiener算法，完全不具备落地可行性。小步大步法（Baby-step Giant-step）虽然也是O(2⁶⁴)时间复杂度，但空间复杂度固定为O(2⁶⁴)，无法做并行加速和时空权衡，工程效率远低于Van Oorschot-Wiener方案。

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