Complexity of subset product
- by threenplusone
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?
