java - 在素数阶循环群中查找元素

Question

在给定生成器的情况下，如何检查元素 a 是否属于特定的素数阶循环群 G？现在我只是生成组中的所有元素，将它们保存到容器中并检查元素是否在其中。这是我目前用来生成组的所有元素的代码:

public HashSet<BigInteger> group_elements(BigInteger g, BigInteger q) {

    HashSet<BigInteger> group = new HashSet<BigInteger>();

    BigInteger element = modPow(g,ONE,q);

    for (int i = 2; !group.contains(element); i++) {
        group.add(element);
        element = modPow(g, BigInteger.valueOf(i), q);
    }

    return group;

}

要查看某个元素是否在组中，我只需检查:

if (group.contains(num)) { ... }

如你所见，语言是Java

Answer 1

也许您有更多关于该组的信息。

如果你知道g生成的群G的阶，并且q是素数(你只告诉我们G的阶是素数，但没有告诉我们q)那么你可以检查一个元素x是否在G中通过测试

1 = x^ord(G) mod q.

如果 q 不是质数，则此测试无效。一个反例是 g = 22, q = 91, x = 53。这里 g 生成包含元素 {1, 22, 29} 的子群。 x 也有 3 阶，但不是 g 生成的子群的元素。