Finding an element in a cyclic group of prime order

Question

Greetings!

How do I check if an element a belongs to a specific cyclic group G of prime order, given the generator? Right now i simply generate all the elements in the group, save them into a container and check if the element is in it. This is the code im currently using to generate all the elements of the group:

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;

}

And to see if a element is in the group i simply check:

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

As you can see the language is Java

Answer 1

Check out the discrete logarithm problem and the algorithms for solving it.

Answer 2

Maybe you have some more information about what the group looks like.

If you know the order of the group G generated by g, and if q is prime (you only told us that the order of G is prime, but nothing about q) then you can check if an element x is in G by testing

1 = x^ord(G) mod q.

If q is not prime then this test does not work. A counter example, would be g = 22, q = 91, x = 53. Here g generates the subgroup with the elements {1, 22, 29}. x also has order 3, but is not an element of the subgroup generated by g.