Entiendo que la definición de una raíz cúbica primitiva de la unidad en un campo finito $\mathbb{F}_p$ son todos aquellos números $x$ tales que $x^3=1$ pero $x\neq 1$ y $x^2 \neq 1$
Cuando tenemos un $p$ pequeño, digamos $p=7$, podemos calcular estos a través de 'fuerza bruta' - es decir, llenando la siguiente tabla:
\begin{array}{|c|cccccc|} \hline x & x^1 & x^2 & x^3 & x^4 & x^5 & x^6\\ \hline 1 & \underline{\bf{1}} & 1 & 1 & 1 & 1 & 1\\ 2 & 2 & 4 & \bf{\underline{1}} & 2 & 4 & 1\\ 3 & 3 & 2 & 6 & 4 & 5 & \underline{\bf{1}}\\ 4 & 4 & 2 & \underline{\bf{1}} & 4 & 2 & 1\\ 5 & 5 & 4 & 6 & 2 & 3 & \underline{\bf{1}}\\ 6 & 6 & \underline{\bf{1}} & 6 & 1 & 6 & 1\\ \hline \end{array}
Luego buscamos a lo largo de todas las filas cualquier valor de $x$ que tenga el primer valor de $1$ en la columna de $x^3$; en este ejemplo tenemos las raíces cúbicas primitivas de la unidad como $2$ y $4$ (primer valor de $1$ en cada fila está en negrita y subrayado en la tabla anterior)
Sin embargo, esto se vuelve poco factible cuando $p$ se vuelve muy grande.
¿Alguien puede indicarme un método fácil para calcular las raíces cúbicas primitivas de la unidad que requiera la menor cantidad de cálculos posible (eventualmente implementaré esto en Python usando valores de $p$ de varios cientos de dígitos de longitud)
0 votos
¿Es $p$ primo? Sin embargo, para un primo $p\ne2$, el hecho de que $x^3-1=(x-1)(x^2+x+1)$, da como resultado que sume al cálculo de $2^{p-2}\cdot\left(-1\pm\lambda\right)$, donde $\lambda^2=-3\pmod p$. Aunque en realidad no ganas mucho en tiempo de ejecución en comparación con tu primera suposición.
1 votos
No tengo respuesta a tu pregunta, pero ten en cuenta que cuando encuentras $a\in \mathbb F_p$ como una raíz cúbica primitiva de la unidad, entonces la otra raíz cúbica es $a^2$, y no necesitas buscar a través de $a+1, a+2,\ldots$ etc. Además, antes de hacer cualquier trabajo, vale la pena verificar si el campo tiene raíces cúbicas de la unidad (que no sean $1$) en él. Esto es "fácil" de verificar ya que necesariamente $p-1$ debe ser un múltiplo de $3$. Si se conoce $p$ en términos de su representación en base 10, la prueba es fácil de llevar a cabo. Si $p$ solo se conoce en representación base 2, es un poco más complicado.
0 votos
@ G.Sassatelli Sí, $p$ es primo. Y gracias por eso
0 votos
Quizás me falte algo aquí, pero todo se resume en calcular las raíces de $\;x^2+x+1=0\,\pmod p\;$, y así tenemos que saber si $\;-3\;$ es un residuo cuadrático, y luego $$\binom{-3}p=1\iff p=1\pmod3$$Así, por ejemplo en $\;\Bbb F_{17}\;$ no hay raíces primitivas de raíces cúbicas de la unidad, pero en $\;\Bbb F_{19}\;$ hay: $\;7\;,\;\;11\;$
0 votos
@DonAntonio, ¿podrías expandir un poco más sobre eso, por favor? Entiendo lo que es un residuo cuadrático, pero no veo cómo obtuviste $7$ y $11$ de él en $\mathbb{F}_{19}$.
0 votos
@lioness99a Ahora he agregado una respuesta.