Сложность подмножества продукта

Question

У меня есть набор чисел, созданный с использованием следующей формулы с целыми числами 0

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

Например, начиная с 2 с = 649.

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

Я после подмножества этих чисел, которые при умножении вместе равняются 1 мод N.

Я считаю, что эта проблема сама по себе является NP-полной (на основе сходства с проблемой Subset-Sum).

Однако начало с любого целого числа (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

Интересно, делает ли этот дополнительный факт решение этой проблемы быстрее?
Или, если кто-то сталкивался с этой проблемой ранее или есть какие-либо советы?

Answer 1

Так f(x) = g^(2^x) % a, где g=f(0).Вы можете использовать теорему Эйлера, чтобы найти несколько f(x), чтобы умножить их вместе, чтобы получить 1. Теорема Эйлера утверждает, что g^Phi(a) % a = 1 (Phi(a) = функция тока Эйлера = # целое число < 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 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).

Answer 2

Проблема с подмножеством продукта также доказана завершенной, и имеет еще большее сходство с этим: http://www.wolframalpha.com/entities/famous_math_problems/subset_product_problem/oa/xp/7d/

Сумма подмножества фактически разрешима за псевдополиномиальное время, O (nC), где C = общий «вес» (например, 649). Я не знаю, возможно ли подобное с подмножеством продукта.