python源代码中冲突解决公式的一个难题

Question

我很抱歉在这里问这样的问题，尽管它看起来有点像数学问题。你知道吗

以下冲突解决公式出现在python源代码中，\pythoncore\Objects\dictobject.c

j = ((5*j) + 1) mod 2**i

对于范围（2*i）内的任何初始j，此公式的简要描述为，重复2*i次生成每个 int在范围（2*i）内正好一次。在一个 对于一张桌子来说，这个例子实在太小了，不足以说明这一点 大小2*3索引顺序为：

0 -> 1 -> 6 -> 7 -> 4 -> 5 -> 2 -> 3 -> 0 [and here it's repeating]

我的问题是如何证明这个公式的正确性。你知道吗

Answer 1

您所指的注释包含说明

see any text on random-number generation for proof

如果搜索一下，就会发现5*j+1 mod 2**i循环是linear congruential generator。线性同余发生器的形式如下

x_(n+1) = a*x_n + c (mod m)

对于非零c，线性同余生成元具有全周期（生成所有数mod m）当且仅当

1. c和m是相对素数
2. a-1可被m的所有素数因子整除，且
3. 如果m是4的倍数，那么a-1也是4的倍数。你知道吗

这就是赫尔-多贝尔定理。所有这些条件都适用于5*j+1 mod 2**i，因此循环将遍历哈希表中的所有条目。你知道吗

赫尔-多贝尔定理的充分证明可以在here中找到。你知道吗