-2

在下面的片段中，请从第一个“for”循环开始解释发生了什么以及为什么。为什么加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 都有一个布尔值。当你这样看时，很明显每个值都设置为 0 以将其初始化为 false，然后设置为 1 以将其设置为 true。

  • 最后一个 for 循环是测试所有的布尔值。如果其中任何一个为 0（表示为假），则该函数返回假。如果全部为真，则该函数返回真。

  • 解释if您询问的语句将需要解释原始根 mod n 是什么，这是函数的全部要点。我认为如果你的目标是理解这个程序，你应该首先理解它实现了什么。如果您阅读Wikipedia关于它的文章，您会在第一段中看到：

在模算术（数论的一个分支）中，原根模 n 是任何数 g，其性质是任何与 n 互质的数都与 g 的幂（mod n）全等。也就是说，如果 g 是一个原始根 (mod n)，那么对于每个具有 gcd(a, n) = 1 的整数 a，都有一个整数 k 使得 gk ≡ a (mod n)。k称为a的索引。也就是说，g 是整数模 n 的乘法群的生成器。

  • 函数modPow实现模幂运算。一旦您了解了如何找到原始根 mod n，您就会理解它。

也许你的最后一个难题是知道如果两个数字的最大公约数是 1，它们是互质的。所以你会在你粘贴的算法中看到这些检查。

额外链接： 这篇论文有一些很好的背景，包括如何在结尾处测试原始根。

于 2010-05-14T20:57:45.697 回答