Encontrando un generador de$(\mathbb Z/p\mathbb{Z})^*$

Question

¿Existe un método para encontrar un elemento primitivo (generador) de$(\mathbb Z/p\mathbb{Z})^*$, donde$p$ es un número primo?

Answer 1

William Stein tiene una página web sobre el problema de encontrar los generadores de $(\mathbb{Z}/p\mathbb{Z})^*$.

Hay algunos probabilístico polytime algoritmos para la búsqueda de raíces primitivas. Asumiendo también la Extendida Hipótesis de Riemann, no son polytime algoritmos.

Sin embargo, en general no eficiente (rápido) algoritmo es conocido.