我有一组使用以下公式生成的数字，其中整数 0 < x <一个。
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
我想知道这个额外的事实是否能让这个问题更快地解决？
或者是否有人以前遇到过这个问题或有任何建议？
I have a set of numbers produced using the following formula with integers 0 < x < a.
f(x) = f(x-1)^2 % a
For example starting at 2 with a = 649.
{2, 4, 16, 256, 636, 169, 5, 25, 649, 576, 137, ...}
I am after a subset of these numbers that when multiplied together equals 1 mod N.
I believe this problem by itself to be NP-complete (based on similaries to Subset-Sum problem).
However starting with any integer (x) gives the same solution pattern.
Eg. 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
I am wondering if this additional fact makes this problem solvable faster?
Or if anyone has run into this problem previously or has any advice?
发布评论
评论（2）
所以 数量代码>）。因此，您只需计算
f(x) = g^(2^x) % a，其中g=f(0)。您可以使用欧拉定理找到一些f(x)相乘即可得到 1。欧拉定理指出g^Phi(a) % a = 1(Phi(a)= 欧拉 totient 函数 = 与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< /代码> mod <代码>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) 相乘。So
f(x) = g^(2^x) % a, whereg=f(0). You can use Euler's theorem to find somef(x)to multiply together to get 1. Euler's theorem states thatg^Phi(a) % a = 1(Phi(a)= Euler's totient function = # of integers< awhich are relatively prime toa). So you just need to computePhi(a), then decompose it into its bit representation and pick the appropriatexto set the bits that add together to makePhi(a).Perhaps an example would be clearer. Let
a = 54, thenPhi(a) = 18. Then18 = 2^4 + 2^1, sof(4) * f(1) = g^(2^4+2^1) = g^18 = 1moda.All that is straightforward, but you do need to compute
Phi(a). This is hard in general (equivalent to factoringa), but it can be easy if, for example, you know thatais prime.Note that this solution does not depend on the value of
g = f(0), other than the fact thatgandaare relatively prime (if they aren't, then there aren't any solutions).In your case,
Phi(649) = 580 = 2^9 + 2^6 + 2^2, so you multiply together f(2), f(6), and f(9).子集乘积问题也被证明是 NP 完全问题，并且与此有更强的相似性：
http://www.wolframalpha.com/entities/known_math_problems/subset_product_problem/ oa/xp/7d/
子集和实际上可以在伪多项式时间内求解，O(nC)，其中 C = 总“权重”（例如 649）。我不知道子集产品是否可以实现类似的效果。
The subset product problem is proven NP complete as well, and has an even stronger resemblance to this:
http://www.wolframalpha.com/entities/famous_math_problems/subset_product_problem/oa/xp/7d/
Subset sum is actually solvable in pseudo polynomial time, O(nC) where C = The total "weight" (eg 649). I don't know if a similar thing is possible with subset product.