Encontrar eficazmente los generadores de un grupo cíclico

Question

¿Existe algún método eficaz para encontrar los generadores de un grupo cíclico?

Editar: El grupo (cíclico) se refiere aquí a un grupo general multiplicativo de módulo primo. ¿Hay algún algoritmo eficiente para encontrar los generadores del grupo (cíclico)?

Answer 1

Así que estás tratando de encontrar una raíz primitiva módulo de un primo. Wang, On the least primitive root of a prime, Scientia Sinica 10 (1961) 1-14, demostró que si la Hipótesis de Riemann Extendida es cierta, basta con probar los números 1, 2, 3, etc., sucesivamente para encontrar una raíz primitiva en tiempo polinómico. Se han producido mejoras en los detalles del resultado de Wang, pero no, creo, en la "visión general".

EDIT: En respuesta a algunos de los comentarios anteriores y posteriores, cito el libro de texto de Victor Shoup, A Computational Introduction to Number Theory and Algebra, página 268:

Encontrar un generador para ${\bf Z}_p^*$ : No hay ningún algoritmo eficiente conocido para este problema, a no ser que la factorización prima de $p-1$ es y aún así, debemos recurrir al uso de un algoritmo probabilístico algoritmo probabilístico.

Shoup se refiere a este punto en algunas notas en la página 281, donde discute el resultado de Wang sobre la raíz primitiva positiva más pequeña, y los resultados relacionados, y luego escribe

Por supuesto, sólo porque existe una pequeña raíz primitiva, no hay forma conocida de reconocer eficientemente una raíz primitiva módulo $p$ sin conocer la factorización primaria de $p-1$ .

También tomo nota del ejercicio 11.4:

Supongamos que existe un algoritmo eficiente que toma como entrada un entero positivo $n$ y un elemento $\alpha\in{\bf Z}_n^*$ y calcula el orden multiplicativo de $\alpha$ . Mostrar cómo utilizar este algoritmo para ... construir un algoritmo eficiente de factorización de enteros.