我有一组使用以下公式生成的数字，其中整数 0 < x < a。
f(x) = f(x-1)^2 % a
例如，从 2 开始，a = 649。
{2, 4, 16, 256, 636, 169, 5, 25, 649, 576, 137, ...}
我想要的是这些数字的子集，当它们相乘时等于 1 mod N。
我相信这个问题本身是 NP 完全的(基于与子集和问题的相似性)。
但是，从任何整数 (x) 开始都会给出相同的解决方案模式。
例如。 a = 649
{2、4、16、256、636、169、5、25、649、576、137、... } = 16 * 5 * 576 = 1 % 649
{3、9、81、71、498、86、257、500、135、53、213、...} = 81 * 257 * 53 = 1 % 649
{4、16、256、636、169、5、25、649、576、137、597、...} = 256 * 25 * 137 = 1 % 649
我想知道这个额外的事实是否可以更快地解决这个问题？
或者是否有人以前遇到过这个问题或有任何建议？
最佳答案
所以f(x) = g^(2^x) % a ，其中g=f(0) 。您可以使用欧拉定理找到一些 f(x)相乘得到 1。 Euler's theorem指出g^Phi(a) % a = 1 ( Phi(a) = Euler's totient function = 与 < a 互质的整数 a 的数量)。所以你只需要计算Phi(a) ，然后将其分解为其位表示形式并选择适当的 x设置加在一起形成 Phi(a) 的位.
也许举个例子会更清楚。让a = 54 ，然后Phi(a) = 18 。然后18 = 2^4 + 2^1 ，所以f(4) * f(1) = g^(2^4+2^1) = g^18 = 1模组a .
所有这些都很简单，但您确实需要计算 Phi(a) 。一般来说，这很困难(相当于因式分解 a )，但如果您知道 a ，那么这可能会很容易。是质数。
请注意，此解决方案不依赖于 g = f(0) 的值，除了 g和a是相对质数(如果不是，则没有任何解)。
就您而言，Phi(649) = 580 = 2^9 + 2^6 + 2^2 ，因此将 f(2)、f(6) 和 f(9) 相乘。
关于math - 子集积的复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4577606/