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 に答える