Complexity of subset product

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, ...} = 1开发者_JAVA技巧6 * 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?

So f(x) = g^(2^x) % a, where g=f(0). You can use Euler's theorem to find some f(x) to multiply together to get 1. Euler's theorem states that g^Phi(a) % a = 1 (Phi(a) = Euler's totient function = # of integers < a which are relatively prime to a). So you just need to compute Phi(a), then decompose it into its bit representation and pick the appropriate x to set the bits that add together to make Phi(a).

Perhaps an example would be clearer. Let a = 54, then Phi(a) = 18. Then 18 = 2^4 + 2^1, so f(4) * f(1) = g^(2^4+2^1) = g^18 = 1 mod a.

All that is straightforward, but you do need to compute Phi(a). This is hard in general (equivalent to factoring a), but it can be easy if, for example, you know that a is prime.

Note that this solution does not depend on the value of g = f(0), other than the fact that g and a are 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).

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.