algorithm - 重复使用 (mod 2^32+1)

Question

其中 m = 2^32+1 = 641*6700417 mod 函数只不过是 32 位处理器上的一个减法。我不在乎复发
种子 = 种子*a%m
不是一个好的随机数生成器。我希望在加密算法中将它用作 32 位宽的 sbox。如果“a”的试验值会导致循环访问所有 2^32 值，是否有一种算法会返回 true？

假设这样的算法存在，我怀疑如果 a*b%m = 1 那么使用“b”的循环会向后运行。我怀疑是真的。我会使用“b”来实现逆 sbox。

我可以使用 mod (2^16+1) 做我要求的一切，但那个数字是素数。

Answer 1

Is there an algorithm that would return true if a trial value of “a” would cause the recurrence to visit all 2³² values?

是的，有:

return false;

最明显的原因是所有 2³² 个可能值的集合包括值零，并且循环卡在那里，所以它不是循环的。但即使您排除零，如果您从 641 的倍数开始，那么您将只会访问 641 的倍数，并且对于其他因素也是如此。

这种“访问所有值”属性仅在您对某个质数取模并排除零时才有效。