Hola
Hola, quisiera saber si hay otra forma más optimizada de encontrar generadores que la "fuerza bruta". Por ejemplo, encontrar un generador en \( (\mathbb{Z}/343\mathbb{Z})^* \).
En general nota lo siguiente (denoto \( (\mathbb{Z}/n\mathbb{Z})^*=\Bbb U_n \).
1) \( \Bbb U_n \) es cíclico si y sólo si \( n=1,2,4,p^k \) ó \( 2p^k \) con \( p>2 \) primo y \( k\geq 1 \) natural.
En tu caso \( n=343=7^3 \), luego si es cíclico.
2) Sabemos que \( orden(\Bbb U_n)=\varphi(n) \). En tu caso \( \varphi(n)=\varphi(7^3)=7^2(7-1)^2=2\cdot 3\cdot t^2 \).
3) El orden de un elementpo en \( \Bbb U_n \) necesariamente es divisor de \( \varphi(n) \). Si \( x\in \Bbb U_n \) NO es un generador entonces \( x^k=1 \) mod \( n \) con \( k \) divisor propio de \( \varphi(n) \). Pero también \( x^m=1 \) mod \( n \) para cualquier divisor propio de \( \varphi(n) \) múltiplo de \( k \).
4) Como consecuencia de lo anterior
para probar que \( x \) es generador basta comprobar que \( x^k\neq 1 \) mod \( k \) para todo \( k=\varphi(n)/p \) siendo \( p \) factor primo de \( \varphi(n) \). Eso es por (3) y porque los números \( k=\varphi(n)/p \) son los únicos divisores propios de \( \varphi(n) \) sin múltiplos que también sean divisores propios de \( \varphi(n) \).
En tu caso entonces para comprobar si \( x \) es generador "sólo" tienes que calcular \( x^{2\cdot 3\cdot 7},x^{2\cdot 7^2},x^2{3\cdot 7^2} \) módulo \( 343 \).
Comprueba que \( x=2 \) no cumple \( (4) \), pero \( x=3 \) si.
Saludos.
