¿Cómo encontrar el generador en un grupo finito?

Question

Supongamos que un grupo $Z_p=$ { $1,2,3......(p-1)$ donde p es un número primo. ¿Cómo determinar el generador/generadores de este grupo? ¿cuáles son los posibles métodos para encontrarlo?

Answer 1

Supongamos que se puede factorizar el orden del grupo, $p-1$ (que no es una suposición segura para grandes $p$ ). Supongamos que $p-1$ tiene factorización prima $p-1 = f_1^{i_1}\cdots f_k^{i_k}$ . A continuación, puede probar cualquier elemento $a$ como generador calculando $a^{(p-1)/f_j} \bmod p$ para cada $j\in [1,k]$ . Si alguna vez consigues 1, entonces $a$ no es un generador. Si obtienes no-1's cada vez, entonces $a$ es. Sigue adivinando hasta que encuentres uno.

Tenga en cuenta que $Z_p^*$ es siempre cíclico, por lo que siempre hay un generador. De hecho, hay $\phi(p-1)$ de ellos. Si quiere que los generadores sean fáciles de encontrar, puede elegir un prime $p=2q+1$ donde $q$ es primo ya que entonces $\phi(p-1)=\phi(2q) = q-1$ lo que significa que casi la mitad del grupo son generadores. Necesitas unos 2 intentos esperados para encontrar uno.