Formas de encontrar el orden de un elemento en un grupo

Question

¿Existe una forma mejor de encontrar el orden de un elemento en un grupo que no sea dar vueltas hasta alcanzar la identidad?

¿Existe o PUEDE existir una mejor forma general de encontrar órdenes de elementos? (si no, por favor, explique por qué no puede haber ninguna manera)

Un ejemplo que tengo es un grupo multiplicativo de elementos $Z_{20}$ bajo el módulo 20. ¿Tengo que pasar por encima de cada elemento para encontrar órdenes?

Answer 1

Esta es una buena pregunta. Como habrás deducido de los comentarios, a falta de más información sobre el grupo, la respuesta es no, lo único que puedes hacer es probar sucesivamente con poderes superiores.

Pero en la mayoría de las situaciones que se dan en la práctica, se dispone de información adicional de un tipo u otro. Por ejemplo, si tu elemento es una matriz sobre un campo finito, o incluso sobre el número racional o un campo numérico, entonces el conjunto de todos los posibles órdenes de elementos es conocido (al menos en teoría).

En estas situaciones, se suele tener un límite superior multiplicativo para el orden. En otras palabras, se conoce un número entero (posiblemente muy grande) $N$ tal que el orden del elemento $g$ divide $N$ . A continuación, puede proceder de la siguiente manera

Para todos los primos $p$ dividiendo $N$ , computa $g^{N/p}$ . Si $g^{N/p} = 1$ para algunos $p$ , entonces sustituye $N$ por $N/p$ y empezar de nuevo - tenga en cuenta que habrá un máximo de $\log n$ reducciones de este tipo. En caso contrario, si $g^{N/p} \ne 1$ para todos $p$ , entonces el orden de $g$ debe ser $N$ .

Tenga en cuenta también que el cálculo de $g^N$ se puede lograr en $O(\log n)$ operaciones de grupo, escribiendo $N$ en binario $N = 2^{n_1} + \cdots + 2^{n_k}$ y luego se puede calcular $g^N$ como $g^{2^{n_1}} \cdots g^{2^{n_k}}$ .