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 :

  1. Cyclotomic polynomial splits in $\mathbb{F}_p$ as degree = $ord_{q_i}(p)$ irreducible factors.
  2. Correspondence between splitting of ideal $ (p) $ in $\mathbb{Q}(\zeta_{q_i})$ and factorization of $\Phi_{q_i}(x)$ in $\mathbb{F}_p$.
  3. 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.


The galois group of cyclotomic field over $\Bbb Q$ is cyclic hence it will always contain such a subfield $\Bbb K$ and inertness follows from the fact that $\gcd([\Bbb K:\Bbb Q],[\Bbb Q(\zeta):\Bbb K])=1$ as $q-1$ is square free.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.