部分集合生成の複雑さ

Question

私は整数0 < x <を持つ次の公式を使用して生成された一連の数値を持っています。

f(x) = f(x-1)^2 % a 

= 649

{2, 4, 16, 256, 636, 169, 5, 25, 649, 576, 137, ...} 

で2から始まる例えば私が掛け合わさが1つのmod N.

に等しいとき、私はすることにより、この問題を信じることを、これらの数字のサブセット後にしていますそれ自身がNP完全である（Subset-Sum問題と類似している）。

ただし、任意の整数（x）で開始すると同じ解パターンが得られます。

例： A =

{2、4、、256、636、169、、25、649、576 、137、...} = 16 * 5 * 576 = 1％649 649
{3,9、、71、498、86、、500、135、、213、...} = 81 * 257 * 53 = 1％649
{4、 16,,636,169,5,,649,576, 、597、...} = 256 * 25 * 137 = 1％649

この問題がこの問題をより早く解決できるかどうかは疑問です。
誰か以前にこの問題に遭遇したことがありますか、それとも助言がありますか？

Answer 1

従ってf(x) = g^(2^x) % a（g=f(0)）。オイラーの定理を使って、1を得るために掛けるべきf(x)を見つけることができます。Euler's theoremはg^Phi(a) % a = 1（Phi(a) = Euler's totient function =整数の数は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とaが比較的素数であること以外は、g = f(0)の値には依存しません（そうでない場合、解決策はありません）。

あなたのケースでは、Phi(649) = 580 = 2^9 + 2^6 + 2^2ですので、f（2）、f（6）、f（9）を掛け合わせます。

Answer 2

サブセット製品の問題は同様にNPが完了証明し、これにさらに強い類似有する： http://www.wolframalpha.com/entities/famous_math_problems/subset_product_problem/oa/xp/7d/

サブセット和が擬似多項式時間で実際に解決可能であるが、Cの合計= O（NC）」 （例えば、649）。サブセット製品でも同様のことが可能かどうかはわかりません。