I am reading this paper by Adleman,Lenstra on finding Irreducible polynomial over Finite field. Here in Section VI(Proof of correctness of Algo B) I came across this argument:
Let $q_i $ be a prime such that $q_i-1$ is square free. Then $\mathbb{Q}(\zeta_{q_i})$ contain a subfield $K$ such that $[K:\mathbb{Q}]=ord_{q_i}(p)$ and prime p is inert in $K$.
I am aware of following facts :
- Cyclotomic polynomial splits in $\mathbb{F}_p$ as degree = $ord_{q_i}(p)$ irreducible factors.
- Correspondence between splitting of ideal $ (p) $ in $\mathbb{Q}(\zeta_{q_i})$ and factorization of $\Phi_{q_i}(x)$ in $\mathbb{F}_p$.
- Since $ord_{q_i}(p) | q_i-1$, therefore there exist a field K' such that $[K':\mathbb{Q}]=ord_{q_i}(p)$.
But I am not sure of how these things give the claim given in the paper.