Optimization-Factoring $ le_p $ decision-factoring

Question

最適化ファクタリング：
入力：$ n in mathbb {n} $
出力：$ n $のすべての主要な要因

意思決定：
入力：$ n、k in mathbb {n} $
出力：true iff $ n $には最大$ k $の主要な要因があります

決定の問題が多項式的に溶媒がある場合、多項式時間に最適化の問題を解決するにはどうすればよいですか？

Answer 1

$ n $でアルゴリズムの多項式を取得する必要があります。ここで、$ n = log n $は入力のサイズです。コース指数）。

与えられた dec(k, x) 意思決定の問題を解決するには、二分法を使用して$ x $の最小のプライム除数を見つけて、手順数を対数保持する手順を書きましょう。

sp(x):
  min = 2
  max = x - 1
  while (max >= 1 + min):
    k = floor ((min + max) / 2)
    if dec(k, x):
      max = k
    else:
      min = k + 1
  if x % (min + 1) == 0:
    return (min + 1)
  else if x % min == 0:
    return min
  else:
    return 1

上記の手順は呼び出します dec $ o（ log x）$ timesと$ x $を分割する最小の素数を見つけます。 1 存在しない場合。これで、次のファクタリング機能を簡単に定義できます。

factor(x):
  p = sp(x)
  if (p == 1):
    print x
  else:
    print p
    factor(x / p)

係数は$ log x $ times（$p≥2$）未満と呼ばれるため、通話の数 dec $ x $未満の値で$ log^2 x $の時間で制限されています。の複雑さの場合 dec 多項式ですか？ factor まだ多項式であり、$ n^2p（n）$で制限されています。

Answer 2

$ k $を操作することにより、決定版を使用して$ n $の係数を検索できます。最適化バージョンへの入力を考えると、$ 2 $、$ 3 $、...、$ sim sqrt {n} $以下のプライムファクターがあるかどうかを尋ねることができます。 $ k_ {1} $で最初の回答を得ると、それは前にイエスと言わなかったので、$ k_ {1} $は$ n $の係数でなければならないので、これを書き留めてから再び開始できます$ frac {n} {k_ {1}} $。

理想的には、最大$ sim sqrt {n} $までのプライムのみをテストするだけですが、最初に主要な要因にヒットするので、複合材料をテストするかどうかは関係ありません。コンポジットに対するはいの答え。

次に、個々の検索ごとに最大$ sqrt {n} $の決定問題で解決し、各ステップで（完了するまで）$ n $を$ frac {n} {2未満に減らします。 } $、したがって、ptime（たとえば、$ o（n^{c}）$ for constant $ c $）の決定問題を解決できる場合、$ o（n^{cのようなことをすべて実行できます。 +1/2} log n）$。