Diffie-Hellman -- Primitive root mod n -- cryptography question.

Question

In the below snippet, please explain starting with the first "for" loop what is happening and why. Why is 0 added, why is 1 added in the second loop. What is going on in the "if" statement under bigi. Finally explain the modPow method. Thank you in advance for meaningful replies.

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

• Treat the vector as a list of booleans, with one boolean for each number 0 to m. When you view it that way, it becomes obvious that each value is set to 0 to initialize it to false, and then set to 1 later to set it to true.

• The last for loop is testing all the booleans. If any of them are 0 (indicating false), then the function returns false. If all are true, then the function returns true.

• Explaining the if statement you asked about would require explaining what a primitive root mod n is, which is the whole point of the function. I think if your goal is to understand this program, you should first understand what it implements. If you read Wikipedia's article on it, you'll see this in the first paragraph:

In modular arithmetic, a branch of number theory, a primitive root modulo n is any number g with the property that any number coprime to n is congruent to a power of g (mod n). That is, if g is a primitive root (mod n), then for every integer a that has gcd(a, n) = 1, there is an integer k such that gk ≡ a (mod n). k is called the index of a. That is, g is a generator of the multiplicative group of integers modulo n.

• The function modPow implements modular exponentiation. Once you understand how to find a primitive root mod n, you'll understand it.

Perhaps the final piece of the puzzle for you is to know that two numbers are coprime if their greatest common divisor is 1. And so you see these checks in the algorithm you pasted.

Bonus link: This paper has some nice background, including how to test for primitive roots near the end.