-2

以下のスニペットでは、最初の「for」ループから始めて、何が起こっているのか、そしてその理由を説明してください。2番目のループで0が追加されるのはなぜですか、1が追加されるのはなぜですか。bigiの下の「if」ステートメントで何が起こっているのか。最後に、modPowメソッドについて説明します。有意義なご返信をよろしくお願いいたします。

public static boolean isPrimitive(BigInteger m, BigInteger n) {

    BigInteger bigi, vectorint;
    Vector<BigInteger> v = new Vector<BigInteger>(m.intValue());
    int i;

    for (i=0;i<m.intValue();i++)
        v.add(new BigInteger("0"));

    for (i=1;i<m.intValue();i++)
    {
        bigi = new BigInteger("" + i);

        if (m.gcd(bigi).intValue() == 1)
            v.setElementAt(new BigInteger("1"), n.modPow(bigi,m).intValue());
    }

    for (i=0;i<m.intValue();i++)
    {
        bigi = new BigInteger("" + i);

        if (m.gcd(bigi).intValue() == 1)
        {
            vectorint = v.elementAt(bigi.intValue());
            if ( vectorint.intValue() == 0)
                i = m.intValue() + 1;
        }
    }

    if (i == m.intValue() + 2)
        return false;
    else
        return true;

}
4

1 に答える 1

1

  • 0 から m までの数値ごとに 1 つのブール値を持つ、ブール値のリストとしてベクトルを扱います。そのように見ると、各値が 0 に設定されて false に初期化され、後で 1 に設定されて true に設定されていることが明らかになります。

  • 最後の for ループは、すべてのブール値をテストしています。それらのいずれかが 0 (false を示す) の場合、関数は false を返します。すべてが true の場合、関数は true を返します。

  • あなたが尋ねたステートメントを説明するにはif、プリミティブルート mod n が何であるかを説明する必要があります。これが関数の要点です。あなたの目標がこのプログラムを理解することであれば、まずそれが何を実装しているのかを理解する必要があると思います. ウィキペディアの記事を読むと、最初の段落に次のように表示されます。

数論の一分野である剰余算術では、n を法とする原始根は、n と互いに素な任意の数が g のべき乗 (mod n) に合同であるという性質を持つ任意の数 g です。つまり、g が原始根 (mod n) の場合、gcd(a, n) = 1 を持つすべての整数 a に対して、gk ≡ a (mod n) となる整数 k が存在します。k は a のインデックスと呼ばれます。つまり、g は n を法とする整数の乗法群の生成元です。

  • 関数modPowはべき乗剰余を実装します。原始根 mod n を見つける方法を理解すれば、理解できるでしょう。

おそらく、パズルの最後のピースは、最大公約数が 1 の場合、2 つの数値が互いに素であることを知ることです。貼り付けたアルゴリズムにこれらのチェックが表示されます。

ボーナス リンク: この論文には、最後にプリミティブ ルートをテストする方法など、優れた背景がいくつかあります。

于 2010-05-14T20:57:45.697 に答える