$ NC $階層の素数ですか?

AKSの素数性テストは、与えられた整数が$ P $で素数であるかどうかを解きます。 AKSアルゴリズムは次のとおりです。

Input: integer n > 1.

  1. Check if $n$ is a perfect power: if $n = a^b$ for integers $a
    > 1$ and $b > 1$, output composite.

  2. Find the smallest $r$ such that $ord_r(n) > (log_2 n)^2$ (if
    $r$ and $n$ are not coprime, then skip this $r$).

  3. For all $2 ≤ a ≤min(r, n−1)$, check that $a$ does not divide
    $n$: If $a|n$ for some $2 ≤ a ≤ min(r, n−1)$, output
    composite.

  4. If $n ≤ r$, output prime.

  5. For $a = 1$ to ${displaystyle leftlfloor scriptstyle {{sqrt
    {varphi (r)}}log_{2}(n)}rightrfloor}$ do

    if $((X+a)^n – (X^n+a))≠0bmod (X^r − 1,n)$, output
    composite;

  6. Output prime.

Emilのコメント・ノート5.が$ NC $階層にない。 $ GCD $は$ NC $で知られていないので、ステップ2.は$
NC $にはないようです。

私たちは$ r leqポリロッグ(n)$無条件の境界を持っているので、パラレルプロセッサテストのそれぞれで$ NC $で$
r |(n ^ k-1)$をテストすることによって、最小$ r $ parallelyコモンリミットが$ NC
$の場合はブーリアンロジックを使用してステップ2と5を組み合わせて並列に実行することができます。他のすべてのステップは、ブール論理を使用して完全に並列化できるようです。

したがって、$ GCD $の検索ではなく、($ GCD $の検索ではなく)共有のテストとこの特定の多項式の多項式の識別テストが$
NC $で証明された場合、素数は$ NC $ですか?

それは、共起が$ NC $である可能性があると思われる。これは$ GCD $ findingより簡単です。

ベストアンサー
申し訳ありませんが、適切な答えはありません

返信を残す

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