1

给定生成器，如何检查元素 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

4

2 回答 2

3

也许你有更多关于组长什么样的信息。

如果你知道 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 生成的子群的元素。

于 2010-03-26T11:36:39.030 回答
1

查看离散对数问题和解决它的算法。

于 2010-03-25T19:37:12.950 回答