有界2次合同問題に関する解明

Given: 3 positive integers $a, b, L$.
Problem: Is there a positive integer $x < L$
such that $x^2 equiv a (mod b)$?

The above problem is NP Complete (as mentioned in G&J) even
if we have the factorization of $b$ given. My query is the
following:

残余$ a $の総発生数が多項式で決まるという約束/条件が課されていると仮定しよう。 $ b $の素因数の数、すなわち$ a
$の発生数は常に$ {pct} ^ C $より小さい。

$ pct $ = $ b $、$ C $ =正の整数定数の素因数の数。

この問題は依然としてNP完結のままであるか、それともP時間解決可能になるか。

本質的に、残渣が発生する回数は、この問題を困難にする原因であるか、それとも重要ではないか、それは$ b
$の素因数の数に依存するだけですか?

ベストアンサー

最初の問題の NP – 完成はMandersとAdleman [1]が
3-SAT
からの削減を使って証明されました。それらの削減は間違いです。したがって、(素因数の数は入力$ n
$の長さによって上限が定められていることを考慮して、M-A削減では少なくとも$ n ^ ε$です)問題は<
strong>約束]を選択します。 Valiant-Vaziraniによると、
promise-UP は無作為多項式時間短縮の下では NP です
– したがって、 promise-FewP 。したがって、問題は基本的に
NP と同じくらい難しいです。

EDIT: The answer above assumes that in the question, the unclear
phrase “the number of occurrences of $a$” means the number of
residues $xtotal number of residues mod $b$ that square to
$a$. In the latter case, the problem is solvable in
promise-ZPP: using the factorization of $b$, just
compute all possible square roots of $a$ modulo $b$ by the usual
algorithm (Tonelli–Shanks + Hensel’s lifting + Chinese remainder
theorem).

リファレンス:

[1] Kenneth L. MandersとLeonard M. Adleman、 NP完成
  バイナリ2次方程式の決定問題
、Journal of Computer and System
  Sciences 16(1978)、no。 2、pp.168-184。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です