Diffie-Hellman -- 原根 mod n -- 密码学问题

Question

在下面的代码片段中，请从第一个“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;

}

Answer 1

• 将向量视为布尔值列表，0 到 m 中的每个数字都有一个布尔值。当您以这种方式查看时，很明显每个值都设置为 0 以将其初始化为 false，然后设置为 1 以将其设置为 true。

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

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

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

• 函数 modPow 实现 模幂。一旦你了解了如何找到原根 mod n，你就会明白它。

也许您面临的最后一个难题是要知道，如果两个数字的最大公约数为 1，则它们互质。因此，您会在粘贴的算法中看到这些检查。

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