Recherche d'un élément dans un groupe cyclique de premier ordre

Question

Comment vérifier si un élément a appartient à un groupe cyclique spécifique G de premier ordre, étant donné le générateur? En ce moment, je crée simplement tous les éléments du groupe, les enregistre dans un conteneur et vérifie si l'élément est dedans. Ceci est le code im utilise actuellement pour générer tous les éléments du groupe:

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; 

} 

Et pour voir si un élément est dans le groupe je vérifie simplement:

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

Comme vous pouvez le voir la langue is Java

Answer 1

Découvrez le problème discrete logarithm et le algorithms pour le résoudre.

Answer 2

Peut-être avez-vous plus d'informations sur l'apparence du groupe. Si vous connaissez l'ordre du groupe G généré par g, et si q est premier (vous nous avez seulement dit que l'ordre de G est premier, mais rien à propos de q) alors vous pouvez vérifier si un élément x est dans G en testant

1 x = ^{ord (G)} mod q.

Si q n'est pas premier alors ce test ne fonctionne pas. Un exemple de compteur serait g = 22, q = 91, x = 53. Ici, g génère le sous-groupe avec les éléments {1, 22, 29}. x a également l'ordre 3, mais n'est pas un élément du sous-groupe généré par g.