Los factorisations siga la factorización de $\Phi_n$ en los intermedios de los campos entre el$\mathbb Q$$\mathbb Q(\zeta_n)$.
Por ejemplo, supongamos $n=12$. Hay $4$ de los casos :
Si $p = 1 \pmod {12}$, $\Phi_{12}$ se divide en $\mathbb F_p$, así que tienes que encontrar una raíz primitiva de $1$, $\zeta_{12}$, a continuación, escriba $\Phi_{12}(X) = (X- \zeta_{12})(X- \zeta_{12}^5)(X- \zeta_{12}^7)(X- \zeta_{12}^{11})$
Si $p = 5 \pmod {12}$, entonces tiene la misma factorización en el $\mathbb Q(i)$,$(X^2-iX-1)(X^2+iX-1)$, por lo que sólo necesita encontrar una de las dos raíces cuadradas de $ -1$ $\mathbb F_p$ para obtener la factorización.
Si $p = 7 \pmod {12}$, entonces tiene la misma factorización en el $\mathbb Q(j)$,$(X^2-j)(X^2-j^2)$, por lo que sólo necesita para encontrar uno de los dos primitivos tercer raíces de $1$ $\mathbb F_p$ para obtener la factorización.
Si $p = 11 \pmod {12}$, entonces tiene la misma factorización en el $\mathbb Q(\sqrt 3)$,$(X^2-\sqrt 3 X + 1)(X^2+ \sqrt 3 X + 1)$, por lo que sólo necesita encontrar una de las dos raíces cuadradas de $3$ $\mathbb F_p$ para obtener la factorización.
En cualquier caso, encontrar a los factorisations significa que usted tiene que resolver algunas ecuaciones algebraicas en $\mathbb F_p$ (que no siempre son simples raíces por ejemplo si $n=7$ usted puede tener que encontrar a $\cos(2\pi/7)$ que es una raíz de un grado $3$ mientras que la ecuación no es una raíz cúbica), y en algunos casos, usted tiene que encontrar una primitiva $n$th raíz de $1$ raíz en $\mathbb F_p$.
Yo no creo que haya un gran salto en la dificultad de simplemente encontrar una raíz primitiva $\zeta_n$ $\mathbb F_{p^d}$ y, a continuación, calcular la irreductible factores que son todas las $(X- \zeta_n^k)(X - \zeta_n^{kp}) (X - \zeta_n^{kp^2})\ldots (X - \zeta_n^{kp^{d-1}})$
