Нахождение элемента в циклической группе простого порядка

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.

Answer 2

Ознакомьтесь с проблемой дискретного логарифма и алгоритмами для ее решения.