Resolver $x^3 \equiv 1 \pmod p$ $x$

Question

¿Cómo puedo encontrar solución para $x^3 \equiv 1 \pmod p$ ($p$ un primer) eficientemente?

La raíz trivial es $x_1 = 1$. Necesito encontrar otra raíces $x_2, x_3$.

Answer 1

Los enteros modulo $p$ formulario un campo. Desde $x^3 - 1 = (x-1)(x^2+x+1)$, el problema es equivalente a resolver $x^2+x+1\equiv 0 \pmod{p}$. Para $p\neq 2$, la habitual fórmula cuadrática de las obras; por lo que tendría que encontrar $y$ tal que $y^2\equiv -3\pmod{p}$. Si $p=2$, $x^2+x+1=0$ no tiene soluciones, y si $p=3$,$x^3-1 = (x-1)^3$, así que de nuevo no hay ninguna raíz distinta de $x=1$.

Vamos a considerar los otros primos, $p\gt 3$.

El uso de la reciprocidad cuadrática, si $p\equiv 1\pmod{4}$, $-1$ es un cuadrado modulo $p$ y tenemos: $$\left(\frac{-3}{p}\right) = \left(\frac{-1}{p}\right)\left(\frac{3}{p}\right) = \left(\frac{p}{3}\right).$$ Así que si $p\equiv 1 \pmod{3}$ (por lo tanto,$p\equiv 1 \pmod{12}$), a continuación, $-3$ es un cuadrado modulo $p$; si $p\equiv 2\pmod{3}$ (por lo $p\equiv 5\pmod{12}$), $-3$ no es un cuadrado modulo $p$, así que no hay otra solución.

Si $p\equiv 3\pmod{4}$, $-1$ no es un cuadrado modulo $p$, y tenemos: $$\left(\frac{-3}{p}\right)=\left(\frac{-1}{p}\right)\left(\frac{3}{p}\right) = \left(\frac{p}{3}\right)$$ (desde $\left(\frac{3}{p}\right) = -\left(\frac{p}{3}\right)$); de nuevo, si $p\equiv 1\pmod{3}$ (por lo $p\equiv 7\pmod{12}$), a continuación, $-3$ es un cuadrado modulo $p$; y si $p\equiv 2\pmod{3}$ (por lo $p\equiv 11\pmod{12}$), a continuación, $-3$ no es un cuadrado modulo $p$.

En resumen, hay raíces de $x^3-1$ modulo $p$ otros de $x\equiv 1\pmod{p}$ si y sólo si $p\equiv 1\pmod{6}$. Si $p=6k+1$ es un número primo, entonces las dos raíces de la $x^3-1$ otros de $x=1$ son precisamente las raíces de $x^2+x+1$, los cuales son $$\frac{-1\pm\sqrt{-3}}{2} = -3k(-1\pm a),$$ donde $a$ es un número entero tal que $a^2\equiv -3\pmod{p}$. Esto significa que usted todavía necesita para averiguar la raíz cuadrada, que puede realizarse mediante cualquiera de los métodos sugeridos por Bill Dubuque, tales como Tonelli del algoritmo (es decir, en los Mangos de la versión, como se describe en Wikipedia).

Agregado: Como Alex Bartel notas en los comentarios y en su propia respuesta, se puede evitar el uso de la reciprocidad cuadrática anterior. Desde las unidades de $\mathbb{Z}/p\mathbb{Z}$ formar un grupo cíclico de orden $p-1$, hay soluciones no triviales a $x^3=1$ si y sólo si $3$ divide el orden, es decir, si y sólo si $p\equiv 1\pmod{3}$. A partir de ahí, es fácil saltar a soluciones si y sólo si $p\equiv 1 \pmod{6}$, ya que de lo contrario tendríamos $p\equiv 4\pmod{6}$ lo cual es imposible, ya que $p$ es primo. Una vez que se establece que, la fórmula cuadrática puede ser aplicado seguro en el conocimiento que estos primos deben tener $-3$ como residuos cuadráticos.

Answer 2

En primer lugar, tenga en cuenta que si el $p \equiv 2\text{ mod } 3$, luego elevar a la tercera potencia es un bijection en $\left(\mathbb{Z}/p\mathbb{Z}\right)^\times$, por lo que 1 es la única raíz. Si $p \equiv 1\text{ mod } 3$, entonces lo único que puedo pensar para encontrar las raíces es encontrar una raíz primitiva módulo $p$ (es decir, un generador de la cíclica del grupo $\left(\mathbb{Z}/p\mathbb{Z}\right)^\times$) y llevarlo al % de poderes $(p-1)/3$y $2(p-1)/3$.

Answer 3

Algoritmo de Tonelli para raíces cuadradas se puede generalizar fácilmente a calcular raíces d'th en campos finitos, e.g. vea Adleman; Manders; Miller: Tomando raíces en campos finitosy Bach; Shallit: Teoría algorítmica del número, sección 7.3.